wu :: forums
« wu :: forums - help with a putnam question »

Welcome, Guest. Please Login or Register.
Jan 19th, 2022, 12:45pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: towr, Grimbal, Eigenray, Icarus, william wu, SMQ)
   help with a putnam question
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: help with a putnam question  (Read 4083 times)
sarah9
Newbie
*





   


Posts: 1
help with a putnam question  
« on: Nov 6th, 2008, 12:31pm »
Quote Quote Modify 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: male
Posts: 13730
Re: help with a putnam question  
« Reply #1 on: Nov 6th, 2008, 1:18pm »
Quote Quote Modify 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: male
Posts: 1948
Re: help with a putnam question  
« Reply #2 on: Nov 6th, 2008, 2:02pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board