MathLabs

第3問

正の整数からなる無限数列 a1,a2,a3,…a_1,a_2,a_3,\ldots と正の整数 NN を考える。各 n>Nn>N に対して、ana_n はリスト (a1,a2,…,an−1)(a_1,a_2,\ldots,a_{n-1}) の中に an−1a_{n-1} が現れる回数に等しいとする。数列 a1,a3,a5,…a_1,a_3,a_5,\ldots と a2,a4,a6,…a_2,a_4,a_6,\ldots の少なくとも一方は、ある時点から周期的になることを証明せよ。
ステップ 2/6: 隣接する塔は離れすぎない
前のステップ次のステップ
ざっくり言うと

塔 k+1 が過程から新しいブロックを受け取るたびに、その出来事は短い単射的な連鎖をたどって塔 k の対応する新しいブロックまで追跡できるので、塔 k が塔 k+1 より大きく遅れることは決してない。

hk≥hk+1−Ch_k\ge h_{k+1}-C
詳しい解説

BiB_i を aia_i に対応するブロックとし、その塔のラベルを aia_i とする。i>Ni>N では定義より BiB_i の高さは ai+1a_{i+1} である。これは ai+1a_{i+1} がラベル aia_i のそれまでの出現回数を数えるからである。kk を固定する。BnB_n が塔 k+1k+1 の黄色いブロックなら、an=k+1a_n=k+1 なので、Bn−1B_{n-1} はその塔の高さ k+1k+1 のブロックである。最初の赤いブロックに関係する有限個を除けば、Bn−1B_{n-1} の直下のブロックも黄色である。これを BrB_r と書くと、その高さは kk だから規則より ar+1=ka_{r+1}=k、したがって Br+1B_{r+1} は塔 kk にある。ゆえに有限個の例外を除き、塔 k+1k+1 の各黄色ブロック BnB_n をこの Br+1B_{r+1} に対応させる。この対応は単射である。異なる BnB_n は異なる Bn−1B_{n-1} を与え、それらの直下のブロックも異なり、したがって後続ブロックも異なるからである。よって任意の時点で、塔 k+1k+1 の黄色ブロック数は塔 kk のブロック数に固定された例外数を加えたもの以下である。有限個の赤いブロックを、NN と MM だけに依存する定数 CC に吸収すれば hk≥hk+1−Ch_k\ge h_{k+1}-C を得る。特に、ある塔が無限に伸びれば、その直ちに左の塔も無限に伸びる。