學長的解法 ※ [本文轉錄自 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)