Re: 小謎題-交換禮物(機率)

看板Inference (推理遊戲)作者wisdom7676時間16年前 (2008/12/18 05:12)推噓4(4推 0噓 4→)

留言8則, 5人參與討論串4/5 (看更多)

Q:假設有N個人交換禮物大家把禮物放在一堆抽禮物的時候可以拿到自己的禮物開獎的時候至少有一對人是互相拿到對方禮物的機率 A: 1 2 3 4 5 6 ... N 口口口口口口... 口上排為人下排空格填上數字則為拿到的禮物編號當然編號n的人他提供的禮物編號也給n 在N個空格填上1~N且不重複總共有N!種填法以下是題目的重點: 至少有一對人互相拿到對方禮物若是我強制指定其中兩個人互拿對方禮物則剩下N-2個人無論怎麼把剩下數字填入都一定符合"至少一對人互相拿到對方禮物" 因為那一對拿到彼此禮物的兩人早就已經被指定了剩下的人是否還有人彼此拿到對方的禮物已經無所謂因此剩下N-2個數字填入N-2個格子總共有(N-2)!種填法而最初的時候強制指定任兩人必須填入對方的數字則有C(N,2)種指定的方法因此符合條件的總共有[C(N,2)]x(N-2)! = N!/2種但是此N!/2種會重複計算同時有兩對以上互相拿到對方禮物的狀況也就是指定1和4號互拿對方禮物的時候5和8號可能也互拿但是指定5和8號互拿的時候又算了一次1和4互拿這兩種情況是同一件事情因此接下來就是要用排容原理把同時兩對人互拿的情況扣掉然後補回三對人同時互拿扣掉四對人同時互拿 $%@&#!^& 另外一種算法 P(至少有一對互拿對方禮物) = 100% - P(完全沒有人互拿對方禮物) 以上不管哪種算法都讓人不想算下去... 囧不過真的要算應該就是這樣算了吧最簡單解：叫電腦跑比較快 Edit:方法1試算化簡了一下答案就是上面那一篇給的公式兩對 => C(N,2)xC(N-2,2)x(N-4)!/2! = N!/[(2^2)x2!] k對 => C(N,2)xC(N-2,2)x...xC(N-2k)x(N-2k-2)!/k! = N!/[(2^k)x(k!)] 按排容原理補上正負號以後全部加起來最後就變成上一篇的公式因此機率 = 上篇公式/N! ※ 編輯: wisdom7676 來自: 122.120.40.166 (12/18 05:30) ※ 編輯: wisdom7676 來自: 122.120.40.166 (12/18 05:31)