Solution
The Josephus Survivor
Show the problem again
100 people stand in a circle, numbered 1 to 100. Starting the count at person 1, every second person is eliminated (so person 2 goes first), around and around until only one remains. What number survives?
Worked solution
The answer is 73. For the k = 2 Josephus problem with n = 2^m + ℓ people (0 ≤ ℓ < 2^m), the survivor is 2ℓ + 1. Here 100 = 64 + 36, so the survivor is 2 · 36 + 1 = 73. The slick proof: after ℓ eliminations, exactly a power of two remain and the count is starting fresh at position 2ℓ + 1, which a power-of-two circle never eliminates. Equivalently, cyclically left-shift the binary representation of n: 1100100 → 1001001 = 73.
Source: The Josephus problem, named for the account in Flavius Josephus; standard treatment in Graham, Knuth and Patashnik, 'Concrete Mathematics' (1989). Statement written for AxiomIQ.