MathLabs

第4問

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

第4段階で得た位置から出発し、第5段階を円周に沿って繰り返し適用すると、十分後にはすべての位置が共通の連続3周で 2 stops and 1 bypass2\text{ stops and }1\text{ bypass} のパターンを持つ。連続通過禁止の規則により、このパターンは次の周にも続く。古いブロックの通過の次は停止であり、2回の停止が残りの項を決めるからである。帰納法により、以後のすべての3周ブロックとすべてのマスでこのパターンが成り立つ。