※ 另一種平靜 ※

無名要刪了...把之前打過覺得還有價值的文章轉備份到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! / (365ⁿ)(365-n)!

推導出來了!!!但這式子有複雜，所以來算個大概值吧~
by泰勒展開式，e^x = 1 + x/1 + x²/2! + x³/3! + ...

=> e^x ≒ 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%的機率!!!

＠＠＠＠＠＠＠＠＠