Putnam 1997 Problem A2 Players 1, 2, ... , n are seated in a circle. Each has one penny. Starting with player 1 passing one penny to player 2, players alternately pass one or two pennies to the next player still seated. A player leaves as soon as he runs out of pennies. So player 1 leaves after move 1, and player 2 leaves after move 2. Find an infinite set of numbers n for which some player ends up with all n pennies. Solution
: for 2 n + 1 or 2 n + 2 players (where n ≥ 0) one player ends up with all the coins. In all other cases the game does not terminate. Tough. We give a complete solution for the game, although to solve the problem one need only consider one of the cases 2 n + 1 or 2 n + 2. It is convenient to deal separately with odd and even numbers of players. Suppose first that the number is even, so we may write it as 2 m (2r + 1) + 2, where m ≥ 1 and r ≥ 0. Call a round a set of moves in which each remaining player plays once, starting with the lowest numbered remaining player (the low player ). Thus the first round always leaves the (new) low player with 3 or 4 coins and the other remaining players with 2 each. Call an eliminating round a round in which one or more players drop out. The kth eliminating round, for k ≤ m, leaves 2 m-k (2r + 1) players, the low player with 2 k + 2 coins, and the others with 2 k each, and the low player about to pass 1 coin. This is an easy induction. It is easily verified for k = 1. Assume it is true for k-1. The number of players is even, so until the next elimination any given player always passes and receives the same number of coins each round. The players in even positions receive 1 coin and pass 2, so they lose 1 coin in each round. They are thus all eliminated together after 2 k rounds. Similarly, the players in odd positions (including the low player) gain a coin each round, a total gain of 2 k . This establishes the result for k. So after m eliminating rounds there are (2r + 1) players, the low player with 2 m + 2 coins, the others with 2 m each, and the low player about to pass 1 coin. Of course, if r = 0, then a single player has all the coins. If not, then we show that play continues indefinitely. After the next round the sequence of coins is 2 m + 2, 2 m - 1, 2 m + 1, 2 m - 1, ... , 2 m + 1, and the low player is about to pass 1. After the next round the situation is just as it was after the mth eliminating round, so the game now cycles indefinitely. For an odd number of players, it is more convenient to regard the round as ending one play earlier with the highest numbered remaining player (the high player ) about to play. Thus in the first round the high player does not play. In subsequent rounds each player plays once. We can write the initial number of players as 2 m (2r + 1) + 1, with m ≥ 1 and r ≥ 0. Arguing as before, the kth eliminating round for k ≤ m leaves 2 m-k (2r + 1) players, the high player with 2 k + 1 coins and about to pass 1, and the others with 2 k each. So after the mth eliminating round, there are (2r + 1) players, the high player with 2 m + 1, the others with 2 m each. Again if r = 0, then one player has all the coins and the game terminates. If not, then after the next round the sequence of coins is 2 m - 1, 2 m + 1, 2 m - 1, ... , 2 m + 1, 2 m + 1, with the high player about to pass 2. After the next round the situtation is just as it was after the mth eliminating round, so the game now cycles indefinitely. Putnam 1997 © John Scholes jscholes@kalva.demon.co.uk 12 Dec 1998