The following problem appeared in the 58th Putnam Competition, 1997. Problem: Th
ID: 3283446 • Letter: T
Question
The following problem appeared in the 58th Putnam Competition, 1997. Problem: There are n people sitting on a circular table (n > 1). Each one of them has a penny, and they start playing the following game the person sitting to their right, who gives one penny to the person sitting to their right and so on, always alternating between giving one or two pennies to the person sitting to their right. The moment a person gets out of pennies, they are out of the game and leave the table. The game ends when one of the players gets all the pennies. If this does not happen, then the game never ends. a) Show that there erists a natural number n >1 such that the game never ends b) Show that there erists an infinite number of values of n such that the game ends.Explanation / Answer
(a) If we assume n=7, then the game never ends.
(To understand this explanation easily, draw a circle with the entries p1 to p7 and carry the procedure simultaneously when reading it.)
For this, we choose a person among them at random and name him p1. Starting from his right we call each player as p2, p3,.. p7. Now p1 gives 1 penny to p2 and goes out of pennies and leaves the table. p2 gives 2 pennies to p3 and leaves too. p3 now has 3 pennies out of which he gives 1 to p4 and is left with 2. p4 gives 2 pennies to p5 and goes out of the game. p5 now has 3 pennies and is left with 2 pennies after giving 1 to p6. p6 gives all he has to p7 and leaves the game. p7 now has 3 pennies. Now we are left with only 3 players viz. p3, p5 and p7 with 2, 2 and 3 pennies respectively. p7 gives 1 penny to p3 and is left with 2 pennies. p3 gives 2 pennies to p5 and is left with 1 penny. p5 gives 1 penny to p7 and is left with 3. p7 then gives 2 pennies to p3 and is left with 1. p3 gives 1 penny to p5 and is left with 2 pennies. p5 gives 2 pennies to p7 and is left with 2. p7 has now 3 pennies (and he has to give 1 penny forward) and we are stuck in a loop. When we keep on doing this process, this stage of 2-2-3 pennies (such that the one with 3 pennies has to give 1 penny to the next player) is repeated again and again and hence the game never ends. Hence, there exists natural number n=7 such that the game never ends.
(b) This game will end for every n=2k (for natural number k) of players. to see this, consider that there are 2 people playing the game. Then the person who gives 1 penny to the other and goes out of pennies and the other player wins and the game ends. This happens for 4 people as well. And for
Observe that this happens because half of the people recieve 1 penny and give all of the 2 pennies they have and 2 people get out of the game and the starting, resulting in 2k-1+2 of them leaving the table. The number of people that are still on the table are 2(k-1)-2. After this, people will get out of the game in pairs per whole circle and hence, This process goes on and eventually at last, 2 people will remain on the table. Among these two, one will always recieve 2 pennies and give 1 penny and the other will always recieve 1 penny and give 2 pennies, resulting in the win of the first player. So the game ends whenever number of people is power of 2. Hence, There exist infinite number of values of n such that the game ends.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.