这个续集只聊第 \(6\) 题. 这个问题和 Siteswap 有关.
一个杂耍师在表演一种抛球的杂技. 表演开始, 杂技师往空中抛出一个球. 球在第 \(1\) 秒爬升到 \(a_1\) 的高度. 以后, 每过 \(1\) 秒, 这个球高度降低 \(1\). 那么, 球离开杂技师 \(a_1\) 秒之后, 也就是在表演开始后的第 \(1+a_1\) 秒, 这个球将回到杂耍师手中. 第一个球回到杂耍师的时间记为 \(d_1\), 即 \(d_1=1+a_1\).
杂耍师在抛出第一个球之后, 每过 \(1\) 秒, 他都要抛出一个球.
如果 \(1+a_1=2\), 即 \(a_1=1\) 之时, 第一个球在第 \(2\) 秒回到他的手中. 于是, 杂耍师可以把这个球再次的抛向高空.
如果 \(1+a_1\gt2\), 即 \(a_1\gt1\) 之时, 第一个球在第 \(2\) 秒不能回到他的手中. 这时, 杂耍师需要一个新球, 并且把这个新球往空中抛出.
无论杂技师在第 \(2\) 秒抛出的是第一个球还是新球, 这个球都会飞速在第 \(2\) 秒到达海拔 \(a_2\). 以后, 这个球的高度每过 \(1\) 秒降低 \(1\), 因此将在第 \(2+a_2\) 秒回到他的手中. 记 \(d_2=2+a_2\). \(d_2\ne d_1\) 蕴涵前两次抛出的球不会同时落地, 因此当然不在同一高度.
杂耍师在第 \(3\) 秒要抛出一个球.
如果 \(d_1=3\) 或 \(d_2=3\), 第一次或第二次抛出的球此时会回到杂耍师手中, 因此, 他可以把回来的球抛出.
如果 \(d_1\ne3\) 并且 \(d_2\ne3\), 没有球回来, 杂耍师把一个新球抛出.
无论杂技师在第 \(3\) 秒抛出的是旧球还是新球, 这个球都会在第 \(3\) 秒飞速到达海拔 \(a_3\). 以后, 这个球的高度每过 \(1\) 秒降低 \(1\), 因此将在第 \(3+a_3\) 秒回到他的手中. 记 \(d_3=3+a_3\). \(d_1\),\(d_2\), \(d_3\) 互不相等蕴涵空中的球不会同时落地, 因此当然不在同一高度.
杂耍师的表演一直这样继续, 直至海枯石烂. 他在第 \(k\) 秒要抛出一个球, 这里 \(k\) 是正整数.
记 \(d_j=a_j+j\), \(j=1\), \(2\), \(\dotsc\). 注意, \(d_1\), \(d_2\), \(\dotsc\) 两两不等.
如果有某个正整数 \(j\lt k\) 使得 \(d_j=k\), 第 \(j\) 秒抛出的球此时会回到杂耍师手中. 因此, 他可以把回来的球抛出. 否则, 没有球回来, 杂耍师把一个新球抛出.
无论杂技师在第 \(k\) 秒抛出的是旧球还是新球, 这个球都会在第 \(k\) 秒飞速到达海拔 \(a_k\). 以后, 这个球的高度每过 \(1\) 秒降低 \(1\), 因此将在第 \(k+a_k\) 秒回到他的手中. \(d_1\),\(d_2\), \(\dotsc\), \(d_k\) 互不相等表明空中的球不会同时落地, 因此当然不在同一高度: 如果 \(d_j\geqslant k\)(\(1\leqslant j\leqslant k\)), 第 \(j\) 秒抛出的球在第 \(k\) 秒的高度是 \(a_j-(k-j)=a_j+j-k\)(高度是 \(0\) 的意思是球回到杂耍师手上).
杂耍师不会需要无穷多个新球. 实际上, 他至多需要 \(2015\) 个球就可以永远站在舞台上卖力表演. 这是因为空中抛出的球的高度都不超过 \(2015\) 并且互不相同, 每个球经过至多 \(2015\) 秒就会回到他的手中.
设杂耍师用了 \(b\) 个球. 当然, \(1\leqslant b\leqslant2015\). 把这 \(b\) 个球的初次被抛出的时间记为 \(t_1\), \(t_2\), \(\dotsc\), \(t_b\). 于是, \(t_1\), \(t_2\), \(\dotsc\), \(t_b\) 恰是 \(d_1\), \(d_2\), \(\dotsc\) 不能取到的全部正整数.
我们用 \(S_j\) 表示第 \(j\) 秒空中所有的球的高度之和(第 \(j\) 秒, 杂耍师抛出的球已经到达海拔 \(a_j\). 在 \(j\geq2\), 第 \(j-1\) 秒高度为 \(1\) 的球在第 \(j\) 秒已经回到杂技师手中并且已被抛到高度 \(a_j\), 第 \(j-1\) 秒高度不低于 \(2\) 的球的高度在第 \(j\) 秒都已降低 \(1\)), \(j=1\), \(2\), \(3\), \(\dotsc\). 注意 \(S_1=a_1\).
取定一个正整数 \(N\geqslant\max\{t_1, t_2, \dotsc, t_b\}\).
当 \(j\geqslant N\), 在第 \(j\) 秒, 杂耍师完成把一个球抛到海拔 \(a_j\) 后, 空中有 \(b\) 个球, 这些球的高度互不相同, 并且恰好有一个球的高度是 \(1\), 因为第 \(j+1\) 秒恰好有一个球回到杂耍师手中(就是第 \(i\) 秒抛出的那个球, \(i\) 使得 \(d_i=j+1\)). 于是, \(S_j\) 是 \(b\) 个互不相同的数的和: 有一个是 \(1\), 有 \(b-1\) 个属于 \(\{2, 3, 4, \dotsc, 2015\}\).
既然第 \(j\) 秒, 高度是 \(1\) 的球会在第 \(j+1\) 秒被抛到海拔 \(a_{j+1}\), 高度 \(\gt1\) 的 \(b-1\) 个球都在第 \(j+1\) 秒海拔降低 \(1\), 因此
\begin{equation}S_{j+1}-S_j=a_{j+1}-1-\left(b-1\right)=a_{j+1}-b.\end{equation}
至此, 对于任意满足 \(n\gt m\geqslant N\) 的正整数 \(m\) 和 \(n\), 有
\begin{equation}S_n-S_m=\sum_{j=m+1}^n\Big(a_j-b\Big).\end{equation}
注意, \(S_n\) 和 \(S_m\) 都是 \(\{1, 2, 3,\dotsc,2015\}\) 中包括 \(1\) 在内的 \(b\) 个互不相同的数的和, 所以
\begin{equation}\begin{split}
\left|S_n-S_m\right|&\leqslant\Big(1+2015+2014+\dotsb+(2017-b)\Big)-\Big(1+2+3+\dotsb+b\Big)\\&=\Big(2015-b\Big)\Big(b-1\Big)\leqslant1007^2.\end{split}\end{equation}
我们下面来把这个证明改写成”纯”, “完全彻底” 的数学论证. 有几个选择, 不过繁简有微小差别, 虽然实质一样.
解答三
对每个整数 \(j\geq1\), 令
\begin{equation}\mathfrak A_j=\{a_k+k-j\mid1\leq k\leq j,\;a_k+k\gt j\}.\end{equation}
显然, \(a_j\in \mathfrak A_j\).
注意, \(1\leq k\leq j\) 时,
\[a_k+k-j\leq a_k\leq2015\]
蕴涵 \(1\leq|\mathfrak A_j|\leq 2015\).
另一方面, \(1\leq k\leq j\) 时,
\[\Big(a_k+k-j\Big)-1=\Big(a_k+k\Big)-\Big(j+1\Big)\ne a_{j+1}\]
蕴涵 \(a_{j+1}\notin\{x-1\mid x\in \mathfrak A_j\}\).
当 \(1\notin \mathfrak A_j\) 时,
\[\mathfrak A_{j+1}=\{x-1\mid x\in \mathfrak A_j\}\cup\{a_{j+1}\}.\]
此时, \(|\mathfrak A_{j+1}|= |\mathfrak A_j|+1\).
当 \(1\in \mathfrak A_j\) 时,
\[\mathfrak A_{j+1}=\{x-1\mid x\gt1,\; x\in \mathfrak A_j\}\cup\{a_{j+1}\}.\]
此时, \(|\mathfrak A_{j+1}|= |\mathfrak A_j|\).
无论如何, \(|\mathfrak A_{j+1}|\geq |\mathfrak A_j|\) 为真. 于是, 存在正整数 \(N\), 使得对任意整数 \(j\geq N\), \(|\mathfrak A_j|\) 都是同一个数. 记这个不变的数是 \(b\), 即 \(b=|\mathfrak A_N|\). 注意, \(j\geq N\), \(|\mathfrak A_j|\) 不变蕴涵 \(1\in\mathfrak A_j\).
考察 \(S_j=\sum\limits_{h\in\mathfrak A_j}\)h, \(j\geq1\).
当 \(j\geq N\), 照样有 \((1)\), \((2)\), \((3)\).
解答四
考察 \(d_j=a_j+j\), \(j=1\), \(2\), \(\dotsc\). 于是, 正整数序列 \(d_1\), \(d_2\), \(\dotsc\) 互不相同, 并且对每个正整数 \(j\geqslant1\), 有 \(j+1\leqslant d_j\leqslant j+2015\).
显然, 肯定有正整数不会在序列 \(\{d_j\}\) 中出现, 比如 \(1\). 我们指出, 至多有 \(2015\) 个正整数 \(t\), 使得不存在正整数 \(j\), 满足 \(d_j=t\). 换句话说, 集合 \(\{1, 2, 3, \dotsc\}\setminus\{d_1, d_2,\dotsc\}\) 的元素个数 \(b\), 成立 \(1\leqslant b\leqslant 2015\).
设 \(t_1\), \(t_2\), \(\dotsc\), \(t_c\) 是没有在序列 \(\{d_j\}\) 中出现的 \(c\) 个正整数, 这里 \(c\) 是正整数. 对每一个 \(t_i\), \(1\leqslant i\leqslant c\), 考察如下的正整数序列
\begin{equation}x_0=t_i,\; x_j=d_{x_{j-1}},\; j\geqslant1. \end{equation}
我们把这个序列称为由 \(t_i\) 出发的 \(d\) 序列. 如此一来, 这样的 \(d\) 序列有 \(c\) 个. 序列 \(d_1\), \(d_2\), \(\dotsc\) 互不相同说明任意两个 \(d\) 序列不会出现相同的项.
显然, 对每个正整数 \(j\geqslant1\), \(x_j\) 会在序列 \(\{d_j\}\) 中出现, 并且 \(x_j=d_{x_{j-1}}\gt x_{j-1}\) 表明序列 \(\{x_j\}\) 严格递增, 以及
\begin{equation}x_j=d_{x_{j-1}}\leqslant x_{j-1}+2015.\end{equation}
对于任意的正整数 \(T\gt t_i\), 设 \(g_i\) 是使得 \(x_{g_i+1}\gt T\) 成立的最小非负整数. 换句话说, \((5)\) 中的序列 \(\{x_j\}\) 中的项 \(x_1\), \(x_2\), \(\dotsc\), \(x_{g_i}\) 都是不超过 \(T\) 的正整数, 并且这 \(g_i\) 项都在序列 \(\{d_j\}\) 中出现(\(g_i=0\) 的意思是 \(x_1\), \(x_2\), \(x_3\), \(\dotsc\) 都大于 \(T\)). 我们指出
\begin{equation}g_i\gt\frac{T-t_i}{2015}-1.\end{equation}
事实上, 记得 \((6)\), 于是
\[T\lt x_{g_i+1}\leqslant t_i+2015(g_i+1).\]
这就是 \((7)\).
取定一个正整数 \(A\gt\max\{t_1, t_2, \dotsc, t_c\}\). 根据 \((7)\), 当 \(T\) 是任意的满足 \(T\gt A\) 的正整数时, 序列 \(\{d_j\}\) 中不超过 \(T\) 的项至少有
\begin{equation}g_1+g_2+\dotsb+g_c\gt\sum_{i=1}^c\left(\frac{T-t_i}{2015}-1\right)\gt\sum_{i=1}^c\left(\frac{T-A}{2015}-1\right)=c\left(\frac{T-A}{2015}-1\right)\end{equation}
个.
显然, 序列 \(\{d_j\}\) 中不超过 \(T\) 的项少于 \(T\) 个. 于是
\begin{equation}T\gt c\left(\frac{T-A}{2015}-1\right).\end{equation}
这个式子要对大于 \(A\) 的所有正整数 \(T\) 为真, 必定 \(c\leqslant2015\).
至此, 我们证明了 \(1\leqslant b\leqslant 2015\).
设 \(Y=\{t_1, t_2, \dotsc, t_b\}\) 是所有的没有在序列 \(\{d_j\}\) 中出现的 \(b\) 个正整数组成的集合. 于是, 有由 \(t_1\), \(t_2\), \(\dotsc\), \(t_b\) 出发的 \(b\) 个 \(d\) 序列; \(Y\cup\{d_1, d_2, d_3\dotsc\}\) 恰好就是全部正整数形成的集合.
记 \(\mathfrak D=\{d_1, d_2, d_3\dotsc\}\).
我们指出, \(\mathfrak D\) 中的每个元素在一个 \(d\) 序列中出现一次, 并且只在一个 \(d\) 序列中出现. 于是, \(b\) 个 \(d\) 序列的所有项不重复不遗漏的恰好是全部的正整数.
事实上, 设 \(d_{j_1}\) 是 \(\mathfrak D\) 中的任何一个元素.
如果 \(j_1\notin \mathfrak D\), 那么 \(d_{j_1}\) 恰是由 \(j_1\) 出发的 \(d\) 序列的第 \(2\) 项. 如果 \(j_1\in \mathfrak D\), 必有 \(j_2\lt j_1 \) 使得 \(d_{j_2}=j_1\).
如果 \(j_2\notin \mathfrak D\), 那么 \(d_{j_1}\) 恰是由 \(j_2\) 出发的 \(d\) 序列的第 \(3\) 项. 如果 \(j_2\in \mathfrak D\), 必有 \(j_3\lt j_2 \) 使得 \(d_{j_3}=j_2\).
如此下去. 这个过程不可能无限进行下去. 恰有惟一的正整数 \(l\), 使得
\[ j_l\notin \mathfrak D,\; j_{l-1},\; j_{l-2},\;\dotsc,\; j_2,\; j_1\in \mathfrak D,\; j_l\lt j_{l-1}\lt j_{l-2}\lt\dotsb\lt j_2\lt j_1, \]
\[d_{j_l}=j_{l-1},\; d_{j_{l-1}}=j_{l-2},\;\dotsc,\; d_{j_2}=j_1.\]
\(d_{j_1}\) 恰是由 \(j_l\) 出发的 \(d\) 序列的第 \(l+1\) 项.
取定一个正整数 \(N\gt\max\{t_1, t_2, \dotsc, t_b\}\).
设 \(n\) 和 \(m\) 是任意的满足 \(n\gt m\geq N\) 的整数. \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 会分布在所有的这 \(b\) 个 \(d\) 序列中. 每一个 \(d\) 序列的下标都是严格递增的(\(d_k\) 与 \(d_l\) 都是同一个 \(d\) 序列中的项, 且 \(d_k\) 在 \(d_l\) 前面, 那么 \(k\lt l\)), 因此, \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 在同一个 \(d\) 序列中出现的项一定是这个 \(d\) 序列中的连续若干项.
考虑由 \(t_i\)(\(1\leq i\leq b\)) 出发的 \(d\) 序列中的连续项
\begin{equation}x_u,\; x_{u+1},\;x_{u+2},\;\dotsc,\; x_{u+v},\; x_{u+v+1},\end{equation}
这里 \(u\) 是正整数, \(v\) 是非负整数, 并且
\begin{equation}x_u\lt m+1\leq x_{u+1}\lt x_{u+2}\lt\dotsb \lt x_{u+v}\leq n\lt x_{u+v+1}.\end{equation}
换句话说, \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 在 \(t_i\)(\(1\leq i\leq b\)) 出发的 \(d\) 序列中出现的所有的项恰好就是下面这 \(v\) 项(\(v=0\) 就是此 \(d\) 序列不包括 \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 中的任意一项)
\begin{equation}d_{x_{u+1}},\;d_{x_{u+2}}\,\;\dotsc,\;d_{x_{u+v}}.\end{equation}
注意
\begin{equation}x_{u+1}=d_{x_u},\;x_{u+2}=d_{x_{u+1}},\;x_{u+3}=d_{x_{u+2}}\,\;\dotsc,\;x_{u+v+1}=d_{x_{u+v}},\end{equation}
我们有
\begin{equation}\sum_{k=1}^v\Big(d_{x_{u+k}}-x_{u+k}\Big)=\sum_{k=1}^v\Big(x_{u+k+1}-x_{u+k}\Big)=x_{u+v+1}-x_{u+1}=d_{x_{u+v}}-d_{x_u}.\end{equation}
于是
\begin{equation}\sum_{k=1}^v\Big(d_{x_{u+k}}-x_{u+k}\Big)-\Big(n-m\Big)=\Big(d_{x_{u+v}}-n\Big)-\Big(d_{x_u}-m\Big).\end{equation}
注意
\begin{equation}d_{x_u}-m=\Big(x_u+a_{x_u}\Big)-m=a_{x_u}-\Big(m-x_u\Big)\end{equation}
说明 \(1\leq d_{x_u}-m\leq2015\). 同样的道理, \(1\leq d_{x_{u+v}}-n\leq2015\).
我们记 \(h=d_{x_u}-m\), \(H=d_{x_{u+v}}-n\). 则
\begin{equation}\sum_{k=1}^v\Big(d_{x_{u+k}}-x_{u+k}\Big)-\Big(n-m\Big)=H-h,\end{equation}
这里, \(1\leq h,\; H\leq2015\).
把 \(t_i\) 相应的 \(u\), \(v\), \(h\), \(H\) 记为 \(u_i\), \(v_i\), \(h_i\), \(H_i\), \(1\leq i\leq b\). 注意, \(h_i\) 互不相同, \(H_i\) 也是互不相同.
当 \(i\) 跑遍 \(1\), \(2\), \(\dotsc\), \(b\) 时,
\begin{equation}\sum_{i=1}^b\Big(\sum_{k=1}^{v_i}(d_{x_{u_i+k}}-x_{u_i+k})-(n-m)\Big)=\sum_{i=1}^b\Big(H_i-h_i\Big)=\sum_{i=1}^b H_i-\sum_{i=1}^b h_i.\end{equation}
\(d_{x_{u_i+1}}\), \(d_{x_{u_i+2}}\), \(\dotsc\), \(d_{x_{u_i+v_i}}\) 是 \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 在由 \(t_i\)(\(1\leq i\leq b\)) 出发的 \(d\) 序列中出现的所有的项. 当 \(i\) 跑遍 \(1\), \(2\), \(\dotsc\), \(b\) 时, \(d_{x_{u_i+1}}\), \(d_{x_{u_i+2}}\), \(\dotsc\), \(d_{x_{u_i+v_i}}\) 不重复不遗漏恰好就是 \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\). 我们有
\begin{equation}\sum_{k=m+1}^n\Big(d_k-k\Big)=\sum_{i=1}^b\sum_{k=1}^{v_i}\Big(d_{x_{u_i+k}}-x_{u_i+k}\Big).\end{equation}
\(d_k-k=a_k\) 表明
\begin{equation}\begin{split}\sum_{k=m+1}^n\Big(a_k-b\Big)&=\sum_{k=m+1}^n a_k-b\Big(n-m\Big)\\&=\sum_{i=1}^b\Big(\sum_{k=1}^{v_i}(d_{x_{u_i+k}}-x_{u_i+k})-(n-m)\Big)\\&=\sum_{i=1}^b H_i-\sum_{i=1}^b h_i.\end{split}\end{equation}
注意, 一定恰有惟一的 \(i\)(\(1\leq i\leq b\)), 使得 \(x_{u_i+1}=m+1\); 恰有惟一的 \(j\)(\(1\leq j\leq b\)), 使得 \(x_{u_j+v_j+1}=n+1\). 此时
\begin{equation}h_i=d_{x_{u_i}}-m=x_{u_i+1}-m=1,\; H_j=d_{x_{u_j+v_j}}-n=x_{u_j+v_j+1}-n=1.\end{equation}
\(h_1\), \(h_2\), \(\dotsc\), \(h_b\) 是 \(\{1, 2, 3,\dotsc,2015\}\) 中包括 \(1\) 在内的 \(b\) 个互不相同的元素, \(H_1\), \(H_2\), \(\dotsc\), \(H_b\) 亦然. 故而
\begin{equation}\begin{split}
\left|\sum_{k=m+1}^n\Big(a_k-b\Big)\right|&\leqslant\Big(1+2015+2014+\dotsb+(2017-b)\Big)-\Big(1+2+3+\dotsb+b\Big)\\&=\Big(2015-b\Big)\Big(b-1\Big)\leqslant1007^2.\end{split}\end{equation}
看到我们的魂牵梦绕.
最后的式子泄漏了本性: 与上两个解法的本质是一样的!
解答五
这个主意是本题供题人之一的 Ivan Guo 给出的. 背后的想法倒不是多复杂, 要写清楚要仔细的挑选.
令 \(d_j=a_j+j\), \(j=1\), \(2\), \(\dotsc\). 于是, 正整数序列 \(d_1\), \(d_2\), \(\dotsc\) 互不相同, 并且对每个正整数 \(j\geqslant1\), 有 \(j+1\leqslant d_j\leqslant j+2015\).
把
\begin{equation}d_1,\; d_2,\; d_3, \;\dotsc\end{equation}
按照从小到大的顺序排列成 \(d_{i_1}\), \(d_{i_2}\), \(d_{i_3}\), \(\dotsc\). 即, \(i_1\), \(i_2\), \(i_3\), \(\dotsc\) 是全体正整数的一个排列, 且
\begin{equation}d_{i_1}\lt d_{i_2}\lt d_{i_3}\lt\dotsb.\end{equation}
把一个序列中的某两项对调位置, 而其余的项不动, 得到另一个序列的变换称为一个对换. 需要强调的是, 这里的对换, 允许对调位置的两项重合. 也就是说, 一个对换可以不变动任何一项的位置.
令 \(\pi_0\) 和 \(\pi\) 分别就是\((23)\) 中的序列 \(\{d_j\}\) 和 \((24)\) 中的序列.
从 \(\pi_0\) 开始, 通过有限次的对换, 我们可以得到最前面若干项与 \(\pi\) 相同, 并且只有有限项与 \(\pi_0\) 不同的序列. 具体来说, 设 \(\pi_1\) 是通过交换 \(\pi_0\) 的两项 \(d_1\) 与 \(d_{i_1}\) 的位置得到的序列. 如果 \(d_1=d_{i_1}\), \(\pi_1\) 与 \(\pi_0\) 是同一个序列. \(\pi_1\) 的首项即是 \(d_{i_1}\). 设 \(\pi_2\) 是通过交换 \(\pi_1\) 的第 \(2\) 项与 \(d_{i_2}\) 的位置得到的序列. \(\pi_2\) 的前 \(2\) 项即是 \(d_{i_1}\), \(d_{i_2}\). 一般地, 设 \(\pi_j\) 是通过交换 \(\pi_{j-1}\) 的第 \(j\) 项与 \(d_{i_j}\) 的位置得到的序列, \(j\) 是正整数. \(\pi_j\) 可能与 \(\pi_{j-1}\) 是同一个序列. \(\pi_j\) 的前 \(j\) 项即是 \(d_{i_1}\), \(d_{i_2}\), \(\dotsc\), \(d_{i_j}\); \(\pi_j\) 至多有 \(2j\) 项与 \(\pi_0\) 不同.
令 \(e_j=d_{i_j}-j\), \(j=1\), \(2\), \(\dotsc\).
首先指出, 序列 \(e_1\), \(e_2\), \(e_3\), \(\dotsc\) 单调递增, 但不是严格单调, 并且对每个整数 \(j\geq1\),
\begin{equation}1+j\leq d_{i_j}\leq2015+j,\;1\leq e_j\leq2015.\end{equation}
于是, 存在两个正整数 \(b\) 和 \(M\), \(1\leq b\leq2015\), 对所有满足 \(j\geq M\) 的整数 \(j\), \(e_j=b\) 成立.
事实上, \(d_{i_1}=i_1+a_{i_1}\geq2\). 于是
\[d_{i_j}\geq d_{i_1}+\Big(j-1\Big)\geq2+\Big(j-1\Big)=j+1.\]
\(d_{i_j}\) 是 \(\pi_0\) 按照从小到大排序的第 \(j\) 项, 所以
\[d_{i_j}\leq\max\{d_1,\;d_2,\;\dotsc,\;d_j\}\leq j+2015.\]
此时, 当然应当有
\[1\leq e_j=d_{i_j}-j\leq2015.\]
此外,
\[e_{j+1}-e_j=\Big(d_{i_{j+1}}-(j+1)\Big)-\Big(d_{i_j}-j\Big)=d_{i_{j+1}}-d_{i_j}-1\geq0\]
表明 \(e_{j+1}\geq e_j\).
\(j\) 是非负整数, \(k\) 是正整数. 设 \(\pi_j\) 的第 \(k\) 项是 \(d_{j,\, k}\), 即 \(\pi_j\) 是如下的序列
\begin{equation}d_{j,\, 1},\; d_{j,\, 2},\; d_{j,\,3},\;\dotsc,\; d_{j,\, k},\;\dotsc.\end{equation}
于是当 \(j\geq1\) 时, \(d_{j,\, 1}=d_{i_1}\), \(d_{j,\, 2}=d_{i_2}\), \(\dotsc\), \(d_{j,\, j}=d_{i_j}\).
我们判定, 对所有的非负整数 \(j\) 和正整数 \(k\), 成立
\begin{equation}1+k\leq d_{j,\,k}\leq2015+k.\end{equation}
我们对 \(j\) 进行归纳.
\(d_{0,\,k}=d_k\) 表明奠基显然.
对正整数 \(j\) 和 \(k\), \(k\gt j\), \(\pi_j\) 是通过交换 \(\pi_{j-1}\) 的第 \(j\) 项与第 \(k\) 项的位置得到的序列. \(\pi_{j-1}\) 的第 \(j\) 项必定是 \(d_{j,\,k}\), 第 \(k\) 项必定是 \(d_{i_j}\), 且 \(d_{j,\,k}\gt d_{i_j}=d_{j,\, j}\). 于是
\[d_{j,\,k}\gt d_{i_j}=d_{j-1,\,k}\geq 1+k.\]
\[d_{j,\,k}= d_{j-1,\,j}\leq 2015+j\lt2015+k.\]
至此, 我们验证了 \((27)\) 的真实性.
当 \(j\geq M\), \(d_{i_j}=j+b\). 故, \(j\geq M\) 时,
\begin{equation}d_{j,\, M}=M+b,\; d_{j,\, M+1}=M+1+b,\; d_{j,\, M+2}=M+2+b,\;\dotsc,\; d_{j,\, j}=j+b.\end{equation}
接下来, 我们来证明: 正整数 \(x\geq M\). 交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), \(x+1\lt y\). 那么
\begin{equation}1\leq y-\Big(x+1\Big)\leq b-1,\; 0\lt d_{x,\, x+1}-d_{x,\, y}\leq2015-b.\end{equation}
事实上, \(d_{x,\,y}=d_{x+1,\, x+1}=x+1+b\), 于是
\begin{equation}0\lt d_{x,\, x+1}-d_{x,\, y}=d_{x,\, x+1}-d_{x+1,\, x+1}\leq\Big(x+1+2015\Big)-\Big(x+1+b\Big)=2015-b.\end{equation}
又因为 \(d_{x,\,y}\geq y+1\), \(x+1\lt y\), 所以
\begin{equation}x+1+b\geq y+1\end{equation}
定出 \(b-1\geq y-(x+1)\geq1\).
设 \(x\geq0\) 是整数. 交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), \(x+1\leq y\). 那么
\begin{equation}0\leq y-\Big(x+1\Big)\leq2014.\end{equation}
事实上, \(d_{x+1,\, x+1}=d_{x,\,y}\), 于是
\begin{equation}\Big(x+1\Big)+2015\geq d_{x+1,\, x+1}=d_{x,\,y}\geq1+y\end{equation}
从而 \(0\leq y-(x+1)\leq 2014\).
这表明, 我们所做的每一个的对换, 把一个序列的某两项对调位置(允许这两项同一), 此序列在这两项之间至多还有 \(2013\) 项. 于是, 设 \(x\) 是整数, \(0\leq x\leq M\), \(x+1\leq y\), 并且交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\). 那么 \(y\leq M+2015\).
取正整数 \(N\), \(N\gt M+2015\). 于是, 如果通过交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 且 \(y\geq N\), 那么必定 \(x\gt M\), 进而 \(d_{x,\,y}=d_{x+1,\,x+1}=x+1+b\).
设整数 \(m\) 和 \(n\) 适合 \(n\gt m\geq N\).
考察
\begin{equation}s_j=\sum_{k=m+1}^n d_{j,\,k},\;j=0,\,1,\,2,\,\dotsc, n.\end{equation}
我们来观察对换 \(\pi_x\) 的第 \(x+1\) 项与 \(d_{i_{x+1}}\) 的位置对 \(s_x\) 的影响, 即估计 \(s_{x+1}-s_x\), 这里 \(0\leq x\lt n\).
当 \(x+1\lt m+1\leq y\), 交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\). 注意 \(d_{x+1,\, y}=d_{x,\, x+1}\), 于是
\begin{equation}0\lt d_{x+1,\, y}-d_{x,\, y}=d_{x,\, x+1}-d_{x,\, y}\leq2015-b.\end{equation}
在 \(y\leq n\) 成立之时, \(s_{x+1}-s_x=d_{x+1,\, y}-d_{x,\, y}\); 在 \(y\gt n\), \(s_{x+1}=s_x\). 故而
\begin{equation}0\leq s_{x+1}-s_x\leq2015-b.\end{equation}
现在来考虑有多少个 \(x\), 使得交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 且 \(x+1\lt m+1\leq y\). 由 \(b-1\geq y-(x+1)\geq1\), 于是
\begin{equation}b-1\geq m+1-\Big(x+1\Big)\geq1.\end{equation}
从而这样的 \(x\) 不超过 \(b-1\) 个.
同样的道理, 交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 且 \(x+1\leq n\lt y\). \(d_{x+1,\, x+1}=d_{x,\, y}\) 蕴涵
\begin{equation}0\gt d_{x+1,\, x+1}-d_{x,\, x+1}=d_{x,\, y}-d_{x,\, x+1}\geq-\Big(2015-b\Big).\end{equation}
在 \(x+1\geq m+1\) 成立之时, \(s_{x+1}-s_x=d_{x+1,\, x+1}-d_{x,\, x+1}\); 在 \(x+1\leq m\), \(s_{x+1}=s_x\). 故而
\begin{equation}-\Big(2015-b\Big)\leq s_{x+1}-s_x\leq0.\end{equation}
现在来考虑有多少个 \(x\), 使得交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 且 \(x+1\leq n\lt y\). 由 \(b-1\geq y-(x+1)\geq1\), 于是
\begin{equation}b-1\geq n-x\geq1.\end{equation}
至多有 \(b-1\) 个这样的 \(x\).
如果交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 当 \(x+1\leq y\lt m+1\) 或 \(m+1\leq x+1\leq y\leq n\) 时, \(s_{x+1}=s_x\) 皆为真.
至此, \(0\leq x\lt n\), \(s_{x+1}-s_x\) 至多有 \(2(b-1)\) 个不是 \(0\): 至多 \(b-1\) 个正数, 每个都不超过 \(2015-b\); 至多 \(b-1\) 个负数, 每个都不小于 \(-(2015-b)\). 于是
\begin{equation}-\Big(2015-b\Big)\Big(b-1\Big)\leq s_n-s_0\leq\Big(2015-b\Big)\Big(b-1\Big).\end{equation}
注意
\begin{equation}\begin{split}s_0-s_n&=\sum_{k=m+1}^n d_k-\sum_{k=m+1}^n d_{n,\,k}\\&=\sum_{k=m+1}^n \Big(a_k+k\Big)-\sum_{k=m+1}^n\Big(b+k\Big)\\&=\sum_{k=m+1}^n \Big(a_k-b\Big).\end{split}\end{equation}
最后, 我们辛苦一生的梦想握在了手中
\begin{equation}\left|\sum_{k=m+1}^n\Big(a_k-b\Big)\right|\leqslant\Big(2015-b\Big)\Big(b-1\Big)\leqslant1007^2.\end{equation}
