This story is based on the Josephus problem, but that's too gruesome a story to include here!

Who gets the dollars?

Once again, the math teacher has come up with a game. He has agreed with the class that everyone should take one dollar to give to the birthday schoolmate. The problem, however, is that the other students don't know whose birthday it is. Yet the teacher says they will only give the coins to the birthday student. How is that possible?

At first, everyone stands in a circle. The teacher knows sees the birthday student and with that he calculates where he himself should stand near the circle. The students have to give each other dollars according to the rules in the next paragraph.
But first I need to explain what I mean by "second-next-neighbor": the second-next-neighbor is the person who is next to your neighbor in the clockwise direction. So if Anne, Bob and Christiane are standing next to each other in the circle then Christiane is Anne's second-next-neighbor.
The teacher gives the student next to him a dollar. Then the teacher goes to the lunchroom. The student must give the teacher's dollar plus his or her own dollar to his or her second-next-neighbor and then go to the lunchroom. That second-next-neighbor must give three dollars to his or her second-next-neighbor and then go to the lunchroom. This continues until there are only two students left in the classroom. One of them has a lot of dollars. The other one is the birthday student. The student with the dollars gives these to the birthday student and goes to the lunchroom. The birthday student now has all the dollars and goes to the lunchroom for a treat.

But how does the teacher know where to start? It depends on the number of students in the class. He calculates this as follows: from the number of students in the class he makes a binary number. For example, 30 is binary 11110. Then he removes the first 1 and places it after the number, so in this example the binary number becomes 11101. This corresponds to place 29. In his mind, the teacher counts backwards from the birthday student at place 29 to number 2. The student at place 2 will soon receive the first dollar.

Start the the simulation below!

Your browser does not support a canvas. Unfortunately, you cannot play the simulation.
Number of students: .   Show the birthday student