2016年2月4日 星期四

瘋子坐飛機

這是其中一條我遇過最精彩、最神奇的數學題,問題如下:有一班航機,有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

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

很熟口熟臉吧? 2推到3,從3推到4,從4推到5... 一直推到100,推到無限。這類問題當然又要用到我們中學時期A MathsPure 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 1st passenger sits on the 1st sit, the probability of the (k+1)-th passenger seating on the (k+1)-th seat is 1.
If the 1st 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 1st 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/21000個乘客機會是1/210000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000個乘客機會仍然是1/2


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

沒有留言:

張貼留言