MathLabs

第6题

设 a1,…,ana_1,\ldots,a_n 是互不相同的正整数，MM 是一个含有 n−1n-1 个正整数且不包含 s=a1+⋯+ans=a_1+\cdots+a_n 的集合。一只蚱蜢从 00 出发，按某个顺序向右跳 nn 次，跳跃长度为 a1,…,ana_1,\ldots,a_n。证明可以选择这个顺序，使蚱蜢从不落在 MM 中的点上。
第 5/5 步：用安全的两跳结尾完成
上一步下一步
通俗地说

先用归纳到达所选两次跳跃之前的位置，再由这两次跳跃依次落在两个安全检查点并最终到达安全总和。

(b1,…,bn−2,an,ai)(b_1,\ldots,b_{n-2},a_n,a_i)
详细分析

对上面找到的指标 ii，对除 aia_i 与 ana_n 外的 n−2n-2 个长度及禁止集合 M∖{x,m}M\setminus\{x,m\} 应用归纳。它们的总和为 viv_i，不在禁止集合中，故设其安全顺序为 (b1,…,bn−2)(b_1,\ldots,b_{n-2})。采用顺序 (b1,…,bn−2,an,ai)(b_1,\ldots,b_{n-2},a_n,a_i)。前半段避开其余地雷；下一落点为 vi+an=uiv_i+a_n=u_i，最后落点为 ui+ai=su_i+a_i=s，二者都安全。归纳完成。