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 中的点上。
第 3/5 步：替换撞上最后一个地雷的跳跃
上一步下一步
通俗地说

若检查点右侧没有地雷，当较短路径撞上最大地雷时，最长跳跃可以越过它。

m=max⁡M⟹m−ak+an>mm=\max M\quad\Longrightarrow\quad m-a_k+a_n>m
详细分析

先设 x∉Mx\notin M 且没有大于 xx 的地雷。若 MM 为空则已完成；否则令 m=max⁡Mm=\max M。对较短的长度和 M∖{m}M\setminus\{m\} 应用归纳。若所得路径从不落在 mm，就在末尾加入 ana_n。若第 kk 次跳跃 aka_k 落在 mm，就用 ana_n 替换该跳跃，并把 aka_k 放到最后。此时的新位置为 m−ak+an>mm-a_k+a_n>m，之后的位置也都大于 mm；终点为 ss。若 x∈Mx\in M 且没有大于 xx 的地雷，同样取 m=xm=x，对 M∖{x}M\setminus\{x\} 应用归纳即可。