シークレットサンタパズル
2023年10月26日のニュースレターで、船上で行われた「ディール・オア・ノー・ディール」というゲームショーについて書いたことを覚えているかもしれません。このゲームでは、プレイヤーは誰でもカードを購入してステージでプレイすることができました。しかし、どのカードにも特典賞を獲得するチャンスがありました。特典賞の仕組みは、各カードに20個のスーツケースが付いており、その20個の箱の裏に20種類の賞金がランダムに配置されていました。スーツケースはフラップを持ち上げて開けます。プレイヤーの勝敗は、自分のカードに記載されている賞品が、画面に表示される同じ賞品のランダムシャッフルとどれだけ一致したかによって決まります。このニュースレターで未解決だった問題は、任意の数の賞品が一致する確率でした。
この問題は、一般的に「シークレットサンタパズル」と呼ばれています。クリスマスパーティーで、通常は同じオフィスにいるグループが、全員の帽子の中から名前を1人ずつ選び、誰にプレゼントを贈るかを決めるというアクティビティにちなんで名付けられました。このゲームの問題点は、自分の名前を引いてしまう可能性があることです。これは決して楽しいことではありません。平均すると、従業員の数に関係なく、どのオフィスでも1人のプレイヤーに同じことが起こります。このニュースレターで私が答えようとしている疑問の一つは、誰も自分の名前を引かない確率がどれくらいなのかということです。
10月26日のニュースレターを執筆した当時は、数学的な計算方法が全く分からなかったので、ポアソン関数を使って推定しました。しかし、それ以来ずっとこの問題が私を悩ませています。推定というものは、知的に納得のいくものではないと感じてきたからです。
まず、賞品のあらゆる組み合わせを巡回し、それぞれの組み合わせで一致する数を数えるコンピュータプログラムを作成しました。しかし、スーツケースが13個の場合、6,227,020,800通りの組み合わせをすべて巡回するのに約1日かかりました。スーツケースが20個の場合、2,432,902,008,176,640,000通りの組み合わせがあり、巡回には約100万年かかります。
次に、Excelで再帰的に計算してみました。予想以上に簡単でした。最初からこの方法でやっておくべきでした。このニュースレターの残りの部分では、そのアプローチの背後にあるロジックを説明します。
読者の皆様はExcelのcombin(x,y)関数をご存知かと思います。これは、x個の項目からy個の項目を選ぶ方法の数を求める関数です。正確な式はx!/(y!*(xy)!)です。
まずは明らかな例から始めましょう。
- 1.サンタが一人だけなら、そのサンタに独自の名前が付けられるのは明らかです。
- 2.サンタが 2 人いる場合、両方が自分の名前またはお互いの名前を得る確率は 50/50 です。
- 3.サンタが3人いる場合、全員が自分の名前をもらう方法は1通りです。2人が自分の名前をもらう方法は0通りです。なぜなら、2人が自分の名前をもらうと、最後の1人だけが残った名前を引いてしまうからです。1人が自分の名前をもらう方法は3通り（3人それぞれ1通りずつ）、残りの2人がお互いの名前をもらう方法は1通りです。3*1 = 1です。3人の名前の順番は全部で3!=6通りあります。0人が自分の名前をもらう方法は、残りの6通り、つまり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 つの一致: 誰もが自分の名前を取得する方法が常に 1 つあります。
3人が同じ名前を引く：1人を除いて全員が同じ名前を引くことは常に不可能です。1人を除いて全員が同じ名前を引くと、残るのは1人だけになり、その名前は必ず同じになります。
2人が一致する場合：4人のうち2人を選んで一致する組み合わせは、combin(4,2)=6通りあります。残りの2人については、お互いの名前を引くという組み合わせが1通りあります。
1つ一致する場合：自分と一致するサンタを選ぶ方法は4通りあります。サンタが3人いる場合からわかるように、他の3人のサンタが一致しない方法は2通りあり、これは必ず起こるはずです。したがって、1つ一致する場合の組み合わせは4×2=8通りです。
一致なし: ここでも、合計順列から他のすべての可能性を差し引きます。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 つの一致: 誰もが自分の名前を取得する方法が常に 1 つあります。
4 つの一致: 4 人のサンタのケースで述べた理由により、不可能です。
3人が一致する場合：5人のうち3人が一致する場合、combin(5,3)=10通りの方法があります。残りの2人がお互いの名前を取得する方法は1通りです。つまり、3人が一致する場合、10通りの方法があります。
2人が一致する場合：5人のうち2人を選ぶ方法はcombin(5,2)=10通りあります。残りの3人については、サンタ3人の場合と同様に、一致しない方法が2通りあります。つまり、2人が一致する場合、10*2=20通りあります。
1マッチ：自分と一致するサンタを選ぶ方法は5通りあります。4人のサンタの場合からわかるように、他の4人のサンタが一致しない組み合わせは9通りあり、これは必然的に起こります。つまり、1マッチの組み合わせは5×9=45通りです。
一致なし: ここでも、合計順列から他のすべての可能性を差し引きます。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 | 44 | 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 | 36 | 0 | 1 | ||||||
| 6 | 1890 | 168 | 28 | 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 | 44 | 9 | 2 | 1 | 0 |
| 合計 | 3628800 | 362880 | 40320 | 5040 | 720 | 120 | 24 | 6 | 2 | 1 |
0個と1個の一致の組み合わせの数は、常に1個以内であることに留意してください。0個の一致の組み合わせの合計は、サンタの数が偶数の場合は1個多く、奇数の場合は1個少なくなります。これが常に当てはまると仮定すれば（実際そうですが）、11個以上のサンタの場合の0個の一致の組み合わせの数は、以下のように簡単に求めることができます。
11人のサンタ：10人のサンタの場合、1つの一致に対して、一致するサンタは11人おり、残りの10人が一致しない組み合わせは133,496通りあります。したがって、1つの一致に対する順列の数は11×133,496 = 14,684,571通りです。11は奇数なので、一致しないサンタが0人の場合の順列の数は1つ少なく、14,684,571 - 1 = 14,684,570通りとなります。
12人のサンタ：1つの一致に対して、一致するサンタは12人おり、残りの11人が一致しない組み合わせは14,684,570通りあります（11人のサンタの場合）。したがって、1つの一致に対する順列の数は12×14,684,570 = 176,214,840通りです。12は偶数なので、一致しない組み合わせの数は1つ多く、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 |
| 13 | 2,290,792,932 | 6,227,020,800 | 0.367879 |
| 12 | 1億7621万4841 | 4億7900万1600 | 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 | 44 | 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です。ポアソン推定値についてもう少し詳しく知りたい方は、スタンフォード・ウォン著の『Sharp Sports Betting』をお勧めします。この本では、ポアソン関数を用いてスーパーボウルのプロポジションベットを分析する方法が解説されています。
サンタが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 |
| 13 | 1億4372万2080円 | 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 日のニュースレターに掲載した私のポアソン分布の推定値と比較すると、すべて 6 桁の小数点以下まで一致していることがわかります。これは、ポアソン関数と数値 e の有用性を示しています。
来週、私はこのトピックについて詳しく説明し、任意の数のサンタの組み合わせの数に関する一般的な公式を示す予定です。