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 中的点上。
第 1/5 步：加强归纳命题并设定记号
上一步下一步
通俗地说

最长的跳跃自然适合放在最后，而它之前的点是关键检查点。

a1<⋯<an,s=a1+⋯+an,x=s−ana_1<\cdots<a_n,\quad s=a_1+\cdots+a_n,\quad x=s-a_n
详细分析

我们对 nn 归纳证明一个稍强的命题：对于任意至多含 n−1n-1 个正禁止点且总和 ss 不在其中的集合，都能安全排列这些跳跃。将长度排列为 a1<⋯<ana_1<\cdots<a_n，记 s=a1+⋯+ans=a_1+\cdots+a_n，并设 x=s−anx=s-a_n。当 n=1n=1 时显然成立。