微軟面試題 - 推理遊戲

※ 引述《Nanan (安慶程二)》之銘言：
: 這是一個知道答案的証明方法，
: 似乎不能算是解法吧？
: 能不能給出一個簡單的解法呢？
: : 先從只有兩人看起
: : 很明顯最後一人坐對的機率是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....
這其實就可以是證明的解法了
用條件機率來看的話
各情況下100號坐在自己位置的機會

1號坐在100號的位置 1/100 * 0 (因為位置被坐走了)

1號坐在 99號的位置 99號坐在 1號位 → 100號一定坐在自己的位置
99號坐在100號位 → 100號一定不坐自己的位置
==> 1/100 * 1/2 (1 + 0)
==> 1/100 * 1/2

1號坐在 98號的位置 98號坐在 1號位 → 天下太平 99、100坐自己的位置
98號坐在 99號位 → 情況變成和上面一樣
此時100坐到自己的位置的機會是1/2
98號坐在100號位 → 100號一定不坐自己的位置
==> 1/100 * 1/3 (1 + 1/2 + 0)
==> 1/100 * 1/2

1號坐在 97號的位置 97號坐在 1號位 → 天下太平 98、99、100坐自己的位置
97號坐在 98號位 → 和98號的位子被1號坐走一樣
依上一段的證明100坐到自己的位置的機會是1/2
97號坐在 99號位 → 和99號的位子被1號坐走一樣
(因為98就會去坐自己的位置)
此時100坐到自己的位置的機會還是1/2
97號坐在100號位 → 100號一定不坐自己的位置
==> 1/100 * 1/4 (1 + 1/2 + 1/2 + 0)
==> 1/100 * 1/2

依此類推下去

1號坐在2號位置 100號坐到自己位置的機會也還是 1/100 * 1/2
1號坐在1號位置 100號坐到自己位置的機會則是 1/100 * 1

把這些通通加起來就是100號坐在自己位置上期望值：

1/100 (0 + 1/2 + 1/2 + 1/2 + 1/2 + 1/2......... + 1/2 + 1)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^供98個 (99 → 2)
==>1/100 * 100/2
==>1/2

--

這是我當初的解法

不過我認為一定有其它直觀的方式說明機會是1/2

--