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 5 of 8: Propagate the pattern to the next cell

Previous step Next step

j+1

Detailed analysis

If position $j$ has two stops and one bypass in three consecutive laps, then position $j+1$ has the same property (possibly with the three laps cyclically shifted). Indeed, when $j$ is bypassed, the rooster must stop at $j+1$ ; in the two laps where it stops at $j$ , the value at $j$ before the action is different on the two visits, so the rooster stops at $j+1$ on one and bypasses it on the other. This proves the propagation claim.