a660: 春香信仰
標籤 :
通過比率 : 73人/76人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-09-07 01:34

內容

我在這裡先聲明我不是偶大廚,但這裡有人死不承認自己是偶大廚

還一直發些奇怪的訊息

因此此題作為判斷是否具有春香信仰的題目,只有具備真正春香信仰的答題者才能一發AC此題。

---

這邊先提一下生日問題

生日問題是指,如果在一個房間要多少人,則兩個人的生日相同的機率要大於50%? 答案是23人。 這就意味著在一個典型的標準小學班級(30人)中,存在兩人生日相同的可能性更高。對於60或者更多的人,這種機率會大於99%。這個問題有時也被稱做生日悖論,但從引起邏輯矛盾的角度來說生日悖論並不是一種悖論,它被稱作悖論只是因為這個數學事實與一般直覺相牴觸而已。大多數人會認為,23人中有2人生日相同的機率應該遠遠小於50%。計算與此相關的機率被稱為生日問題,在這個問題之後的數學理論已被用於設計著名的密碼攻擊方法:生日攻擊。

可以把生日悖論理解成一個盲射打靶的問題。對於一個23人的房間,先考慮問題的補集:23人生日兩兩不同的機率是多少?為此,可以讓23個人依次進入,那麼每個人生日都與其他人不同的機率依次是1,364/365,363/365,362/365,361/365,等等。先進入房間的這些人生日兩兩不同的機率是很大的,比如說前面5個是1×364/365×363/365×362/365×361/365=97.3%。而對於最後進入房間的幾個人情況就完全不同。最後幾個人進入房間並且找不到同生日者的機率是... 345/365,344/365,343/365。可以把這種機率看成對一張靶的盲射:靶上有365個小格,其中有17個左右是黑格,其餘是白格。假設每槍必中靶並且分布符合幾何概型的話,那麼連續射12槍左右任何一發都沒有擊中黑格的機率(投射於房間裡的人生日都兩兩不同)是多少呢?想必大家立即會感覺到這個機率十分微小。

理解生日悖論的關鍵,在於考慮上述「依次進入房間」模型中最後幾個進入房間的人「全部都沒碰到相同生日的人」機率有多大這件事情。

那問題來了,假設有一群春香廚跟春香在同一個房間裡,至少要有多少個春香廚才能使這群春香廚中有超過一半的機率存在一個春香廚的生日跟春香生日同一天?當你看完上一段以為答案是23人的時候,那你就大錯特錯了,生日問題之所以被稱之生日悖論就在此,大多人第一次看到生日問題都會覺得不可思議,原因就在於會把問題轉換成至少要有多少除了我以外的人的生日與我同天生日的機率超過50%,這就跟至少要有多少個春香廚才能使一群春香廚中有超過一半的機率存在一個春香廚的生日跟春香生日同一天的問題一樣,我們先不管至少要有多少個春香廚才能使一群春香廚中有超過一半的機率存在一個春香廚的生日跟春香生日同一天的問題,這題只是想知道至少要有多少個春香廚才能使一群春香廚中有超過一半的機率存在一個春香廚的生日跟春香生日同一天的問題的那個人的生日,不過這裡再提一下機率估計

假設有n個人在同一房間內,如果要計算有兩個人在同一日出生的機率,在不考慮特殊因素的前提下,例如閏年、雙胞胎,假設一年365日出生機率是平均分布的(現實生活中,出生機率不是平均分布的)。計算機率的方法是,首先找出p(n)表示n個人中,每個人的生日日期都不同的機率。假如n > 365,根據鴿巢原理其機率為0,假設n ≤ 365,則機率為

\bar p (n) = 1 \cdot \left(1-\frac{1}{365}\right)\cdot \left(1-\frac{2}{365}\right)  \cdots \left(1-\frac{n-1}{365}\right) =\frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdots \frac{365-n+1}{365}

因為第二個人不能跟第一個人有相同的生日(機率是364/365),第三個人不能跟前兩個人生日相同(機率為363/365),依此類推。用階乘可以寫成如下形式

{ 365! \over 365^n (365-n)! }

p(n)表示n個人中至少2人生日相同的機率

 p (n) = 1 - \bar p (n)=1 - { 365! \over 365^n (365-n)! }
n≤365,根據鴿巢原理,n大於365時機率為1。

當n=23發生的機率大約是0.507。

其他數字的機率用上面的算法可以近似的得出來:

注意所有人都是隨機選出的:作為對比,q(n)表示房間中有n+1個人,當中與特定人(比如你)有相同生日的機率:

{\displaystyle q(n+1)=1-\left({\frac {364}{365}}\right)^{n}}
當n = 22時機率只有大約0.059,約高於十七分之一。如果n個人中有50%機率存在某人跟你有相同生日,n至少要達到253。注意這個數字大大高於365/2 = 182.5;究其原因是因為房間內可能有些人生日相同。

那到底至少要有多少個春香廚才能使一群春香廚中有超過一半的機率存在一個春香廚的生日跟春香生日同一天的問題的答案是甚麼?想必大家應該都知道了吧,答案就是253吧(?)

輸入說明

無輸入

輸出說明

請依題目要求輸出

範例輸入
無輸入
範例輸出

										
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (100%): 1.0s , <1K
提示 :
標籤:
出處:
[管理者:
fdhs108_38002 (NULL)
]


編號 身分 題目 主題 人氣 發表日期
1339
whitebearOuO (ʕ •ᴥ•ʔ)
a660
好了啦偶大廚
228 2021-10-04 12:08
1093
fdhs109_69 (弓長永文武偶大廚)
a660
海龜偶大廚
319 2021-09-13 11:57
1067
fdhs107_KonChin... (konchin)
a660
偶大廚
258 2021-09-08 16:24
1066
Seaturtle (從零開始的旦旦解題人生(我不是偶大廚!))
a660
290 2021-09-07 02:04