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。
第 2/6 步：箭头将其划分为至多 20152015 条上升链
上一步下一步
通俗地说

从任意起点沿箭头前进都会描绘出一条递增的链，并且每个正整数恰好位于一条这样的链上。

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 是单射，每个正整数至多有一个箭头指向它，因此从任意一点沿箭头正向和反向追踪都会描绘出一条上升链，反向只在有限个没有箭头指入的起点处终止。这些链合起来把正整数划分为 bb 条互不相交的上升链 c1,…,cbc_1,\dots,c_b，每条链每一步向前跳跃不超过 20152015。链的数目至多为 20152015，因为在任意 20152015 个连续正整数中，每条链都必须至少包含一个元素（由于同一条链相邻元素之间的间隔至多为 20152015），所以最多只能容纳 20152015 条链。