Problem 4 from the second round
of the 17th USAMTS 2005-2006
A teacher plays the game “Duck-Goose-Goose” with his class. The game is played as follows: All the students stand in a circle and the teacher walks around the circle. As he passes each student, he taps the student on the head and declares her a ‘duck’ or a ‘goose’. Any student named a ‘goose’ leaves the circle immediately. Starting with the first student, the teacher tags students in the pattern: duck, goose, goose, duck, goose, goose, etc., and continues around the circle (re-tagging some former ducks as geese) until only one student remains. This remaining student is the winner.
For instance, if there are 8 students, the game proceeds as follows: student 1 (duck), student 2 (goose), student 3 (goose), student 4 (duck), student 5 (goose), student 6 (goose), student 7 (duck), student 8 (goose), student 1 (goose), student 4 (duck), student 7 (goose) and student 4 is the winner. Find, with proof, all values of n with n > 2 such that if the circle starts with n students, then the nth student is the winner.
Credit: This problem was proposed by Mathew Crawford.
Comments: Adam Hesterberg nicely solves the problem by modifying the game slightly to one that has a recursive nature. Solutions edited by Naoki Sato.
Solution by: Adam Hesterberg (11/WA)
We claim that the nth student is the winner if and only if n of the form
Suppose that the game was actually “Goose-Goose-Duck,” and there were two more people at the start of the circle. This game is equivalent to “Duck-Goose-Goose,” since the two new people will be tagged immediately, and the pattern is equivalent to “Duck-Goose-Goose” from there. In the first round, people numbered with multiples of 3 survive, so either the winner is a multiple of 3, or there are only two people left and he is one of them.
In the latter case, the game ends with that round. In the former case, if the winner is a multiple of 3, then the first two people in the next round will be tagged, and the third will live. In general, if the last person survived the
- Josephus Flavius problem
- Two ancient variants
- A simple solution
- A problem from USAMTS
- Partial recursive solution