微軟面試題 - 推理遊戲

※ 引述《cutesogo (胖老鼠)》之銘言：
: 很有趣 ... 不過, 請問當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 (可能很多人不需要看到這麼詳細的解答, 我只是想說的完整)

以下畫樹狀圖 其中 x->y 表示 人x坐到位置y :

2->1 後面自然3->3 4->4
/
/ 3->1 後面自然4->4
1->2 --< 2->3 <
\ 3->4 後面自然4->1
\
2->4 後面自然3->3 4->1

題設2->1 2->3 2->4機率相同 <--注意這一點

故得2->1分支機率1/3 2->4分支機率1/3

在2->3分支中 題設3->1 3->4機率相同

故得3->1分支機率(1/3)*(1/2)=1/6 3->4分支機率(1/3)*(1/2)=1/6

故得4->4之機率(在1->2的條件下)為(1/3)+(1/6)=1/2

: 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 應該是個錯誤的解法得到的錯誤的答案 ...
: 你跳入了數學歸納法 最大的漏洞了 ...

--
"LPH" is for "Let Program Heal us"....

--