無名要刪了...把之前打過覺得還有價值的文章轉備份到pixnet上!!XD


@@@Thm. @@@

在一間教室裡
隨便抓23個人出來,有超過50%的機率可以找到兩個人的生日是一樣的。
隨便抓57個人出來,有近乎99%的機率可以找到兩個人的生日是一樣的。
隨便抓366個人出來,可到達100%的機率可以找到。(by P.H.) 

@@@@@@@@@


@@@ Goals @@@

知道這個理論有啥好處的?
用於搭訕 --- 多一個嘴砲的知識!?
用於解密 --- 應該沒幾個人有美國時間去寫一套軟體來猜MD5的吧= =?

@@@@@@@@@


@@@ Proof @@@

假設此問題推廣成...
隨便抓n個人出來,有p(n)的機率可以找到兩個人的生日是一樣的。
=> ~p(n)為找不到兩個人的生日是一樣的。( i.e., ~p(n)=1-p(n) )

我們針對~p(n)來下手來考慮下面情況...
in order,我們抓出第k人時,生日不同的機率為
k=1時: 365/365
k=2時: 354/365 ( 剩364種不同的生日可以選 )
...
k=n時: (365-n+1)/365


=> ~p(n) = 365/365 * 364/365 * ... * (365-n+1)/365 = 365! / (3656^k)(365-n)!


=> p(n) = 1 - ~p(n) = 1 - 365! / (365n)(365-n)!

推導出來了!!!但這式子有複雜,所以來算個大概值吧~
by泰勒展開式,ex = 1 + x/1 + x2/2! + x3/3! + ...

=> ex ≒ 1 + x

再將~p(n)的式子簡化一下


~p(n) 


= 365/365 * 364/365 * ... * n/365


= (1 - 0/365) * (1 - 1/365) * ... * (1 - (n-1)/365)


≒ e(-0/365)+(-1/365)+...+(-(n-1)/365)


= e-(n-1)n/730


≒ e-n2/730

所以我們得出一個簡單的式子...
p(n) = 1- ~p(n) ≒ 1 - e -n2 / 730

n=23可知,抓出23個人,有兩個相同生日的機率為p(n) ≒ 1 - 0.48449 = 0.51551
=> 高達超過50%的機率!!!

n=57可知,抓出57個人,有兩個相同生日的機率為p(n) ≒ 1 - 0.01167 = 0.98833
=> 高達近乎99%的機率!!!

@@@@@@@@@

文章標籤
創作者介紹
創作者 Perry 的頭像
Perry

※ 另一種平靜 ※

Perry 發表在 痞客邦 留言(0) 人氣()