A regular elimination, repeated in a circle, ends up hiding a surprisingly clean structure. The pattern takes a while to appear, but when it does it no longer admits of doubt.
A cyclic elimination
Riddle statement
The positions in a circle are numbered from 1 to \(n\).
First position 2 is eliminated, then 4, then 6, and so on, continuing in a circular fashion between the positions that are still alive, until only one remains.
Which position survives at the end?
Show solution
Solution
Answer: If $ n = 2^m + \ell, \qquad 0 \le \ell < 2^m. $ then the surviving position is $ 2\ell+1. $
The pattern is already visible in the first few 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 positions is a power of 2, position 1 survives.
Why? On the first pass, every even position is eliminated, so exactly the odd positions remain: $ 1,3,5,\dots $
If these positions are renumbered as \(1,2,3,\dots\), the same problem reappears with half as many positions.
Writing \(n=2^m+\ell\), the complete block \(2^m\) is absorbed by these successive reductions, while the excess \(\ell\) determines how far the survivor shifts from position 1. Therefore the surviving position is \(2\ell+1\).
There is also an equivalent binary rule: write \(n\) in binary, move its leading bit to the end, and read the result as a binary number.