秘密聖誕老人之謎
你可能還記得，我在2023年10月26日的新聞通訊中寫過一篇關於他們在船上玩的遊戲節目的文章，名為「一擲千金」（Deal or No Deal）。在那個遊戲中，每個玩家都可以購買卡片，並獲得上台表演的機會。不過，每張卡片都有機會贏得安慰獎。安慰獎的玩法是，每張卡片上有20個箱子，箱子後面隨機放著20種不同的獎金。箱子的蓋子打開後即可打開。玩家獲勝的條件是，卡片上的獎金有多少與螢幕上隨機排列的相同獎金匹配。那篇新聞通訊中一個未解決的問題是，任意給定數量的匹配機率。
這個問題通常被稱為「秘密聖誕老人謎題」。它的名字來自聖誕派對上的一項活動：一群人（通常在同一間辦公室）從一頂寫有所有辦公室員工名字的帽子裡抽取一個名字，以此來決定要送禮物給誰。這個遊戲的一個問題是，你有可能抽到自己的名字，這很沒意思。平均而言，每個辦公室都會有一名玩家遇到這種情況，無論有多少員工。在本期簡報中，我試圖解答的一個問題是，沒有人抽到自己名字的確切機率是多少。
在我撰寫10月26日的電子報時，我並不清楚該如何計算，所以用泊松函數進行了估算。然而，這個問題一直困擾著我。我一直覺得估算在智力上非常不令人滿意。
首先，我編寫了一個計算機程序，循環遍歷所有可能的獎品順序，併計算每個排列對應的匹配數量。然而，如果是13個行李箱，程式大約需要一天時間才能遍歷完所有6,227,020,800種排列。如果是20個行李箱，則有2,432,902,008,176,640,000種排列，大約需要一百萬年才能遍歷完畢。
其次，我打開Excel，嘗試用遞歸的方式計算。結果比我想像的簡單得多。我一開始就應該這麼做。本通訊的其餘部分將解釋該方法背後的邏輯。
我假設讀者熟悉 Excel 的 combin(x,y) 函數，它表示從 x 中選擇 y 項的方式數。其確切公式為 x!/(y!*(xy)!)。
讓我們從一些明顯的案例開始。
- 1.有一位聖誕老人，顯然他有自己的名字。
- 2.有兩個聖誕老人，那麼兩個人都有自己名字或彼此名字的機率是 50%。
- 3.有三個聖誕老人，每個人有1種可能的名字。兩個人有0種可能的名字，因為如果他們這樣，最後一個人也會抽到自己的名字，因為這是唯一剩下的一個。一個人有3種可能的名字，分別是3個人各一個，另外兩個人互相有1種可能的名字。 3*1 = 1。3個名字的排序方式共有3!=6種。 0個人有自己名字的可能方式數就是剩下的：6-1-3 = 2。
到目前為止，我們的進展如下：
| 火柴 | 3個聖誕老人 | 2個聖誕老人 | 1 聖誕老人 |
| 3 | 1 | ||
| 2 | 0 | 1 | |
| 1 | 3 | 0 | 1 |
| 0 | 2 | 1 | 0 |
| 全部的 | 6 | 2 | 1 |
接下來，讓我們來談談 4 位聖誕老人。
4 場比賽：每個人總有一種方法可以得到自己的名字。
3個配對：除了一個人之外，其他人抽到自己的名字是不可能的。當除了一個人之外的其他人都匹配成功後，就只剩下一個人和他們的名字，而且他們必須相同。
2 人配對：從 4 個人中選出 2 人進行配對，一共有 combin(4,2)=6 種方法。另外 2 個人不匹配，只有 1 種方法，即透過抽籤的方式匹配對方的名字。
1 次配對：選擇與自己配對的聖誕老人有 4 種方式。從 3 個聖誕老人的情況可以看出，另外 3 個聖誕老人不匹配的情況有兩種，這是必然發生的。因此，1 次匹配的組合數為 4*2=8。
0 個匹配：同樣，我們從總排列中減去所有其他可能性。 4！ - 1 - 6 - 8 = 24-15=9。
現在我們位於：
| 火柴 | 4個聖誕老人 | 3個聖誕老人 | 2個聖誕老人 | 1個聖誕老人 |
| 4 | 1 | |||
| 3 | 0 | 1 | ||
| 2 | 6 | 0 | 1 | |
| 1 | 8 | 3 | 0 | 1 |
| 0 | 9 | 2 | 1 | 0 |
| 全部的 | 24 | 6 | 2 | 1 |
接下來，讓我們來了解 5 位聖誕老人。
5 場比賽：每個人總有一種方法可以得到自己的名字。
4 場比賽：不可能，原因在 4 個聖誕老人的案例中有所說明。
3 次配對：從 5 個人中選擇 3 個人進行配對，共有 combin(5,3)=10 種方法。另外兩個人互相知道對方名字的方法只有 1 種。因此，3 次配對共有 10 種方法。
2 人配對：從 5 個人中選出 2 人進行配對，一共有 combin(5,2)=10 種方式。其餘 3 人，有兩種不匹配的方式，這一點我們從 3 個聖誕老人的案例中可以看出。因此，2 人配對共有 10*2=20 種方式。
1 次配對：選擇與自己配對的聖誕老人有 5 種方式。從 4 個聖誕老人的情況可以看出，其他 4 個聖誕老人不匹配的情況有 9 種，這是必然發生的。因此，1 次匹配的組合數為 5*9=45。
0 個匹配：同樣，我們從總排列中減去所有其他可能性。 5！ - 1 - 0 - 10 - 20 - 45 = 44。
現在我們位於：
| 火柴 | 5個聖誕老人 | 4個聖誕老人 | 3個聖誕老人 | 2個聖誕老人 | 1個聖誕老人 |
| 5 | 1 | ||||
| 4 | 0 | 1 | |||
| 3 | 10 | 0 | 1 | ||
| 2 | 20 | 6 | 0 | 1 | |
| 1 | 45 | 8 | 3 | 0 | 1 |
| 0 | 四十四 | 9 | 2 | 1 | 0 |
| 全部的 | 120 | 24 | 6 | 2 | 1 |
按照同樣的邏輯，我們得到最多 10 位聖誕老人的下表。
| 墊。 | 10個聖誕老人 | 9個聖誕老人 | 8個聖誕老人 | 7個聖誕老人 | 6個聖誕老人 | 5個聖誕老人 | 4個聖誕老人 | 3個聖誕老人 | 2個聖誕老人 | 1個聖誕老人 |
| 10 | 1 | |||||||||
| 9 | 0 | 1 | ||||||||
| 8 | 45 | 0 | 1 | |||||||
| 7 | 240 | 三十六 | 0 | 1 | ||||||
| 6 | 1890 | 168 | 二十八 | 0 | 1 | |||||
| 5 | 11088 | 1134 | 112 | 21 | 0 | 1 | ||||
| 4 | 55650 | 5544 | 630 | 70 | 15 | 0 | 1 | |||
| 3 | 222480 | 22260 | 2464 | 315 | 40 | 10 | 0 | 1 | ||
| 2 | 667485 | 66744 | 7420 | 924 | 135 | 20 | 6 | 0 | 1 | |
| 1 | 1334960 | 133497 | 14832 | 1855 | 264 | 45 | 8 | 3 | 0 | 1 |
| 0 | 1334961 | 133496 | 14833 | 1854 | 265 | 四十四 | 9 | 2 | 1 | 0 |
| 全部的 | 3628800 | 362880 | 40320 | 5040 | 720 | 120 | 24 | 6 | 2 | 1 |
請注意，0 個匹配和 1 個匹配的排列數總是相差無幾。如果聖誕老人數量為偶數，則 0 個匹配的排列數比 1 個匹配的排列數多一個；如果聖誕老人數量為奇數，則 0 個匹配的排列數比 1 個匹配的排列數少一個。如果我們接受這種情況總是成立（事實也確實如此），那麼我們可以快速確定 11 個或更多聖誕老人的 0 個匹配的排列數，如下所示。
11個聖誕老人：對於一個匹配，有11個聖誕老人需要匹配，而其他10個不匹配的情況，則有133,496種方式。因此，1個匹配的排列數為11*133,496 = 14,684,571。由於11是奇數，因此0個匹配的排列數少一個，即14,684,571 - 1 = 14,684,570。
12個聖誕老人：對於一個匹配，有12個聖誕老人需要匹配，而其他11個不匹配的情況，則有14,684,570種方式。因此，1個匹配的排列數為12*14,684,570 = 176,214,840。由於12是偶數，因此0個匹配的排列數多一個，即176,214,840 + 1 = 176,214,841。
繼續同樣的邏輯，這裡是 1 到 20 個聖誕老人的 0 個匹配的排列數，包括總排列數和機率。
| 聖誕老公公 | 0 場比賽 | 總排列 | 可能性 |
| 20 | 895,014,631,192,902,000 | 2,432,902,008,176,640,000 | 0.367879 |
| 19 | 44,750,731,559,645,100 | 121,645,100,408,832,000 | 0.367879 |
| 18 | 2,355,301,661,033,950 | 6,402,373,705,728,000 | 0.367879 |
| 17 | 130,850,092,279,664 | 355,687,428,096,000 | 0.367879 |
| 16 | 7,697,064,251,745 | 20,922,789,888,000 | 0.367879 |
| 15 | 481,066,515,734 | 1,307,674,368,000 | 0.367879 |
| 14 | 32,071,101,049 | 87,178,291,200 | 0.367879 |
| 十三 | 2,290,792,932 | 6,227,020,800 | 0.367879 |
| 12 | 176,214,841 | 479,001,600 | 0.367879 |
| 11 | 14,684,570 | 39,916,800 | 0.367879 |
| 10 | 1,334,961 | 3,628,800 | 0.367879 |
| 9 | 133,496 | 362,880 | 0.367879 |
| 8 | 14,833 | 40,320 | 0.367882 |
| 7 | 1,854 | 5,040 | 0.367857 |
| 6 | 265 | 720 | 0.368056 |
| 5 | 四十四 | 120 | 0.366667 |
| 4 | 9 | 24 | 0.375000 |
| 3 | 2 | 6 | 0.333333 |
| 2 | 1 | 2 | 0.500000 |
| 1 | 0 | 1 | 0.000000 |
請注意，0場比賽的機率是如何接近0.367879的。這個數字看起來很熟悉嗎？沒錯！它是1/e。我現在可以寫一本關於泊松估計的小冊子了，但這份簡報已經太長了。想了解更多，我推薦史丹佛·黃（Stanford Wong）的《敏銳體育博彩》（Sharp Sports Betting），這本書解釋瞭如何使用泊松函數分析超級盃的命題投注。
讓我們回到 Deal or No Deal 遊戲，它相當於 20 個聖誕老人的情況。我們想知道 0 到 20 個匹配的組合數。
20 位聖誕老人中，m 個匹配項的組合數為 combin(20,m)*z(m)，其中 z(m)=m 位聖誕老人中 0 個匹配項的組合數。下表使用該方法計算了 20 位聖誕老人中，0 到 20 個匹配項的組合數。
| 火柴 | 排列 | 可能性 |
| 20 | 1 | 0.000000 |
| 19 | - | 0.000000 |
| 18 | 190 | 0.000000 |
| 17 | 2,280 | 0.000000 |
| 16 | 43,605 | 0.000000 |
| 15 | 682,176 | 0.000000 |
| 14 | 10,271,400 | 0.000000 |
| 十三 | 143,722,080 | 0.000000 |
| 12 | 1,868,513,010 | 0.000000 |
| 11 | 22,421,988,160 | 0.000000 |
| 10 | 246,642,054,516 | 0.000000 |
| 9 | 2,466,420,377,200 | 0.000001 |
| 8 | 22,197,783,520,770 | 0.000009 |
| 7 | 177,582,268,088,640 | 0.000073 |
| 6 | 1,243,075,876,659,240 | 0.000511 |
| 5 | 7,458,455,259,939,930 | 0.003066 |
| 4 | 37,292,276,299,704,500 | 0.015328 |
| 3 | 149,169,105,198,817,000 | 0.061313 |
| 2 | 447,507,315,596,451,000 | 0.183940 |
| 1 | 895,014,631,192,902,000 | 0.367879 |
| 0 | 895,014,631,192,902,000 | 0.367879 |
| 全部的 | 2,432,902,008,176,640,000 | 1.000000 |
如果您將這些機率與我在2023 年 10 月 26 日的新聞通訊中的泊松估計進行比較，您會發現所有人都同意提供的六位小數，這表明泊松函數和數字 e 的有用性。
下週，我計劃詳細闡述這個主題，並展示任意數量聖誕老人的排列數的一般公式。