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 の少なくとも一方は、ある時点から周期的になることを証明せよ。
ステップ 5/6: 小さな項に対する有限状態記述
前のステップ次のステップ
ざっくり言うと

無限に成長する L 個の塔の間の相対的な高さだけが、二段階後の次の小さな項を予測するうえで重要であり、ステップ2の評価はこれらの相対的な高さを有限個の可能性に限定する。

T(n)=(h1−h2,…,hL−1−hL,an)T(n)=(h_1-h_2,\ldots,h_{L-1}-h_L,a_n)
詳しい解説

n≡N′(mod2)n\equiv N'\pmod2 のとき、BnB_n の後の高さを用いて T(n)=(h1−h2,h2−h3,…,hL−1−hL,an)T(n)=(h_1-h_2,h_2-h_3,\ldots,h_{L-1}-h_L,a_n) と定める。二段階の遷移を明記する。q=hanq=h_{a_n} とおく。ステップ4より q=an+1>Mq=a_{n+1}>M である。次のブロックは塔 qq に置かれる。ラベルが MM より大きい全ての塔の高さは MM 以下なので、この配置の後の次の小さい項は an+2=#{i:hi≥q}a_{n+2}=\#\{i:h_i\ge q\} であり、寄与できるのは i=1,…,Li=1,\ldots,L だけである。この個数は相対的な高さだけで決まる。なぜなら qq は h1,…,hLh_1,\ldots,h_L のいずれかだからである。そして Bn+2B_{n+2} は塔 an+2a_{n+2} の高さを1増すので、全ての隣接差と最後の座標は T(n)T(n) から決定される。状態が有限個であることを示すため、ステップ2より hk+1≤hk+Ch_{k+1}\le h_k+C である。また k<Lk<L に対して hk≤hk+1+C(L−1)h_k\le h_{k+1}+C(L-1) を示す。これが塔 kk の更新直後に破れたなら hk>hk+1+C(L−1)h_k>h_{k+1}+C(L-1) である。hj≥hj+1−Ch_j\ge h_{j+1}-C を繰り返し使うと、h1,…,hkh_1,\ldots,h_k の全てが hk+1,…,hLh_{k+1},\ldots,h_L の全てより大きい。q=hkq=h_k とおけば、高さが少なくとも qq の塔はちょうど最初の kk 個なので、次の小さい項は kk となり、同じ二段階遷移によって塔 kk が永遠に更新される。これは塔 k+1,…,Lk+1,\ldots,L を有界にしてしまい、それらの定義に矛盾する。従って隣接差は全て固定された有限区間に入り、an∈{1,…,L}a_n\in\{1,\ldots,L\} でもあるから、状態 T(n)T(n) は有限個しかない。