2025 APMO 第 4 题

Let $n \geq 3$ be an integer. There are $n$ cells on a circle, and each cell is assigned either 0 or 1. There is a rooster on one of these cells, and it repeats the following operations:

If the rooster is on a cell assigned 0, it changes the assigned number to 1 and moves to the next cell counterclockwise. If the rooster is on a cell assigned 1, it changes the assigned number to 0 and moves to the cell after the next cell counterclockwise.

Prove that the following statement holds true after sufficiently many operations:

If the rooster is on a cell $C$ , then the rooster would go around the circle exactly three times, stopping again at $C$ . Moreover, every cell would be assigned the same number as it was assigned right before the rooster went around the circle 3 times.

设 $n \geq 3$ 为整数。一个圆上有 $n$ 个单元格，每个单元格分配为 0 或 1。其中一个单元格上有一只公鸡，它重复以下操作：

如果公鸡位于分配为 0 的单元格上，它会将分配的数字更改为 1 并逆时针移动到下一个单元格。如果公鸡位于分配为 1 的单元格上，它会将分配的数字更改为 0 并逆时针移动到下一个单元格之后的单元格。

经过足够多的操作后证明以下陈述成立：

如果公鸡位于 $C$ 单元格上，那么公鸡将恰好绕圈三圈，再次停在 $C$ 处。此外，每个单元格都会分配与公鸡绕圈 3 圈之前分配的编号相同的编号。