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。证明存在两个正整数 bb 和 NN,使得对所有满足 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。
第 4/6 步:按链拆分目标和
通俗地说

从和的每一项中减去 bb,恰好补偿了每条链多加的一个“超出”项。

∑j=m+1n(aj−b)=∑chain c[(min⁡{x>n:x∈c}−n)−(min⁡{x>m:x∈c}−m)]\sum_{j=m+1}^{n}(a_j-b)=\sum_{\text{chain }c}\Big[\big(\min\{x>n:x\in c\}-n\big)-\big(\min\{x>m:x\in c\}-m\big)\Big]
详细分析

把上一步的裂项恒等式对全部 bb 条链求和,并与 ∑j=m+1naj=∑j=m+1n(f(j)−j)\sum_{j=m+1}^n a_j=\sum_{j=m+1}^n\big(f(j)-j\big) 比较,可以发现 ∑j=m+1n(aj−b)\sum_{j=m+1}^n(a_j-b) 恰好等于对 bb 条链 cc 求和的 (min⁡{x>n:x∈c}−n)−(min⁡{x>m:x∈c}−m)\big(\min\{x>n:x\in c\}-n\big)-\big(\min\{x>m:x\in c\}-m\big):每条链在 nn 处贡献一个越界项,在 mm 处贡献一个越界项,而恰好有 bb 条链,与施加于 n−mn-m 个下标中每一个的 −b-b 修正相匹配。