Problem #2

A number of students stand in a circle. Beginning with student #1 and going clockwise around the circle (student #2, student #3, student #4, etc.), the students count off 1,2,3,1,2,3,1,2,3,... The students who say "2" or "3" leave the circle immediately. When the count gets back to student #1, it continues to follow the same pattern (but only with the students who remain). The last student remaining wins a prize.

For example, if there are 14 students, the first round would proceed as follows

student # 1 2 3 4 5 6 7 8 9 10 11 12 13 14

count 1 2 3 1 2 3 1 2 3 1 2 3 1 2

and only students #1, #4, #7, #10, and #13 would be around for the second round. Since student #14 had said "2", student #1 will say "3" (and be eliminated). Round two will proceed as follows

student # 1 4 7 10 13

count 3 1 2 3 1

and hence students #4 and #13 will survive to the third round. Since student #13 said "1", student #4 must say "2" and be eliminated, leaving student #13 as the winner.

This month's problem is to determine the winner if there are 2004 students.

Source: Vietnamese Olympiad in Mathematics