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 中的点上。
第 2/5 步：右侧有地雷的安全检查点
上一步下一步
通俗地说

检查点之后有地雷时，之前的地雷太少，无法阻挡所有较短的跳跃。

x∉M,M∩(x,∞)≠∅x\notin M,\quad M\cap(x,\infty)\ne\varnothing
详细分析

设 x∉Mx\notin M 且 M∩(x,∞)≠∅M\cap(x,\infty)\ne\varnothing。不超过 n−2n-2 个禁止点位于 xx 的左侧或恰在 xx。对 n−1n-1 个长度 a1,…,an−1a_1,\ldots,a_{n-1} 及这些点应用归纳假设，可以不碰到禁止点而到达该点。最后跳跃 ana_n 落在 x+an=sx+a_n=s，而终点不属于 MM。