題目的描述是：有100個人上飛機，本應該按照各自的座位1-100號坐下，但其中有一個是瘋子
瘋子的行為是：隨機選擇一個座位坐下。
而正常人的行為是： 盡量做自己的座位，如果自己的座位被占了，就隨機選一個座位。
問題是：最後一個人坐在自己的位置的概率是多大。
分析：
這個題目裡瘋子登機號也是隨機的，我們可以先簡化問題成，假設有n個人，瘋子是第一個登機的，求出最後一個人坐在自己位置的概率。
我們可以從小規模分析這個問題
n = 2， P(2) = 0.5
n = 3
如果瘋子做在自己的位置S1上，那麼最後一個人肯定坐在自己的座位上 概率是 1/3
如果瘋子坐在第二個人S2上，那麼空余座位是 S1, S3，現在第二個人登機的時候，我們可以把他理解成瘋子，他本該有的座位是S1, 所以問題變成了 n = 2的子問題
這個時候的概率是 1/3 * P(2)
如果瘋子直接坐在最後一個人的位置上，那麼最後一個人坐在自己座位概率就是0.
則 P(3) = 1/3 + 1/3 * P(2) + 0 = 1/2.
n = 4
類似的，如果瘋子直接坐在自己的位置上，最後一個人坐在自己位置的概率 概率是 1/4
如果坐在 第二個人位置上， 最後一個人坐在自己的概率是 1/4 * P(3)
如果坐在第三個人的位置上，這個時候可能有點特殊，瘋子登機後，到第三個之間還有第二個人，第二個的位置沒有被占，所以他一定正常登機，這個時候當第三個人登機的時候，問題變成， 第三個人是瘋子，他應該有的座位是S1，變成P(2). 所以概率是 1/4 * P(2)
如果直接坐在最後一個人座位上，那麼概率是0.
計算得知 P(4) = 1/2
這樣我們可以用歸納法，假設 1-n個人的時候，P(n) = 1/2
然後我們現在求 P(n+1)
根據我們上面的求法有公式
P(n+1) = 1/(n+1) + ∑i(from 2 to n) P(n+1 - i) / (n+1) + 0 = 1/(n+1) + (n-2+1)/((n+1) 2)+ 0 = (n+1)/2(n+1) = 1/2
歸納假設成立。
所以最後的概率是 1/2.
----------------------------------------------------------------------------------------------
不過現在還不是我們的問題，我們的問題中瘋子可以任意次序登機，不過問題都可以歸一為一個，因為瘋子前面的所有人都會正常做自己的座位，
如果瘋子第i個登機， 問題就是 P(100 - i + 1) 所有的概率都是 1/2, 所以最後總的概率也是 1/2.
----------------------------------------------------------------------------------------------
不過面試現場沒有證明出來，有點悲劇的。 sigh！
