黃昏流星群51提到的2009數學奧林匹克第六題
據說這題，當年只有三位參賽者答出。
澳16岁华裔少年数学奥林匹克大赛夺冠 … 澳洲16岁华裔少年，来自James Ruse中学11年级学生Sampson Wong在2009年国际数学奥林匹克大赛为澳洲夺得一枚金牌。成为少数几个获得过奥数金牌的澳洲人。… 前四题Sampson得到满分，第五题得到6分，虽然他没有解出第六题,但因总分34分的好成绩获得金牌。
森棚教官…把问题改编成简易版: 一隻蚱蜢要回家， 从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 这个顺序跳， 否则它在第三步会踩到地雷. 好， 问题是这样: 证明不管路上的九个地雷如何分佈， 蚱蜢一定可以找到一种安全跳回家的方法.
原始问题是这个简易版的一般化. 解这个问题我花了三天， 终于有点眉目. 我不用太难过， 同一个问题 Terence Tao (费尔兹奖得主， IMO 最年轻金牌纪录保持人) 也花了八个小时. 他还在网路上开了一个讨论串号召大家一起解题， 一堆有名气的数学家上去集体想，也是花了好几天才终于有个完整的答桉.
而那些考试的学生只有四个半小时作三题，其中一题是这个超级难题. 然后， 居然还有三个学生作对. 这不是天赋是什麽? 只要好好培养，保持坚持的毅力，并跳脱解小问题的格局， 这裡面真的会出现很多好科学家.
用歸納法 假設 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 為第一步 , 剩下交給歸納假設 看看囉~
.
reply_count: 0
get_replies : 0
.
