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

(USAMTS stands for the USA Mathematical Talent Search, a math competition in its 17th 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.