Problem 4

Let

n\ge 3

be an integer. There are

n

cells on a circle, each assigned either 0 or 1, and a rooster occupies one cell. Repeatedly, if the rooster is on a cell assigned 0, it changes that number to 1 and moves to the next cell counterclockwise; if it is on a cell assigned 1, it changes that number to 0 and moves to the cell after next counterclockwise. Prove that after sufficiently many operations, whenever the rooster is on a cell

C

, it goes around the circle exactly three times and stops again at

C

, while every cell has the same number as it had immediately before those three laps.

Step 8 of 8: Conclude the three-lap return

Previous step Next step

3n

Detailed analysis

Summing the contribution of all $n$ cells, the rooster advances a total of $3n$ positions during each later three-lap block. This is exactly three complete circuits, so if it starts that block at a cell $C$ , it stops again at $C$ . By Step 7 every cell has also regained its number, which is precisely the required statement after sufficiently many operations.