学长的解法
※ [本文转录自 Math 看板]
作者: WINDHEAD (Grothendieck吹头) 看板: Math
标题: Re: [计算] 蚱蜢闪地雷
时间: Sun Aug 2 04:03:50 2009
※ 引述《trausing (trausing)》之铭言：
: 一只蚱蜢要回家, 从 0 往右跳
: , 规定一共要跳 1,2,3,4,5,6,7,8,9,10 各一次,
: 但顺序它可以自己决定 (所以蚱蜢一共落脚九次, 而且它家在 1+2+...+10=55 的地方).
: 但是路上有九个地雷, 蚱蜢跳到地雷就拜拜了,
: 比如在 2,5,6,15,17,21,28,43,52 的地方有地雷,
: 则蚱蜢就不能按照 1,2,3,4,5,6,7,8,9,10 这个顺序跳,
: 否则它在第三步会踩到地雷. 好,
: 问题是这样: 证明不管路上的九个地雷如何分布,
: 蚱蜢一定可以找到一种安全跳回家的方法.
: (转自游森鹏blog)
我脑袋简单，麻烦各位大师帮忙抓错:)
用归纳法
假设 n个相异数 a_1 > .. > a_n 为蚱蜢允许的步伐数
假设地雷点由左至右为 b_1 ~ b_(n-1)
情况一) a_1 = b_1
蚱蜢首步走 a_1 , 踩到地雷先不管
因为第二步之后依归纳假设都不会踩到地雷
然后第一步跟第二步对调，因为a_1严格大于其他a_i，所以避开了地雷b_1
情况二) a_1 < b_1
蚱蜢首步走 a_1
依归纳假设，除 b_1 外第二步之后都不会踩到地雷
假设蚱蜢踩到 b_1 ，称踩到 b_1 后的下一步为 a_j
区间 [0 , b_1+a_j] 上的步伐必须重新调配
因为 a_1 > a_j
所以 区间 [0, b_1+a_j] 的最后一步可使用 a_1 , 其他步随便
如此一来就避开了地雷 b_1
情况三) a_1 > .. > a_j ≧ b_1 > a_(j+1) > ... , n>j>1
考虑 j 个位置 a_j~a_1
如果其中某个位置没地雷, 则以此为第一步, 之后交给归纳假设
如果位置 a_j~a_1 全都是地雷, 再考虑 a_1+a_(j+1) ~ a_1+a_n 这n-j个位置
因为只有n-1个地雷, 所以必存在某个位置 a_1+a_i 非地雷
那么以 a_i 为第一步, a_1 为第二步.
因为 a_1~a_j 全是地雷的缘故 , 区间[0,a_1+a_i]中至少有 j≧2 颗地雷
*此步要扣分:::
当j=1时 a_1 >= b_1 > a_2, 但a_1 = b_1时已证
此时 [0,a_1+a_i]中仍然至少有a_1>b_1两颗地雷，但理由不同
故从第三步开始交给归纳假设即可。
情况四) a_n≧b_1
考虑 n-1 个位置 a_1 ~ a_(n-1) , 其中必有某个位置 a_i 非地雷
以 a_i 为第一步 , 剩下交给归纳假设
看看囉~