學長的解法
※ [本文轉錄自 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 為第一步 , 剩下交給歸納假設
看看囉~