MathLabs

第4問

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

位置 jj が連続3周で2回停止され1回通過されるなら、位置 j+1j+1 も同じ性質を持つ(3周を巡回的にずらしてよい)。実際、jj が通過されると雄鶏は必ず j+1j+1 で停止する。jj で停止する2周では作用前の jj の値が2回で異なるので、j+1j+1 では一方で停止し、他方で通過する。これで伝播が示された。