Problem 4 from the second round
of the 17^th USAMTS 2005-2006

(USAMTS stands for the USA Mathematical Talent Search, a math competition in its 17^th year. Problem 4/2/17.)

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 3^k - 2 or 2·3^k - 2, where k is a positive integer.

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 (k - 1)^st round, then the survivors of the kth round will be the multiples of 3^k. Therefore, for the last person to be the final survivor, he must have the greatest power of 3 as a factor. In case there are two numbers with the same greatest power of 3 as a factor, the lower number gets tagged earlier, so the last person would still win. Therefore, the possible numbers for the last person are 3^k and 2·3^k – greater multiples of 3^k would produce someone with a greater power of 3. Subtract 2 to revert to the original game, getting n = 3^k - 2 or n = 2·3^k - 2.

• Josephus Flavius problem
• Two ancient variants
• A simple solution
• A problem from USAMTS
• Partial recursive solution