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

看板Inference (推理遊戲)作者euleramon (Holy Knight)時間16年前 (2008/12/21 13:23)推噓1(1推 0噓 1→)

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

※ 引述《wisdom7676 ()》之銘言： : 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!)] ^^^^^A ^^^^^^B ＊有點小bug，訂正一下： A應改為 N-2k+2，即 A = N-2k+2 B應改為 N-2k，因為 B = A-2 = N-2k ＊LPH66 po的公式化簡如下，即為機率公式 floor(n/2) (-1)^k 　　　　－ Σ -------- k=1 2^k * k! ＊附上matlab code，畫圖，橫軸n為人數，縱軸p為機率。(機率趨近0.393...) n=linspace(1,100, 100); tmp=0; for k = 1:100 tmp = tmp + (-1)^k/2^k/factorial(k); p(1,k) = -tmp; end plot(n,p); ＊附上c# code，用來算機率 using System; namespace SwithPresents { class Program { static void Main() { Console.WriteLine("請輸入人數(不要超過100，太大會爆掉)"); string numberStr = Console.ReadLine(); long number = Int32.Parse(numberStr); double possibility = 0; // 簡化版 for (long k = 1; k <= Math.Floor(number / 2.0); k++) { possibility += -1 * Math.Pow(-1, k) / Math.Pow(2, k) / (double)factorial(k); } Console.WriteLine("{0}", possibility); } static long factorial(long t) { if (t == 1) return t; else return t * factorial(t - 1); } } } ＊本來想寫個亂數模擬程式，今天太忙了，心血來潮再來補上 orz 以上有錯請指正" : 按排容原理補上正負號以後全部加起來最後就變成上一篇的公式 : 因此機率 = 上篇公式/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 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.120.13.162