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 が存在することを証明せよ。
ステップ 6/6: 2つの境界を組み合わせ、bb に関して最適化する
前のステップ次のステップ
ざっくり言うと

nn における超過和と mm における超過和の差は (b−1)(2015−b)(b-1)(2015-b) によって制御され、これは AM-GM により 100721007^2 を上限とする。

∣∑j=m+1n(aj−b)∣≤(b−1)(2015−b)≤10072\left|\sum_{j=m+1}^{n}(a_j-b)\right|\le (b-1)(2015-b)\le 1007^2
詳しい解説

前段より、t=nt=n における超過和と t=mt=m における超過和はいずれも区間 [b(b+1)/2, b(4031−b)/2]\big[b(b+1)/2,\ b(4031-b)/2\big] に属するので、それらの差（ステップ4より ∑j=m+1n(aj−b)\sum_{j=m+1}^n(a_j-b) に等しい）はその区間の幅 (b−1)(2015−b)(b-1)(2015-b) によって絶対値が有界となる。AM-GM により (b−1)(2015−b)≤((b−1)+(2015−b)2)2=10072(b-1)(2015-b)\le\left(\frac{(b-1)+(2015-b)}2\right)^2=1007^2 であり、b=1008b=1008 のとき等号が成り立つ。実際の鎖の個数 b∈{1,…,2015}b\in\{1,\dots,2015\} が何であろうと、この不等式 (b−1)(2015−b)≤10072(b-1)(2015-b)\le1007^2 は常に成り立つので、求めるとおり、すべての n>m≥Nn>m\ge N に対して ∣∑j=m+1n(aj−b)∣≤10072\left|\sum_{j=m+1}^n(a_j-b)\right|\le1007^2 が成り立つ。