Passing Alternate Numbers of Coins Around a Table

Question

I am working on a puzzle which I originally got from Rustan Leino's website (see here: http://leino.science/puzzles/passing-alternating-numbers-of-coins-around/)

The puzzle is as follows:

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.

I have an idea of how to approach this question, although I don't quite have a formal proof. I was hoping I could get some people to chime in and let me know I'm on the right track (without disclosing anything about how to prove this).

My thought is $N$ is terminating iff $N-\left\lfloor\frac{N}{2}\right\rfloor-1$ is a power of $2$ (i.e. $N-\left\lfloor\frac{N}{2}\right\rfloor-1=2^k$ for some $k\in\mathbb{N}_0$).

The informal, not completely developed idea is that, if you view this game as having rounds (where a round ends after everybody who is still in the game has passed on a coin to the person on their left), then, after the first round, every player in an even-numbered position gets kicked out as well as the player in the first position. EDIT: All of these remaining players will have the same number of coins after the first round (that is, if you subtract the pennies the first person in the second round gets from the last player in the first round).

After the first round, if you have an odd number of people remaining (greater than 1), I think the game must go on infinitely. That's because, after the first round, every player that was in an odd-numbered position in round 1 will have at least two pennies and, before it's their turn to pass coins to their neighbour, will receive at least one penny. So no player will get kicked out in the second round. But every player who gave up two pennies in the second round will get two pennies in the third round, meaning after the third round everybody will be in the same position as they were after the first round. So you get a cycle and the game doesn't end.

If you have an even number of people remaining after the first round, each person remaining who gives up two pennies but receives only one penny will on net lose a penny each round. Further, until players are eliminated, the people giving up two pennies but receiving only one penny will be the same each round. Eventually, there will be a round in which all of the players receiving one penny and giving up two pennies will be knocked out. This will halve the number of players. EDIT: I may have missed making this clear, but I want to clarify that I'm pretty sure players will all be knocked out in the same round. In order for the players to be knocked out in different rounds, I think it would have to be the case that there is a round in which these players start off by have a different number of pennies (minus any pennies that might have been transferred over by the last player in the last round). But this shouldn't be the case.

So reasoning like this, if you eventually get a situation where you have an odd number of players (greater than 1) remaining, the game must go on infinitely. But, on the flip side, if after the first round you have a power of 2 number of players remaining, then the game should eventually terminate.

Answer 1

Since you are only asked to show that there are infinitely many $N$ for which the game is terminating, you can focus on just one family of numbers.

Let us try to show that for $N = 2^k + 1$, the game is always terminating.

We may prove the following lemma:

Lemma: Let $m, k$ be positive integers. Suppose that the game starts with $2^k$ players, all having $m$ pennies, except that the first player (the one who gives penny first) has $m + 1$ pennies, then the game is terminating.

The proof can be done by induction on $k$, which I leave you for the details.

Now for $N = 2^k + 1$, we see that after the first pass, it becomes the situation in the lemma with $m = 1$ and hence the game is terminating.