学长的解法 ※ [本文转录自 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 为第一步 , 剩下交给归纳假设 看看罗~ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 220.137.91.31 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 219.68.25.88 ※ 编辑: LimSinE 来自: 219.68.25.88 (08/02 21:08)