微軟面試題 - 推理遊戲

: 先從只有兩人看起
: 很明顯最後一人坐對的機率是2分之1
: 接著看三人的情況
: 1號可以有3種選擇:
: a. 坐到1號位
: 則3號一定坐對 機率為 1/3*1
: b. 坐到2號位
: 那剩下的可能性就變成類似兩人的情況
: 只是1號位可以視為2號的正確位置
: 得機率為 1/3*1/2
: c. 坐到三號位
: 機率為 0
: 把三種情況機率相加 1/3 + 1/3*1/2 = 1/2
: 接著就可以利用數學歸納法
: 設當 x<n , x 皆成立時
: 若1號坐到第x號
: 那剩下的可能性就變成類似只有x人的情況
: 而x<n的機率已經設為1/2
: 所以最後一人坐對的機率為
: ( 1 + 1/2*(n-2) ) / n = 1/2
: 得證
: 希望大家看的懂這個爛爛的解法orz....

很有趣 ... 不過, 請問當n=4時
1號有四種選擇
a.坐1號位
p = 1/4*1 = 1/4
b.坐2號位
p = 1/4*(1/3) = 1/12
為何是乘1/3 我解釋一下 ...
因為 當2號位被占走時, 剩下三個位置, 可能發生的情況為:
1,3,4 -->位置
(以下是人)
2,3,4 -->正確
3,2,4 -->正確
2,4,3 -->非
3,4,2 -->非
4,2,3 -->非
4,3,2 -->非

2/6 ... 所以是1/3 (可能很多人不需要看到這麼詳細的解答, 我只是想說的完整)

c. 坐到3號位 (情況與b同)
p = 1/4*(1/3) = 1/12
d. 坐到4號位
p = 1/4*0 = 0

1/4 + 1/12 + 1/12 + 0 = 5/12

重點來了 ... 並非是1/2 ...
我覺得這個網友用數學歸納法是很有趣的想法 ...
但要是我沒記錯的話, 歸納法只要能任意用一個n 推論得到錯誤的答案, 則歸納法即是無
效的喔 ( 我離開高中10年了, 不知有無記錯, 以前老師也故意拿過"感覺"上歸納法可以
證明的題目來騙過我們 ... 規納法有個缺點就是, 當n=1,2,3等小數字時 ... 感覺好像
是正確, 然後大家就開始大書特書一番了 ...)

其實, 我還沒想出正確答案[雖然我心中猜測可能是(1/100)*1 + (99/100)*(1/99) = 2%]
不過 從"邏輯"上來思考 ... 我就認為1/2跟本就不可能 ...
當1號坐錯位置時 ... 100號怎麼可能會有高達49/99的機率坐到正確的位置上呢??
不要把問題想的太覆雜 .. 簡單想, 跟本不可能有這麼高的機率
下一篇我再把自己思考到的解法跟大家分享 ..

重點是 ... 由數學歸納法導出的1/2 應該是個錯誤的解法得到的錯誤的答案 ...
你跳入了數學歸納法 最大的漏洞了 ...

--