Re: 小謎題-交換禮物(機率) - 推理遊戲

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)