Author |
Topic: help with a putnam question (Read 4354 times) |
|
sarah9
Newbie
Posts: 1
|
 |
help with a putnam question
« on: Nov 6th, 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 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.
|
|
 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 6th, 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 6th, 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 6th, 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 2m > 1 players, each with 2n-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 2n-m-th loops, at which point there are 2m-1 players each with 2n-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 2n+1 players, then after one loop we'll have 2n-1 players each with 21 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 2n players each with 20 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
2n20 + 2n-121 + 2n-222 + ... + 212n-1 = n*2n.
Of course, one can give a similar argument for the case 2n+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 6th, 2008, 2:24pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print