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 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