Powers Of Two In The Josephus Problem

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)

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)

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 = 2¹ = 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 = 2^m. Show person 1 is the winner for n = 2^m+1.

When n = 2^m+1, 2^m people — all the even numbered people — are eliminated in the first pass, leaving 2^m people — all the odd numbered people — remaining. By the induction hypothesis, person 1 is the winner of the n = 2^m remaining people, and thus the winner among all n = 2^m+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)

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 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 = 2^m + k, where 2^m 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 = 2^m + k and w = 2k + 1 to get a single formula for w:

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

  w = 2(n – 2^m) + 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 2^m 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(log₂(n)), or .

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

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.