Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Players 1, 2, 3, …, 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? :)

share|improve this question
    
As you say, it's a puzzle :-) –  joriki Apr 2 '11 at 8:05
    
No smiley faces, this is serious math business! :) –  Mr_CryptoPrime Apr 2 '11 at 8:09

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
ah, I think I can take it from here, thanks! double smiley:)) –  Mr_CryptoPrime Apr 2 '11 at 8:18
    
you're welcome :-)) –  joriki Apr 2 '11 at 8:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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