MathLabs

第4問

n≥3n\ge 3 を満たす整数 n をとる。円周上に nn 個のマスがあり、それぞれに 0 または 1 が割り当てられ、1 羽の雄鶏がそのうちの 1 マスにいる。雄鶏が 0 のマスにいればその数を 1 に変えて反時計回りの次のマスへ進み、1 のマスにいればその数を 0 に変えて反時計回りに 1 マス飛ばした次のマスへ進む、という操作を繰り返す。十分多く操作した後では、雄鶏がマス CC にいるとき必ず円周をちょうど 3 周して再び CC で止まり、その 3 周の直前と直後で各マスの数が同じであることを証明せよ。
ステップ 1/8: 周回と局所的な訪問を定める
0,1,…,n−1 cyclically; one lap has total advance n0,1,\ldots,n-1\text{ cyclically; one lap has total advance }n
詳しい解説

マスを巡回的に 0,1,…,n−10,1,\ldots,n-1 と番号付けする。雄鶏が円を1周するたびに1周と呼び、その周で雄鶏がそのマスに作用すればそのマスは停止された、そうでなければ通過されたと呼ぶ。1回の移動は1マスまたは2マス進むので、連続する任意の2マスの少なくとも一方では停止する。