wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> help with a putnam question
        
(Message started by: sarah9 on Nov 6^th, 2008, 12:31pm)

Title: help with a putnam question
Post by sarah9 on Nov 6^th, 2008, 12:31pm

Can someone please help me solve this question? I'm not a math genius by any means so a step by step easy to understand solution would be most helpful. I'm trying to get in the swing of working out these questions and this one seems to be at the easy end of the spectrum. Thanks!

It is question A-2 from the 1997 exam

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.

Title: Re: help with a putnam question
Post by towr on Nov 6^th, 2008, 1:18pm

The first thing I'd do would be to find the first few games, and see which end. After a while a pattern becomes blindingly obvious.
On the other hand, it's a lot of work if you can't get a computer to do it for you.

[hide]
n, #steps
1, 0
2, 1
3, 2
4, 4
5, 8
6, 10
9, 24
10, 26
17, 64
18, 66
33, 160
34, 162
65, 384
66, 386
129, 896
130, 898
257, 2048
258, 2050
513, 4608
514, 4610

powers of 2 plus 1 or 2 (if we disregard case n=1)
[/hide]

And of course the real trick is to prove this sequence works (rather than just up to the point you've examined).

Title: Re: help with a putnam question
Post by Eigenray on Nov 6^th, 2008, 2:02pm

Of course, on the Putnam, you'll only have time to compute the first few n for which the game ends, but it makes sense to think about powers of 2, due to the alternating nature of the game. To see what's going on, here are some intermediate steps for the case n=17:
11111111111111111
22222222
13131313
4444
3535
...
88
...
16

The underlined number means that that player is currently passing 1 coin to the next player.

So, suppose at some stage there are 2^m > 1 players, each with 2^n-m coins, not counting the 1 coin that player 0, say, is currently passing. After one loop around the table, players 1,3,... get +1-2 = -1 coins, and players 2,4,...,0 get +2-1 = +1 coins. Since the number of players is even, in each loop the even players gain and the odd players lose. This continues until the odd players all run out of coins on the 2^n-m-th loops, at which point there are 2^m-1 players each with 2^n-m+1 coins. So eventually we're down to one person, and the game ends.

Now it remains to see that if we start with 2ⁿ+1 players, then after one loop we'll have 2^n-1 players each with 2¹ coins, with the last player passing 1 coin. Or, to make it more uniform, we can imagine that the starting player doesn't really exist: that is, consider 2ⁿ players each with 2⁰ coins, not counting the 1 coin that the last player is passing to the second player directly, because this is effectively the same as the first player passing 1 coin to the second player and then leaving. Moreover, we can see that the number of turns required is
2ⁿ2⁰ + 2^n-12¹ + 2^n-22² + ... + 2¹2^n-1 = n*2ⁿ.

Of course, one can give a similar argument for the case 2ⁿ+2 players, but this isn't necessary for the problem as stated. The hard part would be showing that if the number of players isn't 1 or 2 more than a power of 2, the game never ends.

Edit: By the way, solutions to the last 13 Putnams can be found [link=http://www.unl.edu/amc/a-activities/a7-problems/putnamindex.shtml]here[/link].