Загадка Тайного Санты

Возможно, вы помните мой рассказ от 26 октября 2023 года о телеигре «Сделка или нет», которая проходила на корабле. В этой игре каждый игрок мог купить карточки, дающие шанс выйти на сцену. Однако каждая карточка давала шанс выиграть утешительные призы. Утешительные призы представляли собой 20 чемоданчиков, за которыми случайным образом располагались 20 различных денежных призов. Чемоданы открывались поднятием клапанов. Победа зависела от того, сколько призов на его карточке совпадало со случайным набором одинаковых призов, отображаемых на экране. Нерешенной проблемой из того выпуска был вопрос о вероятности любого заданного количества совпадений.

Эта задача обычно называется «Тайный Санта». Название происходит от рождественской игры, где группа людей, обычно из одного офиса, вытаскивает из шляпы имена всех сотрудников офиса, чтобы определить, кому подарить подарок. Проблема игры в том, что есть вероятность вытащить своё собственное имя, что совсем не весело. В среднем, это произойдёт с одним игроком в каждом офисе, независимо от количества сотрудников. Один из вопросов, на который я пытаюсь ответить в этом информационном бюллетене, — это точная вероятность того, что никто не вытащит своё собственное имя.

Когда я писал новостную рассылку от 26 октября, я точно не знал, как произвести расчеты, поэтому использовал функцию Пуассона для приблизительных оценок. Однако эта проблема не даёт мне покоя с тех пор. Я всегда считал приблизительные оценки крайне неудовлетворительными с интеллектуальной точки зрения.

Сначала я написал компьютерную программу, которая перебирала все возможные порядки призов и подсчитывала количество совпадений в каждой перестановке. Однако, имея 13 чемоданов, этой программе потребовался примерно день, чтобы перебрать все 6 227 020 800 перестановок. 20 чемоданов содержали бы 2 432 902 008 176 640 000 перестановок, на перебор которых ушло бы около миллиона лет.

Во-вторых, я зашёл в Excel и попытался решить задачу рекурсивно. Это оказалось намного проще, чем я ожидал. Мне следовало сделать это именно так с самого начала.В оставшейся части этого информационного бюллетеня будет объяснена логика, лежащая в основе такого подхода.

Предполагаю, что читатель знаком с функцией Excel combin(x,y), которая вычисляет количество способов выбрать y элементов из x. Точная формула выглядит так: x!/(y!*(xy)!).

Начнём с нескольких очевидных случаев.

1. 1. Поскольку у Санта-Клауса всего один, очевидно, что ему дают собственное имя.
2. 2. Если Санта-Клаусов два, то есть 50/50 шанс, что оба получат свои имена или имена друг друга.
3. 3. При наличии трёх Санта-Клаусов каждый может получить своё имя только одним способом. Два человека могут получить своё имя 0 способами, потому что в этом случае последний человек тоже получит своё имя, так как останется только один. Один человек может получить своё имя 3 способами: по одному для каждого из трёх Санта-Клаусов, а остальные двое — по одному способу. 3*1 = 1. Всего существует 3! = 6 возможных способов упорядочить 3 имени. Количество способов, при которых никто не получит своё имя, равно оставшемуся числу: 6-1-3 = 2.

Вот чего мы достигли на данный момент:

Матчи	3 Санта-Клауса	2 Санта-Клауса	1 Санта-Клаус
3	1
2	0	1
1	3	0	1
0	2	1	0
Общий	6	2	1

Далее перейдём к четырём Санта-Клаусам.

4 совпадения: Всегда есть 1 способ, которым каждый получает своё собственное имя.

3 совпадения: Всегда невозможно, чтобы все, кроме одного человека, вытянули свои имена. После того, как все, кроме одного человека, вытянули свои имена, останется только один человек и одно имя, и они должны совпадать.

2 совпадения: существует 6 способов выбрать 2 человек из 4, которые подойдут друг другу. В остальных 2 случаях есть 1 способ, которым они не подойдут друг другу — вытянуть имена друг друга.

1 совпадение: Есть 4 способа выбрать Санту, который совпадает сам с собой. Из случая с 3 Сантой видно, что есть 2 способа, которыми остальные 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 совпадений: Всегда есть 1 способ, которым каждый получает своё собственное имя.

4 матча: Невозможно по причинам, изложенным в деле о 4 Санта-Клаусах.

3 совпадения: существует 10 способов выбрать 3 человек из 5, чтобы они совпали друг с другом. Есть 1 способ, чтобы имена двух других людей совпали. Таким образом, существует 10 способов для 3 совпадений.

2 совпадения: существует 10 способов выбрать 2 человек из 5, которые подойдут друг другу. Для остальных 3 есть 2 способа, которыми они не подойдут, что мы видим на примере с 3 Санта-Клаусами. Таким образом, существует 10*2=20 способов для 2 совпадений.

1 совпадение: Существует 5 способов выбрать Санту, который совпадает сам с собой. Из случая с 4 Сантой видно, что существует 9 способов, которыми остальные 4 Санты не совпадают, что должно произойти. Таким образом, количество комбинаций для 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	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 всегда отличается не более чем на единицу. Общее количество совпадений для 0 на единицу больше, чем для четного числа Санта-Клаусов, и на единицу меньше для нечетного числа. Если мы примем, что это всегда так, а это так, мы можем быстро определить количество совпадений для 11 или более Санта-Клаусов следующим образом.

11 Санта-Клаусов: Для одного совпадения существует 11 Санта-Клаусов, которые должны совпадать, и 133 496 способов, которыми остальные 10 не совпадают, исходя из случая с 10 Санта-Клаусами. Таким образом, количество перестановок для 1 совпадения составляет 11 * 133 496 = 14 684 571. Поскольку 11 — нечетное число, количество перестановок для 0 совпадений на единицу меньше, или 14 684 571 – 1 = 14 684 570.

12 Санта-Клаусов: Для одного совпадения существует 12 Санта-Клаусов, которые должны совпадать, и 14 684 570 способов, которыми остальные 11 не совпадают (из случая с 11 Санта-Клаусами). Таким образом, количество перестановок для одного совпадения составляет 12 * 14 684 570 = 176 214 840. Поскольку 12 — четное число, количество перестановок для 0 совпадений на единицу больше, или 176 214 840 + 1 = 176 214 841.

Следуя той же логике, вот количество перестановок для 0 совпадений от 1 до 20 Санта-Клаусов, включая общее количество перестановок и вероятность.

Санта-Клаусы	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	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	5040	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 совпадений.

Количество комбинаций для m совпадений из 20 Санта-Клаусов равно combin(20,m)*z(m), где z(m) = количество комбинаций из нуля совпадений для m Санта-Клаусов. В следующей таблице используется этот метод для нахождения количества перестановок для 0–20 совпадений с 20 Санта-Клаусами.

Матчи	Перестановки	Вероятность
20	1	0.000000
19	-	0.000000
18	190	0.000000
17	2280	0.000000
16	43,605	0.000000
15	682,176	0.000000
14	10 271 400	0.000000
13	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

Если вы сравните эти вероятности с моими оценками Пуассона в информационном бюллетене от 26 октября 2023 года, вы увидите, что все они совпадают с указанными шестью знаками после запятой, что демонстрирует полезность функции Пуассона и числа e.

На следующей неделе я планирую подробнее остановиться на этой теме и представить общую формулу для количества перестановок любого числа Санта-Клаусов.

Автор: Michael Shackleford