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 中的点上。
第 4/5 步：在困难情形中找到安全的一对
上一步下一步
通俗地说

检查点处的地雷不能阻挡一对中的任何成员，而其他每个地雷至多阻挡一对。

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

现在设 x∈Mx\in M 且 M∩(x,∞)≠∅M\cap(x,\infty)\ne\varnothing。令 m=max⁡Mm=\max M。对每个满足 1≤i≤n−11\le i\le n-1 的 ii，定义 ui=s−aiu_i=s-a_i 与 vi=s−ai−an=x−aiv_i=s-a_i-a_n=x-a_i。于是 vi<x<uiv_i<x<u_i，所以地雷 xx 不会阻挡这 n−1n-1 对中的任何一个成员。uiu_i 互不相同且都在 xx 右侧，viv_i 也互不相同且都在 xx 左侧；因此其余 n−2n-2 个地雷每个至多阻挡一对。故在这 n−1n-1 对中存在某个 ii 使 ui∉Mu_i\notin M 且 vi∉Mv_i\notin M。