MathLabs

第4問

n≥3n\ge 3 を満たす整数 n をとる。円周上に nn 個のマスがあり、それぞれに 0 または 1 が割り当てられ、1 羽の雄鶏がそのうちの 1 マスにいる。雄鶏が 0 のマスにいればその数を 1 に変えて反時計回りの次のマスへ進み、1 のマスにいればその数を 0 に変えて反時計回りに 1 マス飛ばした次のマスへ進む、という操作を繰り返す。十分多く操作した後では、雄鶏がマス CC にいるとき必ず円周をちょうど 3 周して再び CC で止まり、その 3 周の直前と直後で各マスの数が同じであることを証明せよ。
ステップ 3/8: 停止は3周続かない
1010…101010\ldots10
詳しい解説

あるマスが連続する2周で停止されたとする。2回目の停止時にその直前の値を調べる。直前のマスが 0 の場合、または直前の局所パターンが 11 の場合、次の周ではそのマスを通過する。直前が交互な 10 の極大ブロックの場合も、そのブロックを2周追跡すれば同じ結論になる。唯一の例外は交互配置 1010…101010\ldots10 であり、この配置では3周の結論を直接確認できるので、すでに終端周期である。