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)
抽禮物的時候可以拿到自己的禮物
開獎的時候至少有一對人是互相拿到對方禮物的機率
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)
→ east101010:看來你離散學的很好~我叫老師幫你加分XD 12/18 05:47
→ wisdom7676:其實我沒學過離散..XD 高中時學的數學的應用而已 12/18 05:54
推 east101010:高中已經教過排容原理了嗎＠＠？ (驚) 12/18 06:00
推 chenyuhung:排容是什麼啊？我也是以為用高中學得來解就可以了 12/18 08:22
推 teves:高中本來就有教排容啊,看來你高中數學沒認真聽XD 12/18 10:32
→ east101010:囧~~~我以為這是大學才會提到的名詞~ 12/18 20:06
→ east101010:高中的時候應該已知道相關概念~但是或許不知道叫排容? 12/18 20:07
推 euleramon:這篇真是經典.. 就算只用到高中數學，也是很經典 12/18 23:09
All Comments