Counting Around the Circle

Number people 1 to $n$ around a circle. Start counting at person 1. Every $k$th person leaves the circle, and the count carries straight on from where it stopped, skipping anybody who has already gone. Eventually one person is left.

With five people counting to two, the count reaches 1 and 2, so 2 leaves. It reaches 3 and 4, so 4 leaves. It reaches 5 and then wraps round to 1, so 1 leaves. It reaches 3 and 5, so 5 leaves. Person 3 is the survivor.

The question is not what happens, which is only bookkeeping. It is whether you can say who survives without doing the bookkeeping - and for $k=2$ you can, in one line, for any circle at all.

Watch one lap of the circle at $k=2$. Everybody in an even position leaves, and everybody in an odd position is still standing. That is the entire first lap, and it has halved the problem.

Now the useful case. Suppose there are exactly $8$ people. After one lap, 2, 4, 6 and 8 have gone, four people remain, and the count is about to reach person 1 again - exactly as it did at the very start, with a circle that is again a power of two. So the same thing happens on the next lap, and the next, and person 1 is untouchable. Try 2, 4, 16 or 32 in the laboratory and person 1 wins every time.

That is the pivot. If a circle whose size is a power of two always leaves the person the count started on, then any other circle only has to be reduced to one, and reducing it means removing enough people to bring the count round to a fresh start on a power-of-two circle. How many is "enough"? Exactly the remainder above the previous power of two.

Write the circle size as

which is just "the largest power of two that fits, plus what is left over". Then, counting to two, the survivor is $2\ell +1$.

Here is what makes that worth a page rather than a footnote. In binary, $2^m$ is the leading 1 of $n$, and $\ell$ is every digit after it. Doubling $\ell$ shifts those digits one place to the left, and adding one puts a 1 in the units place. So:

Take the binary digits of $n$, move the leading 1 from the front to the back, and read the result. That is where to stand.

Forty-one is $101001$. Moving the leading 1 gives $010011$, which is 19. A hundred is $1100100$, which becomes $1001001$, or 73. A power of two is a 1 followed by zeroes, so it becomes zeroes followed by a 1: person 1, every time, and only for those sizes.

None of this survives a change of count. At $k=3$ the rotation gives 19 for a circle of 41 and the survivor is 31, and it is wrong for most sizes below 64. The laboratory therefore withdraws the binary view at other counts instead of drawing a rule that does not apply there.

Let $J(n,k)$ be the label of the survivor in a circle of $n$ people, counting from person 1 and removing every $k$th.

1. $J(1,k)=1$ and $J(n,k)=((J(n-1,k)+k-1)\mathrm{mod}n)+1$ for $n\ge 2$. Proved, for every $k\ge 1$.
2. If $n=2^m+\ell$ with $0\le \ell <2^m$, then $J(n,2)=2\ell +1$. Proved.
3. $J(n,2)$ is the binary representation of $n$ rotated left by one place. Proved, and equivalent to 2.
4. $J(n,2)=1$ if and only if $n$ is a power of two. Proved, and immediate from 2.

Statement 1 is the only one that mentions $k$ at all, and that is the honest summary of this page: the general problem has a recurrence, and the reading has a rule only at $k=2$.

The recurrence. In a circle of $n$, the first count removes person $k$. What is left is a circle of $n-1$ people, and the next count begins at person $k+1$. That is the same problem with a different set of labels, so if the smaller circle's survivor sits at offset $J(n-1,k)-1$ from its own starting person, the original circle's survivor sits at offset $J(n-1,k)-1+k$ from person 1, counted round. Reducing modulo $n$ and returning to 1-based labels gives the stated formula. ∎

A power-of-two circle leaves the person the count starts on. Induction on $m$. For $m=0$ there is one person and nothing to do. For $m>0$, one lap of a circle of $2^m$ removes every person in an even position, which is exactly half of them, and returns the count to the person it began with, now standing in a circle of $2^{m-1}$. By induction that person survives. ∎

The closed form. Let $n=2^m+\ell$ with $0\le \ell <2^m$. Beginning at person 1 and counting to two, the first $\ell$ departures are persons $2,4,\dots ,2\ell$, after which $2^m$ people remain and the next count begins at person $2\ell +1$. By the previous paragraph that person survives, so $J(n,2)=2\ell +1$. ∎

The rotation. The binary representation of $n=2^m+\ell$ is a 1 followed by the $m$ binary digits of $\ell$, padded with leading zeroes. Deleting that leading 1 leaves those $m$ digits, which read as $\ell$; appending a 1 on the right produces $2\ell +1$. So rotating the leading bit to the end computes exactly the closed form. ∎

And person 1. $2\ell +1=1$ exactly when $\ell =0$, exactly when $n=2^m$. ∎

What is not proved. Nothing above says anything about $k=3$. The pivot was that one lap at $k=2$ removes precisely half the circle and lands the count back at a starting position, and no part of that survives when a third of the circle goes each lap and the leftover does not divide the way it needs to.

What this laboratory computes. The circle is simulated person by person up to 200 of them, which is where numbered discs stop being distinguishable rather than where the arithmetic stops being exact. Above that the survivor still comes from the recurrence, which is linear in $n$ and holds up to a million, and the page says it has stopped drawing rather than pretending the picture is there.

The proof was about counting to two, and it does not transfer. This is the part worth carrying away. The argument in layer 5 is complete and elementary, and it is also extremely specific: it turns on a lap at $k=2$ deleting exactly the even positions. Change the count to three and the survivor is still perfectly computable, one departure at a time, and this page can offer no rule for reading it off. That is a statement about what this page establishes. A description of the $k=3$ case does exist in the literature, and it is nothing like moving a bit; the difference in difficulty between the two questions is not visible anywhere in how they are stated.

Read this next to Reverse, Add, and 196. Both rules are one sentence long and both can be run by a child with counters. One of them has an answer you can read off a number's binary digits; the other has swallowed a billion digits of computation without anybody being able to say anything at all. From the outside there is no way to tell which kind of rule you are looking at, and finding out is the entire work.