Author 
Topic: help with a putnam question (Read 4248 times) 

sarah9
Newbie
Posts: 1


help with a putnam question
« on: Nov 6^{th}, 2008, 12:31pm » 
Quote Modify

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 A2 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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: help with a putnam question
« Reply #1 on: Nov 6^{th}, 2008, 1:18pm » 
Quote Modify

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. 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) And of course the real trick is to prove this sequence works (rather than just up to the point you've examined).

« Last Edit: Nov 6^{th}, 2008, 1:19pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: help with a putnam question
« Reply #2 on: Nov 6^{th}, 2008, 2:02pm » 
Quote Modify

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^{nm} coins, not counting the 1 coin that player 0, say, is currently passing. After one loop around the table, players 1,3,... get +12 = 1 coins, and players 2,4,...,0 get +21 = +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^{nm}th loops, at which point there are 2^{m1} players each with 2^{nm+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^{n}+1 players, then after one loop we'll have 2^{n1} players each with 2^{1} 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^{n} players each with 2^{0} 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^{n}2^{0} + 2^{n1}2^{1} + 2^{n2}2^{2} + ... + 2^{1}2^{n1} = n*2^{n}. Of course, one can give a similar argument for the case 2^{n}+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 here.

« Last Edit: Nov 6^{th}, 2008, 2:24pm by Eigenray » 
IP Logged 



