瘋子坐飛機

這是其中一條我遇過最精彩、最神奇的數學題，問題如下：有一班航機，有100個座位，由1-100編好。1號乘客坐1號座位，2號乘客坐2號座位，3號乘客坐3號座位，如此類推，100號乘客坐100號座位。現在乘客由1-100號順序慢慢進座，可惜1號乘客是個瘋子，他會隨機選擇一個座位。其他乘客如果見到自己的座位仍是空的，他們就會坐進去；但如果他們見到自己的座位已被其他人坐了，他們就會在剩下的座位中隨機選擇一個坐進去。試問到最後，100號乘客坐到100號座位的機會有多大？

這題目可不簡單啊，史丹福當年可是想了一個小時的車程才想得到的。這是史丹福當年的思路：

最初我想嘗試認真地計conditional probability，把所有可能列出，最後當然失敗了。於是我就嘗試由簡單的例子著手，希望找到點頭緒。

假如只有2個乘客、2個座位，2號乘客坐到2號座位的機會當然是1/2。

假如只有3個乘客、3個座位，那所有的可能性如下：

	1號座位	2號座位	3號座位
情況1	1	2	3
情況2	2	1	3
情況3	3	1	2
情況4	3	2	1

3號乘客坐到3號座位的機會都是1/2。

假如只有4個乘客、4個座位，那所有的可能性如下：

	1號座位	2號座位	3號座位	4號座位
情況1	1	2	3	4
情況2	2	1	3	4
情況3	3	1	2	4
情況4	4	1	2	3
情況5	4	1	3	2
情況6	3	2	1	4
情況7	4	2	1	3
情況8	4	2	3	1

4號乘客坐到4號座位的機會依然是1/2。

Hmmm，2個座位、3個座位、4個座位的情況都是1/2。那看情況，如無意外，100號乘客坐到100號座位的機會都應該是1/2了吧。但如何證明呢?

很熟口熟臉吧? 從2推到3，從3推到4，從4推到5... 一直推到100，推到無限。這類問題當然又要用到我們中學時期A Maths及Pure Maths的老朋友，最所向披靡、最無所不能的萬能key ── mathematical induction (MI)。

如果你夠心水清的話，在n個乘客、n個座位的情況下，如果第1號乘客坐了第r個座位，第2號乘客就會坐第2個座位，第3號乘客就會坐第3個座位… 第r-1號乘客就會坐第r-1個座位，由於第r個座位已被第1號乘客坐了，第r號乘客就會隨機選擇一個座位。這時候第r號乘客就變成了那位瘋子，這個情況就可以簡化成只有n-r+1個乘客、n-r+1個座位的情況。

現在讓我formally，很嚴謹地proof多一次：

Let P(n) be the proposition “in the situation with n passengers and n seats, the probability of the n-th passenger seating on the n-th seat is 1/2”

When n=2, P(n) is obviously true.

Assume P(2), P(3), P(4), … P(k) is true for some positive integers k.

When n=k+1,

If the 1^st passenger sits on the 1^st sit, the probability of the (k+1)-th passenger seating on the (k+1)-th seat is 1.

If the 1^st passenger sits on the (k+1)-th sit, the probability of the (k+1)-th passenger seating on the k+1-th seat is 0.

If the 1^st passenger sits on the r-th sit, where r =/= 1 or k+1, the situation is equivalent to the situation of n-r+1 passengers and n-r+1 seats (from the above discussion), and the required probability is 1/2 (By P(n-r+1))

So the probability of the (k+1)-th passenger seating on the (k+1)-th seat = 1/(k+1) * 1 + 1/(k+1) * 0 + (k-1)/(k+1) * 1/2 = 1/2

Therefore P(k+1) is also ture.

By mathematical induction, P(n) is true for all positive integers n.

所以100個乘客機會是1/2，1000個乘客機會是1/2，10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000個乘客機會仍然是1/2。

呵呵，這題問題神奇及精彩的地方，在於竟然可以在你完全意想不到的場合用到老朋友mathematical induction，太溫馨了。