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 が存在することを証明せよ。
ステップ 3/6: bb と NN を選ぶ
前のステップ次のステップ
ざっくり言うと

すべての鎖の出発点を過ぎてしまえば、区間上の和はそれぞれの鎖が最初にその区間から出る場所だけに依存する。

b:=#{chains},N:=max⁡(start-points of the chains)b:=\#\{\text{chains}\},\qquad N:=\max(\text{start-points of the chains})
詳しい解説

上で見つかった鎖 c1,…,cbc_1,\dots,c_b の個数を bb とし、NN をすべての鎖の中で最大の出発点とする。こうすると任意の t≥Nt\ge N に対して、各鎖はすでに ≤N≤t\le N\le t である元を含んでいる。区間 (t1,t2](t_1,t_2] と鎖 cc に対して、指数 j∈c∩(t1,t2]j\in c\cap(t_1,t_2] にわたる値 aj=f(j)−ja_j=f(j)-j の和は、鎖に沿ってテレスコープし (min⁡{x>t2:x∈c}−t2)−(min⁡{x>t1:x∈c}−t1)\big(\min\{x>t_2:x\in c\}-t_2\big)-\big(\min\{x>t_1:x\in c\}-t_1\big) となる。