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 の少なくとも一方は、ある時点から周期的になることを証明せよ。
ステップ 6/6: 鳩の巣原理が最終的な周期性を強いる
前のステップ次のステップ
ざっくり言うと

利用可能な状態が有限個しかなく、状態を一度に二つの添字だけ進める決定的な規則があるので、状態の列は最終的にある値を繰り返さざるを得ず、それ以降はずっと周期的に循環する。

T(n)=T(n′)  ⟹  an,an+2,… periodic from that pointT(n)=T(n')\implies a_n,a_{n+2},\ldots \text{ periodic from that point}
詳しい解説

T(n)T(n) は nn が N′,N′+2,N′+4,…N',N'+2,N'+4,\ldots を動くとき（ステップ5）有限個の値しかとらず、T(n+2)T(n+2) は T(n)T(n) の決定的な関数であるから、鳩の巣原理により、ある状態が繰り返される。すなわちある n<n′n<n' で n≡n′(mod2)n\equiv n'\pmod2 を満たすものについて T(n)=T(n′)T(n)=T(n') となる。それ以降、状態は周期 n′−nn'-n で循環し、特に対応する部分列 ana_n（一方の偶奇の添字）はある時点から周期的になる。N′N' の偶奇は定まっているので、これは二つの部分列 a1,a3,a5,…a_1,a_3,a_5,\ldots と a2,a4,a6,…a_2,a_4,a_6,\ldots の少なくとも一方がある時点から周期的であることを示している。