MathLabs

第6問

整数の数列 a1,a2,…a_1,a_2,\dots が次の条件を満たすとする：(i) すべての j≥1j\ge1 に対して 1≤aj≤20151\le a_j\le 2015；(ii) すべての 1≤k<ℓ1\le k<\ell に対して k+ak≠ℓ+aℓk+a_k\ne \ell+a_\ell。n>m≥Nn>m\ge N を満たすすべての整数 mm, nn に対して ∣∑j=m+1n(aj−b)∣≤10072\left|\sum_{j=m+1}^{n}(a_j-b)\right|\le 1007^2 となるような正の整数 bb と NN が存在することを証明せよ。
ステップ 2/6: 矢印は高々 20152015 個の上昇鎖に分割される
前のステップ次のステップ
ざっくり言うと

任意の出発点から矢印をたどると増加する鎖が描かれ、すべての正の整数はちょうど1つのそのような鎖の上にある。

Z>0=c1⊔c2⊔⋯⊔cb,b≤2015\mathbb{Z}_{>0}=c_1\sqcup c_2\sqcup\dots\sqcup c_b,\qquad b\le 2015
詳しい解説

各 k≥1k\ge1 に対して kk から f(k)=k+akf(k)=k+a_k へ矢印を引く。ff は単射であるから、すべての正の整数には高々1本の矢印しか入ってこない。したがって任意の点から矢印を前後にたどると上昇鎖が描かれ、逆方向にたどると入ってくる矢印のない有限個の出発点でのみ終わる。これらの鎖を合わせると、正の整数は bb 個の互いに素な上昇鎖 c1,…,cbc_1,\dots,c_b に分割され、それぞれ1ステップごとに高々 20152015 だけ前方に飛ぶ。鎖は高々 20152015 個である。なぜなら、任意の連続する 20152015 個の正の整数の中に各鎖は少なくとも1つの元を含まねばならず（1つの鎖の連続する元の間の隙間は高々 20152015 であるため）、したがって高々 20152015 個の鎖しか収まらないからである。