Putnam 1997, Problem A-2

Players $1,2,3,\ldots,n$ are seated around a table, and each has a single penny. Player $1$ passes a penny to player $2$, who then passes two pennies to player $3$. Player $3$ then passes one penny to Player $4$, who passes two pennies to Player $5$, and so on, players alternately passing one penny or two to the next player who still has some pennies. A player who runs out of pennies drops out of the game and leaves the table. Find an infinite set of numbers $n$ for which some player ends up with all $n$ pennies.

Solution:
We show more precisely that the game terminates with one player holding all of the pennies if and only if \( n = 2^m + 1 \) or \( n = 2^m + 2 \) for some \( m \). First suppose we are in the following situation for some \( k \geq 2 \). (Note: for us, a "move" consists of two turns, starting with a one-penny pass.)  
- Except for the player to move, each player has \( k \) pennies;  
- The player to move has at least \( k \) pennies.  

We claim then that the game terminates if and only if the number of players is a power of 2. First suppose the number of players is even; then after \( m \) complete rounds, every other player, starting with the player who moved first, will have \( m \) more pennies than initially, and the others will all have 0. Thus we are reduced to the situation with half as many players; by this process, we eventually reduce to the case where the number of players is odd. However, if there is more than one player, after two complete rounds everyone has as many pennies as they did before (here we need \( m \geq 2 \)), so the game fails to terminate. This verifies the claim.  

Returning to the original game, note that after one complete round, \( \lfloor \frac{n-1}{2} \rfloor \) players remain, each with 2 pennies except for the player to move, who has either 3 or 4 pennies. Thus by the above argument, the game terminates if and only if \( \lfloor \frac{n-1}{2} \rfloor \) is a power of 2, that is, if and only if \( n = 2^m + 1 \) or \( n = 2^m + 2 \) for some \( m \).