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 の少なくとも一方は、ある時点から周期的になることを証明せよ。
ステップ 3/6: 二つの大きな項が連続することはあり得ない
前のステップ次のステップ
ざっくり言うと

ある項が、最初の N 個の塔のどれよりもすでに高い塔に置かれたとすると、その高くて全て新しいブロックからなる塔をたどることで、それ以前にすでに M より多くの高い塔が存在していたことになり、これが初めて起こる時点で矛盾となる。

an>M  ⟹  an+1≤Ma_n>M\implies a_{n+1}\le M
詳しい解説

初めて an>Ma_n>M かつ an+1>Ma_{n+1}>M となる時点を考える。ブロック BnB_n はラベル an>Ma_n>M の塔にあり、これを置いた後のその塔の高さは an+1>Ma_{n+1}>M なので、MM 個より多くの黄色いブロックを含む。その各 BrB_r の直前の Br−1B_{r-1} は、自分の塔の高さ an>Ma_n>M の位置に置かれている。これは、ブロック Br−1B_{r-1} の配置後の塔の高さが ana_n だからである。異なる BrB_r は異なる先行塔を与える。同じ塔には同じ高さのブロックが一つしかないからである。従って高さが MM を超えた塔が MM 個より多く既に存在する。そのうち一つはラベル j>Mj>M を持つ。ラベルが MM 以下の塔は MM 個しかないからである。塔 jj の高さを MM から M+1M+1 に初めて上げるブロックを BtB_t とする。このとき at=j>Ma_t=j>M かつ at+1=M+1>Ma_{t+1}=M+1>M であり、t<nt<n なので nn の選び方に矛盾する。よって an>Ma_n>M なら an+1≤Ma_{n+1}\le M である。従って連続する二項のうち少なくとも一方は MM 以下であり、1,…,M1,\ldots,M のいずれかの値が無限回現れる。塔 1,…,L1,\ldots,L が全て無限に伸びるような最大の LL を取る。先の単射により、無限に伸びる塔があればそれより小さい全ての塔も無限に伸び、塔 L+1,…,ML+1,\ldots,M は有界である。