On this page
Who survives in a counting circle of 10?
In the classic counting-out puzzle known as the Josephus problem, a group stands in a circle numbered clockwise from 1 to n. Starting with person 1, counting proceeds around the ring: person 1 is skipped, person 2 is eliminated, person 3 is skipped, person 4 is eliminated, and so on until one survivor remains.
The puzzle traces to The Jewish War by 1st-century historian Flavius Josephus. Following a 47-day Roman siege of Yodfat in 67 CE, Josephus and 40 companions hid in a cave, resolving to die rather than surrender. Josephus proposed drawing lots to eliminate each other in sequence. Through luck or calculation, Josephus and one comrade were the last two survivors, choosing to surrender.
In the modern mathematical problem catalogued on Wolfram MathWorld, we consider a circle of 10 people where every second person leaves. Tracing the eliminations step by step:
Round 1: Starting at 1, persons 2, 4, 6, 8, and 10 are eliminated. Five people remain: 1, 3, 5, 7, and 9.
Round 2: Person 1 is skipped, eliminating 3. Person 5 is skipped, eliminating 7. Person 9 is skipped, wrapping around to eliminate 1. Only 5 and 9 remain.
Round 3: Person 5 is skipped, eliminating 9.
Position 5 survives.
Why does the safe seat reset at powers of 2?
Simulating large crowds by hand quickly becomes tedious. Solving the puzzle for any crowd requires testing small circle sizes and identifying the invariant pattern.
When you record the winning position across consecutive circle sizes, catalogued as sequence A006257 in the On-Line Encyclopedia of Integer Sequences, a distinct rhythm appears. Testing circle sizes 1 to 16 yields survivor seats 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, and 1.
Whenever n is an exact power of 2 (2, 4, 8, 16), position 1 always wins. Each lap eliminates half the circle while returning the turn to person 1, repeating until only person 1 remains.
For other values, write n = 2ᵐ + l, where 2ᵐ is the largest power of 2 in n and l is the excess. Eliminating l people removes positions 2, 4, 6, ..., 2l, leaving exactly 2ᵐ people. The turn passes to person 2l + 1, who is guaranteed to survive:
W(n) = 2l + 1
For our 10-person circle, 10 = 2³ + 2 = 8 + 2. Here m = 3 and l = 2. The winning seat is 2(2) + 1 = 5.
How does binary bit shifting predict the survivor?
This algebraic formula hides a fast bitwise shortcut. In Concrete Mathematics, Ronald L. Graham, Donald E. Knuth, and Oren Patashnik showed that the Josephus recurrence corresponds to a one-bit cyclic left shift in binary, a property surveyed in the Josephus problem on Wikipedia. As highlighted in Donald Knuth's pioneering analysis of algorithms, algebraic recurrences often simplify into basic bitwise operations.
In base 2, n = 2ᵐ + l starts with a leading 1 followed by the bits of l: n = 1 bₘ₋₁ ... b₀. In the formula 2l + 1, multiplying by 2 shifts l left, and adding 1 sets the final bit to 1. The leading 1 moves to the end, turning n into its survivor seat:
Circle of 10: In binary, 10 is 1010. Moving the leading 1 gives 0101, which is 5.
Circle of 41: In binary, 41 is 101001. Moving the leading 1 gives 010011, which is 19.
Circle of 100: In binary, 100 is 1100100. Moving the leading 1 gives 1001001, which is 73.
Connecting binary place values to modular arithmetic is central to the binary number system curriculum in CBSE computer science syllabus, echoing ideas rooted in Pingala's ancient combinatorics and binary sequences.
How can active simulation build mathematical intuition?
Working through the Josephus problem shows why active exploration beats formula memorisation. Sketching small circle sizes lets the power-of-two pattern emerge naturally.
In learning science, visual models help students link physical actions with abstract recurrences. For concepts where dynamic movement makes the mathematics transparent, the Fermi Simulation Lab offers interactive simulations designed for ideas that are easier to see than to read. For structured practice on competitive math and algorithmic challenges, the Fermi Problem Library provides worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
To solve the Josephus problem for any circle size n in your head, use this four-step plan:
Find the highest power of 2 within n (denote it as 2ᵐ).
Subtract that power to find the excess participants: l = n − 2ᵐ.
Double the excess and add one: 2l + 1.
Verify by writing n in binary and moving the leading 1 to the right end.
