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

※ 引述《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

--