Source

I got this problem from Rustan Leino, who found it as a sample question on the web page for the Putnam exam.

I solved it and wrote up my solution.

Problem

A game is played as follows. $N$ people are sitting around a table, each with one penny. One person begins the game, takes one of his pennies (at this time, he happens to have exactly one penny) and passes it to the person to his left. That second person then takes two pennies and passes them to the next person on the left. The third person passes one penny, the fourth passes two, and so on, alternating passing one and two pennies to the next person. Whenever a person runs out of pennies, he is out of the game and has to leave the table. The game then continues with the remaining people.

A game is *terminating* if and only if it ends with just one person
sitting at the table (holding all $N$ pennies). Show that there exists an
infinite set of numbers for which the game is terminating.

Solution
Reveal

We will show that, for any non-negative integer $n$, the game is terminating when $N = 2^n + 2.$ For this, the following lemma will be useful.

**Lemma.** Suppose there exists a non-negative integer $n$ such that
the number of players remaining is $2^n$ and an even number of passes have
occurred so far. Assign the players the numbers $1$ through $2^n$ in the
order they will pass, starting with the next player who will pass. Suppose
further that player $1$ has at least two pennies, the other odd players all
have the same number of pennies $p_o$, and the even players all have the same
number of pennies $p_e.$ Then, the game is terminating.

*Proof.* We prove this by induction on $n$. Clearly, if $n = 0$, then
the game is terminating because it already has terminated: there's only one
player left. So, for the inductive step, we show it holds for $n = k > 0$
assuming it holds for $n = k - 1$. We perform this proof by nested
induction, this time on $p_e$.

As the inner-induction base case, we use $p_e = 1$. After all, the number $p_e$ must be positive, because players still in the game must have a positive number of pennies left. Consider what will happen over the course of the next $2^k$ passes, one by each currently remaining player. The first player will pass one of her pennies, but stay in the game because she started with at least two. Each even player will, before her pass, receive one penny, giving her $p_e + 1 = 2$ pennies; then, she will pass those two pennies away, leaving the game. Each odd player besides $1$ will, before her pass, receive two pennies, giving her $p_o + 2$ pennies, then pass one of them away, leaving her with $p_o + 1$ pennies. Eventually, the first player will receive two pennies from the player on her right, bringing her penny count to at least three. We thus wind up in a situation where there are $2^{k-1}$ players remaining, an even number of passes have occurred, the current player has at least three pennies, and the remaining players all have $p_o + 1$ pennies. Thus, we can apply the outer inductive hypothesis using $n \mapsto k-1$, $p_e \mapsto p_o + 1$, and $p_o \mapsto p_o + 1$, to see that the game is terminating.

For the inner-induction inductive step, we prove it holds for $p_e = P > 1$ assuming it holds for $p_e = P - 1.$ Consider what will happen over the course of the next $2^k$ passes, one by each currently remaining player. The first player will pass one of her pennies, but stay in the game because she started with at least two. Each even player will, before her pass, receive one penny, giving her $P + 1$ pennies; then, she will pass those two pennies away, leaving her with $P - 1$ pennies. Each odd player besides $1$ will, before her pass, receive two pennies, giving her $p_o + 2$ pennies, then pass one of them away, leaving her with $p_o + 1$ pennies. Eventually, the first player will receive two pennies from the player on her right, bringing her penny count to at least three. We thus wind up in a situation where there are $2^k$ players remaining, an even number of passes have occurred, the current player has at least three pennies, the remaining odd players all have $p_o + 1$ pennies, and the remaining even players all have $P - 1$ pennies. Thus, we can apply the inner inductive hypothesis using $p_e \mapsto P - 1$ and $p_o \mapsto p_o + 1$ to see that the game is terminating.

This concludes the inner induction, which concludes the outer induction and thus the proof. $\Box$

When $N = 2^n + 2$, during the first two turns the first two players are eliminated. Thus, there are $2^n$ players left, the next player to pass has three pennies, and the rest have one penny each. We can apply the lemma above with $p_o = 1$ and $p_e = 1$ to conclude that the game is terminating. Since there are an infinite number of non-negative integers $n$, there are an infinite number of values $N = 2^n + 2$ for which the game is terminating.