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 の少なくとも一方は、ある時点から周期的になることを証明せよ。
ステップ 4/6: 最終的な小さい項と大きい項の交替
前のステップ次のステップ
ざっくり言うと

適当な時点を過ぎると、まだ成長しているのは L 個の無限に成長する塔だけになるので、過程はこれらの小さな塔のどれかに落ちることと、常に変化するある大きな塔に落ちることとの間で厳密に交互になる。

aN′,aN′+2,…≤L,aN′+1,aN′+3,…>Ma_{N'},a_{N'+2},\ldots\le L,\qquad a_{N'+1},a_{N'+3},\ldots>M
詳しい解説

前の主張から、ラベルが MM より大きい塔の高さは全て MM 以下である。そのような塔がブロックを受け取ると新しい高さは次の項になるので、高さが MM を超えれば MM より大きい項が二つ連続してしまうからである。N′>NN'>N を、有限塔 L+1,…,ML+1,\ldots,M がそれ以上ブロックを受け取らず、塔 1,…,L1,\ldots,L の高さが max⁡(M,N)\max(M,N) を超えた後で、かつ aN′≤La_{N'}\le L となるように取る。このような添字は、小さい項が無限回現れ、有限塔の小さいラベルは有限回しか現れないので存在する。このとき aN′a_{N'} は成長する塔のラベルだから aN′+1=haN′(N′)>Ma_{N'+1}=h_{a_{N'}}(N')>M である。ステップ3より aN′+2≤Ma_{N'+2}\le M であり、1,…,M1,\ldots,M のうち以後ブロックを受け取れるのは 1,…,L1,\ldots,L だけなので aN′+2≤La_{N'+2}\le L となる。同じ議論を繰り返せば aN′,aN′+2,aN′+4,…≤La_{N'},a_{N'+2},a_{N'+4},\ldots\le L かつ aN′+1,aN′+3,aN′+5,…>Ma_{N'+1},a_{N'+3},a_{N'+5},\ldots>M を得る。