Passing Alternating Numbers of Coins


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.


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 their pennies (at this time, they happen to have exactly one penny) and passes it to the person to their 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, they're out of the game and must 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 are an infinite number of player counts for which the game is terminating.

Solution     Reveal