1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Eventually they have to get knocked out. This is only half-correct, because "they" may not be knocked out in the same round. After one person gets knocked out, the number of players becomes odd. $\endgroup$
    – WhatsUp
    Jul 4, 2021 at 14:49
  • $\begingroup$ In the case of $8$ players, after first round, there are $4$ players, each with $2$ pennies. But the game is non-terminating. $\endgroup$
    – WhatsUp
    Jul 4, 2021 at 20:02
  • $\begingroup$ No, in the case of 8 players, after the first round there are 3 players! Player 1 gets knocked out, player 2 gets knocked out, player 4 gets knocked out, player 6 gets knocked out, player 8 gets knocked out. No? $\endgroup$ Jul 4, 2021 at 20:06
  • $\begingroup$ This depends on your definition of "first round". This is basically the problem of your "intuitive proof", namely you didn't state everything rigorously. Mathematical proofs need to be written concisely so that the correctness is obvious. $\endgroup$
    – WhatsUp
    Jul 4, 2021 at 20:08
  • $\begingroup$ @WhatsUp Well, I noted it wasn't a rigorous proof from the outset and that it was just an idea about how to proceed... I don't see why this depends on my definition of first round by the way? Can you explain further why you think I'm off? $\endgroup$ Jul 4, 2021 at 20:09

1 Answer 1

-2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Hmmm, it seems to me this solution is actually the same as mine! The lemma you're using would work for my proposed solution, too, and (unless I'm mistaken) the induction argument essentially formalizes my intuition about how the game should work. Would you agree with this? $\endgroup$ Jul 4, 2021 at 19:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .