第4题

设

n\ge 3

为整数。圆周上有

n

个格子，每个格子赋值为 0 或 1，一只公鸡位于其中一个格子。反复进行如下操作：若公鸡位于赋值 0 的格子，就把该数改为 1，并逆时针移动到下一个格子；若公鸡位于赋值 1 的格子，就把该数改为 0，并逆时针跳过一个格子移动到下下个格子。证明经过充分多次操作后，每当公鸡位于格子

C

，它恰好绕圆周三周并再次停在

C

，且每个格子的数都与这三周开始之前的数相同。

第 4/8 步：找到初始三圈模式

j

详细分析

由于位置只有有限多个，某个位置 $j$ 必在无穷多圈中被停止。每次公鸡在 $j$ 停止时，局部转移都会改变它在下一位置停止还是跳过的情况。因此下一位置会无穷多次停止、也会无穷多次被跳过。选取一圈中它停止而下一圈被跳过；由前面的规则，后下一圈它又会停止。于是某个位置在连续三圈中有两次停止、一次跳过。