The positions of a circle are numbered from 1 to \(n\). Position 2 is eliminated first, then 4, then 6, and so on, continuing in a circular manner between the positions that are still alive, until only one remains. Which position survives in the end?
Home > Riddles > A cyclic elimination
A cyclic elimination
It is a problem of rhythm rather than violence: a regular elimination ends up hiding a very clear structure. The beautiful thing here is that the pattern takes a while to appear, but then you can't forget it.
Hints
Show hints
- Try small values first and note who survives.
- Sizes that are powers of 2 behave especially cleanly.
- Then see what happens when you intersperse the cases that remain between those powers.
Solution
Show full solution
Answer: Yes
$$ n = 2^m + l \qquad\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\text{con}\qquad 0 \le l < 2^m, $$
then the surviving position is
$$ 2l+1. $$ The pattern is immediately seen in the first cases: $$
1\to1,\quad 2\to1,\quad 3\to3,\quad 4\to1,\quad 5\to3,\quad 6\to5,\quad 7\to7,\quad 8\to1.
$$ Whenever the number of people is a power of 2, position 1 survives. Why? In the first round all even positions disappear and exactly the odd ones survive:
$$ 1,3,5,\dots $$
If you renumber them as
$$ 1,2,3,\dots, $$
the problem that remains is of the same type, only smaller. That means that when you write
$$ n=2^m+l, $$
the entire $2^m$ portion is “consumed” and the excess $l$ determines how much the answer shifts from 1. The final survivor turns out to be
$$ 2l+1. $$ It is also equivalent to an elegant binary rule: take the binary writing of $n$, move the first bit to the end, and interpret the result back into binary. $$
Related riddles
Keep practicing
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.