wu :: forums « wu :: forums - help with a putnam question » Welcome, Guest. Please Login or Register. Apr 20th, 2024, 4:15am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Grimbal, Icarus, towr, Eigenray, SMQ, william wu)    help with a putnam question « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: help with a putnam question  (Read 4248 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »