坐飛機 - 拼圖

※ 引述《ddtddt (得)》之銘言：
: 一共有n個人上飛機，飛機上n個位置，每個人都有自己對應的位置。
: 但今天第一個人很迷糊，所以會隨機做任何一個位置。
: 後面的人如果自己的位置被別人坐了，則會隨機去坐剩下的位置，
: 如果自己的位置沒有被坐，則會做自己的位置。
: 請問，第n個人坐到自己位置的機率為?
: --
: 好像有看過但是/不到，與大家分享。
: --

: 推 yllan:1/2 09/19 19:22
: → ddtddt:give a simple proof 09/19 19:35
: 推 aa124816:一樓在n=1的情況就直接錯了= = 09/19 19:36
: 推 AlexCYW:第一個人一定是1/n 09/19 21:37
: → yllan:第一個人坐到k (1<k<n) 就等於把k 變成新的第一個人去坐n-1 09/19 21:53
: 推 yllan:然後就數學歸納法 09/19 21:56
: → yllan:n=1 時是 1 這終端狀況沒考慮到 orz 總之 n>1 時是 1/2 09/19 21:57
: 推 aa124816:但是第一個人有1/n的機會 會坐到第n個人的位置吶 09/19 22:23
: 推 AlexCYW:不太對..第二個人好像是(n-1)/n 09/19 22:46
: 推 arthurduh1:遞迴式是 P(n) = [1+(n-1)P(n-1)]/n 09/19 22:53
: → arthurduh1:解開會發現是 (n-1)/n 沒錯 09/19 22:53
: 推 yllan:等一下，第 n 個人意思應該是最後一個人吧？題目說 n 個座位 09/19 23:09
: 推 yllan:aa124816: 但也有 1/n 機會坐到第一個位置，這兩個就扯平啦 09/19 23:14
: 推 yllan:ㄟ，好像真的錯了！XD 09/19 23:29
: → yllan:ㄟ，應該沒錯啊…我來算算第 k 位置的看看 09/19 23:34
以下是一個不用數歸只用到簡單對應的做法

(幾乎沒有計算!)

考慮一個 n 號坐在 1 號上的坐法 X 設這坐法中坐在 n 號位置上的人是 k < n 號

和另一個除了 k 號坐 1 號 n 號坐 n 號外其他都和坐法 X 一樣的坐法 Y

顯然這兩個坐法唯一的差別就是 k 號選到 1 號或 n 號位

由題設 k 號決定坐這兩個位置的哪一個的機率都是 1/(n-k+1)

(k > 1 時因為輪到他時沒位置坐 剩下的是 k+1~n 號及 1 號共 n-k+1 個位置

k = 1 時則正好也是 1/n)

然後其他坐法因為選項一樣 選擇的機率自然一樣

因此坐法 X 和坐法 Y 的機率相等

然後我們可以把所有坐法都照這樣配對

(因為 n 號只可能坐在 1 號或 n 號位置

所以每一種坐法一定只屬於其中一種

然後調換 1 號位和 n 號位的人就是和它一組的坐法了)

其中 n 號坐在 n 號位的坐法正好每一組中都有一個

於是答案就是 1/2 了

--
推廣到其他人的話應該是這樣:

每個 k 號坐不到 k 號位的坐法和 n-k+1 個 k 號坐到 k 號位的坐法對應

分歧點在這個坐在 k 號位上的人選到哪個位置

坐到 k 號上一種 坐到 (k+1)~n 號或 1 號的坐法有 n-k+1 種

於是機率便是 (n-k+1)/(n-k+2) 了

--
◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　 　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘ 　 ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ 　　ＩＳＭ　 　　By-gamejye　￠|\ 　　▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏　　 　　　 　　　　█　　　 ⊿Δ 　　▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎　　　　　 　 　ハルヒ主義　　　 　　█▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　

--