Players $1, 2, 3,\dots, n$ are seated around a table and each has a single penny. Player 1 passes a penny to Player 2, who then passes two pennies to Player 3. Player 3 then passes one penny to Player 4, who passes two pennies to Player 5, and so on, players alternately passing one penny or two to the next player who still has some pennies. A player who runs out of pennies drops out of the game and leaves the table. Find an infinite set of numbers n for which some player ends up with all n pennies.

Just a stupid puzzle I am working on that I cannot figure out how to do?! (for a math competition I am practicing for... not that I will actually get in, but I will have fun trying)

I know that during the first round (e.g. no one's exchanged twice) that 1 and 2 will be eliminated and every even number thereafter will be eliminated, that seems to be quite clear, so perhaps we should look into the cases of an even and odd n? Just pretty much testing things out looking for patterns. Assuming even elimination and length $n = 5$, #5 'wins' and length $n=7$, #3 wins. Probably have to do it further to see any pattern. A better way to approach this? I feel an inductive proof coming on, anyone?

Also, I didn't know what category to put this in... no "just-for-fun" tag or anything?

  • $\begingroup$ As you say, it's a puzzle :-) $\endgroup$ – joriki Apr 2 '11 at 8:05
  • $\begingroup$ No smiley faces, this is serious math business! :) $\endgroup$ – Mr_CryptoPrime Apr 2 '11 at 8:09

Some player ends up with all the money if (and I believe iff, except for the trivial cases $n=1$ and $n=2$) $n=2^k+2$ with $k\in\mathbb{N}_0$. In the first round, as you wrote, the first two players are eliminated. For $k=0$, that leaves only one player. For $k>0$, the even-numbered ones of the remaining players are eliminated in the rest of the first round, and the odd-numbered ones end up with two pennies (not counting the pennies in transit at the end of the round). For $k=1$, that leaves only one player. For $k>1$, from then on, whenever there's an even number of players, they get into a pattern where half of them win and half of them lose until half of them are eliminated. Whenever there's an odd number of players, they don't get into such a pattern, but alternately win and lose. So the game ends with one player left iff the number of players left after the first two players have been eliminated is a power of two.

  • $\begingroup$ this is by no means an easy word problem, it appeared on the collegiate math olympiad called the Putnam !! 1996 I think but dont quote me . i upvote joriki's proof as its ' from the book ' 🤓 $\endgroup$ – Randin Sep 12 '18 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.