Powers Of Two In The Josephus Problem

By Rick Regan July 24th, 2009

Pradeep Mutalik of The New York Times recently blogged about a puzzle that is an instance of the Josephus Problem. The problem, restated simply, is this: there are n people standing in a circle, of which you are one. Someone outside the circle goes around clockwise and repeatedly eliminates every other person in the circle, until one person — the winner — remains. Where should you stand so you become the winner?

Here’s an example with 13 participants:

Alternating Elimination with 13 people, order of elimination shown in red (winner is person 11)
Alternating Elimination with 13 people, order of elimination shown in red (winner is person 11)

As Pradeep and his readers point out, there’s no need to work through the elimination process — a simple formula will give the answer. This formula, you won’t be surprised to hear, has connections to the powers of two and binary numbers. I will discuss my favorite solution, one based on the powers of two.

When the Number of Participants is a Power of Two

Alternating elimination means one of every two participants is eliminated. This is halving, and suggests powers of two are involved. Let’s first explore this with the special case where the number of participants is a power of two, since powers of two halve neatly into powers of two.

Here is an example circle with eight people:

Alternating Elimination (8 people)
Alternating Elimination (8 people)

The elimination process works like this: the first pass starts at person 1 and proceeds clockwise, and each new pass starts every time person 1 is reached. The people eliminated on a pass are crossed out, and are marked to indicate the order in which they were eliminated. Eliminated people are then omitted in subsequent diagrams.

Three passes are required to determine the winner:

  • Pass 1 eliminates four people: 2, 4, 6, 8.
  • Pass 2 eliminates two people: 3, 7.
  • Pass 3 eliminates one person: 5.

This leaves person 1 the winner.

The number of people eliminated (and equivalently, remaining) per pass follows the same pattern as in a single-elimination tournament with a power of two number of participants.

Analysis

Regardless of the number of participants n, person 1 survives the first pass. Since n is even, as every positive power of two is, person 1 survives the second pass as well. In the first pass, the process goes like this: person 1 is skipped, person 2 is eliminated, person 3 is skipped, person 4 is eliminated, … , person n-1 is skipped, person n is eliminated. The second pass starts by skipping person 1.

As long as the number of participants per pass is even, as it will be for a power of two starting point, the same pattern is followed: person 1 is skipped each time. Therefore, for any power of two, person 1 always wins.

Proof by Induction

You can also show that person 1 is the winner using an inductive proof (for details see Miguel Lerma’s proof of the Josephus problem). Compared to the argument above, induction works in the opposite direction; that is, it builds up to a more complicated problem from a simpler one.

For n = 21 = 2 participants, the base case, it’s easy to see that person 1 is the winner. For the induction hypothesis, assume person 1 is the winner for n = 2m. Show person 1 is the winner for n = 2m+1.

When n = 2m+1, 2m people — all the even numbered people — are eliminated in the first pass, leaving 2m people — all the odd numbered people — remaining. By the induction hypothesis, person 1 is the winner of the n = 2m remaining people, and thus the winner among all n = 2m+1 people. Therefore, for any power of two, person 1 always wins.

When the Number of Participants is NOT a Power of Two

When the number of participants is not a power of two, we know this much: person 1 can’t be the winner. This is because at least one pass will have an odd number of participants. Once the first odd participant pass is complete, person 1 will be eliminated at the start of the next pass.

So is there an easy way to determine who is the winner? Let’s step back and take a closer look at the elimination process in the 13-person example:

Alternating Elimination (13 people)
Alternating Elimination (13 people)

Four passes are required to determine the winner:

  • Pass 1 eliminates six people: 2, 4, 6, 8, 10, 12.
  • Pass 2 eliminates four people: 1, 5, 9, 13.
  • Pass 3 eliminates one person: 7.
  • Pass 4 eliminates one person: 3.

This leaves person 11 the winner.

Analysis

Powers of two come into play here, but you have to change your perspective to see them. They don’t occur on pass boundaries — they span them. At some point, during pass 1, the number of participants remaining becomes a power of two. In this example, that occurs when 5 of the 13 people are eliminated, leaving an 8 person problem: 11, 12, 13, 1, 3, 5, 7, 9. This means person 11, the first person in the new power of two circle, wins.

Here’s the 13-person example again, with the 8-person power of two sub case shown explicitly with passes realigned:

8-Person Power of 2 Subset of 13-Person Problem
8-Person Power of Two Subset of 13-Person Problem

(It occurred to me that the alternating elimination process is an indirect way to check whether a number is a positive power of two. A number is a positive power of two if and only if, when halved repeatedly, becomes 1.)

The Equations

We can solve both cases — in other words, for an arbitrary number of participants — using a little math.

Write n as n = 2m + k, where 2m is the largest power of two less than or equal to n. k people need to be eliminated to reduce the problem to a power of two, which means 2k people must be passed over. The next person in the circle, person 2k + 1, will be the winner. In other words, the winner w is w = 2k + 1.

Let’s apply these equations to a few examples:

  • n = 8: The equations still apply, although using them is unnecessary: n = 8 + 0, so k = 0 and w = 0 + 1 = 1.
  • n = 13: n = 8 + 5, so k = 5 and w = 2*5 + 1 = 11.
  • n = 1000: This is the example in the New York Times: n = 1000 = 512 + 488, so k = 488 and w = 2*488 + 1 = 977.

The Formula

We can combine the equations n = 2m + k and w = 2k + 1 to get a single formula for w:

  • Rearrange n = 2m + k to isolate k: k = n – 2m.
  • Substitute this expression for k into w = 2k + 1:

    w = 2(n – 2m) + 1

The Formula as a Function of One Variable

As written, the formula is a function of two variables, n and m. This works fine, but ideally it should be a function of only one variable — n. This means we have to eliminate m, or more precisely, make m itself a function of n.

We described 2m loosely as “the largest power of two less than or equal to n,” but that is an algorithmic description. Described mathematically, m is the integer part of the base 2 logarithm of n; that is, m = floor(log2(n)), or \mbox{\footnotesize{\displaystyle{\lfloor log_2(n) \rfloor}}}.

So now we have a formula in terms of the number of participants n:

\mbox{\footnotesize{\displaystyle{w = 2\left(n $-$ 2^{\lfloor log_2(n) \rfloor} ) + 1}}}

Summary

An alternating elimination Josephus problem has a deep connection to the powers of two, a connection reflected in the formula we derived to find the winning spot. The formula requires a few simple calculations, and is a function of the number of participants n: find the largest power of two in n, subtract it from n, double the result, and add 1. The person in that spot will be the winner.

Dingbat

39 comments

  2. Lee,

    I see why your star drawing problem would remind you of this, but one major difference is that it does not “eliminate” points; that is, points that are visited still figure in the skipping.

  3. Rick,

    You are of course correct; my problem is very different in this regard.

    You are also correct in your answer to the “Extra Credit Quiz.” The “totient” function has a particularly simply value for arguments that are powers of 10.

    phi(10^n)=phi((2*5)^n)=10^n*(2-1)/2*(5-1)/5=4*10^(n-1)

    So phi(1000)=400

    and

    (phi(1000)-2)/2 = (400-2)/2 = 200-1 = 199

    Thanks for getting back.

    Lee

  4. Hi Rick,

    Thanks for referring to my blog. Your article looks great.

    I have one suggestion. Since your article is about binary numbers, you may want to discuss the following method of obtaining the solution using binary numbers. It was posted by one of the readers of my blog. I mentioned this in my solution post as follows:

    “Joe gave an elegant method to find the answer using binary numbers. You write 1000 in binary as 1111101000. Now move the leftmost digit over to the right. That gives you 1111010001. Convert that into decimal, and voila, you have 977!”

  5. Pradeep,

    I omitted the binary calculation mainly because I didn’t think it provided insight into the problem.

    In the derived formula w = 2(n – 2m) + 1, subtracting 2m is the same as zeroing the highest 1 bit of n, multiplying by 2 is the same as shifting left one place, and adding one is the same as setting the lowest bit to 1 — in other words, what works out to be a rotate left. I think it a happy coincidence, rather than a reflection of the underlying structure of the problem, that this is so.

    I spent quite a bit of time trying to work back from rotate left to a derivation in terms of the problem. To this end, I explored its relationship to the “divide by 2” binary conversion algorithm — it kind of works if you do an extra step at the beginning and skip the last divide — but still I couldn’t map it as cleanly to the problem as I could the powers of two. (If you have any thoughts on this approach let me know).

    Thanks for taking the time to comment.

  7. Abhishek,

    I’m not sure what you mean. By convention, the person at the start of the circle is person number 1. However, you could change that so that you number the people first and then start from any number. But then, the answer is the number you start with, whether it’s a power of two or not.

  8. Hi Rick

    Sorry , I didnt understand the following sentence.

    Write n as n = 2m + k, where 2m is the largest power of two less than or equal to n. k people need to be eliminated to reduce the problem to a power of two, which means 2k people must be passed over.

    You found that 2k people should be passed over. Can you plz explain more how you arrived on this logic?

    Thanks

  9. @Manish,

    The superscripts did not come out in your comment, so I’ll rewrite the sentence you asked about here:

    Write n as n = 2m + k, where 2m is the largest power of two less than or equal to n. k people need to be eliminated to reduce the problem to a power of two, which means 2k people must be passed over.

    Maybe the confusion is with my use of the term “passed over.” I don’t mean skipped over. I just meant that for every two people encountered, one is eliminated. (I was using “pass” as in “taking a pass around the circle.”)

  10. Thank you! This was very helpful for my class! I showed my 7th graders this and they really were able to grasp on to this

  12. Pingback: Josephus Problem

  13. Hi Rick Regan

    Thank you for the simpler explanation of the problem.
    Can you please tell us how should we approach to the problem when every 7th person is to be eliminated rather than every alternate person?

  15. @Rick Regan
    Thanks but I couldnt undertand from the wikipedia reference. Can you please explain the generalised form in your point of view?

  17. @Prachi (and Rick)
    For the binary case, the formula is
    w = 2(n-2^m) + k, where m = floor(log base 2 of n)
    Perhaps replacing the 2’s with 7’s would work?

    Also, I agree: the wikipedia page on this problem IS rather confusing.

  18. I want to know a variation of this problem. If each time if we eliminate people in an increasing order, like in 1st move the 1st person, in 2nd move we remove the 2nd person, then in the third move we remove the 3rd person…how can i proceed..??

  22. if there are 513 persons,,, then what is the answer????by follow these formula ,getting the value 2… how it is possible??? can u plz explain????

  24. Hi Rick,

    Could you maybe explain how the final formula works.
    i.e. when I’m stuck when computing (n-2^log2⁡n) the answer will always be 1? as 2^log2n = n. Hence n – n =1.. could you please clarify?

    (yes i know it’s logbase2n)

  26. hey i wanted to ask if there is another way to solve this problem that could be a little easier
    i also wanted to ask if there are more interesting riddles to be solved and with alot of strategies
    i have a project and i need an interesting riddle as soon as possible

  30. Hi, Could You please explain what i should do when step is 3 or something else.
    I just need some formula which i can use with any number of participants and any step. I tried to use formula from Wiki but it doesn’t work for me. Thank’s.

  34. A very good way of deriving a formula…I hope this is the best solution as per the computer programming..because it does not have recursion. As this does not have recursion, we can use this formula for any positive integer n.
    Simply Superb!!!

  36. A real easy way – without any formula – to convert the number of people in the circle to a binary number. Next, remove the most significant digit, which is always a “1”, and make it the least significant digit. Convert back to a Base 10 number. This new binary number will always be the remaining person.
    For example: 79
    Binary: 1001111
    New Binary Number: 0011111 = 11111
    Converted to Base 10: 31

Comments are closed.

Copyright © 2008-2024 Exploring Binary

Privacy policy

Powered by WordPress

css.php