Salainen joulupukki -palapeli

Saatat muistaa, että kirjoitin 26. lokakuuta 2023 julkaistussa uutiskirjeessä laivalla pelatusta peliesityksestä nimeltä Deal or No Deal. Tässä pelissä jokainen pelaaja saattoi ostaa kortteja päästäkseen lavalle. Jokaisella kortilla oli kuitenkin mahdollisuus voittaa lohdutuspalkintoja. Lohdutuspalkinnot toimivat siten, että jokaisessa kortissa oli 20 matkalaukkua, joissa oli 20 erilaista rahapalkintoa satunnaisesti sijoitettuna 20 laatikon taakse. Matkalaukut avattiin nostamalla läppiä. Pelaaja voitti sen mukaan, kuinka monta hänen kortillaan olevaa palkintoa vastasi ruudulla näkyvien samojen palkintojen satunnaista sekoitusta. Yksi uutiskirjeessä ratkaisematon ongelma oli minkä tahansa osumien todennäköisyys.

Tätä ongelmaa kutsutaan yleensä Salainen Joulupukki -pulmaksi. Se on saanut nimensä joulujuhlatoiminnasta, jossa joukko ihmisiä, yleensä samassa toimistossa, valitsee kukin nimen kaikkien toimistotyöntekijöiden hatuista päättääkseen, kenelle antaa lahja. Pelin ongelmana on, että on mahdollista arpoa oma nimi, mikä ei ole hauskaa. Keskimäärin tämä tapahtuu yhdelle pelaajalle jokaisessa toimistossa työntekijöiden lukumäärästä riippumatta. Yksi kysymys, johon yritän vastata tässä uutiskirjeessä, on tarkka todennäköisyys sille, ettei kukaan arpo omaa nimeään.

Kirjoittaessani 26. lokakuuta julkaistua uutiskirjettä en tiennyt tarkalleen, miten laskutoimitukset lasketaan, joten käytin Poissonin funktiota arvioiden tekemiseen. Ongelma on kuitenkin kalvanut minua siitä lähtien. Olen aina kokenut arviot älyllisesti niin epätyydyttäviksi.

Ensin kirjoitin tietokoneohjelman, joka kävi läpi kaikki mahdolliset palkintojärjestykset ja laski kunkin permutaation osumien määrän. Kolmellatoista matkalaukulla ohjelmalta kesti kuitenkin noin päivän käydä läpi kaikki 6 227 020 800 permutaatiota. Kahdessakymmenessä matkalaukussa olisi 2 432 902 008 176 640 000 permutaatiota, joiden läpikäyminen olisi kestänyt noin miljoona vuotta.

Toiseksi, menin Exceliin ja yritin selvittää sen rekursiivisesti. Tämä oli paljon helpompaa kuin odotin. Minun olisi pitänyt tehdä se näin alun perin. Tämän uutiskirjeen loppuosassa selitän tämän lähestymistavan taustalla olevaa logiikkaa.

Oletan lukijan tuntevan Excelin combin(x,y)-funktion, joka kertoo, kuinka monta tapaa valita y alkiota x joukosta. Tarkka yhtälö on x!/(y!*(xy)!).

Aloitetaan joistakin ilmeisistä tapauksista.

1. 1. Yhden joulupukin kohdalla on selvää, että hän saa oman nimensä.
2. 2. Kahden joulupukin kohdalla on 50/50 mahdollisuus, että molemmat saavat omat nimensä tai toistensa nimet.
3. 3. Jos joulupukkeja on kolme, jokainen saa oman nimensä vain yhdellä tavalla. Kaksi ihmistä saa oman nimensä 0 tavalla, koska jos saisivat, viimeinenkin arpoisi oman nimensä, koska se on ainoa jäljellä oleva nimi. Yksi henkilö saa oman nimensä 3 tavalla: yksi jokaiselle kolmelle henkilölle ja sitten kaksi muuta saavat toistensa nimet 1 tavalla. 3 * 1 = 1. Kolme nimeä voi järjestää yhteensä 3! = 6 tavalla. 0 henkilön oman nimensä saamisen tapoja on jäljellä oleva määrä: 6 - 1 - 3 = 2.

Tässä on tilanne tähän mennessä:

Ottelut	3 joulupukkia	2 joulupukkia	1 Joulupukki
3	1
2	0	1
1	3	0	1
0	2	1	0
Kokonais	6	2	1

Seuraavaksi siirrytään neljään joulupukkiin.

4 ottelua: Jokainen saa aina oman nimensä vain yhdellä tavalla.

3 osumaa: Kaikkien paitsi yhden on aina mahdotonta arpoa nimeään. Kun kaikki muut paitsi yksi henkilö ovat löytäneet saman nimen, jäljelle jää vain yksi henkilö ja yksi nimi, joiden kaikkien on oltava samat.

2 paria: On combin(4,2)=6 tapaa valita 2 paria neljästä henkilöstä. Kahden muun kohdalla on yksi tapa, jolla he eivät paria, arpomalla toistensa nimet.

1 osuma: On neljä tapaa valita itseään vastaava joulupukki. Kolmen joulupukin tapauksesta näemme, että on kaksi tapaa, joilla muut kolme joulupukkia eivät ole samoja, mikä olisi pakko tapahtua. Joten yhden osuman yhdistelmien määrä on 4 * 2 = 8.

0 osumaa: Jälleen vähennämme kaikki muut mahdollisuudet permutaatioiden kokonaismäärästä. 4! – 1 – 6 – 8 = 24 - 15 = 9.

Nyt olemme kohdassa:

Ottelut	4 joulupukkia	3 joulupukkia	2 joulupukkia	1 Joulupukki
4	1
3	0	1
2	6	0	1
1	8	3	0	1
0	9	2	1	0
Kokonais	24	6	2	1

Seuraavaksi siirrytään viiteen joulupukkiin.

5 ottelua: Jokainen saa aina oman nimensä vain yhdellä tavalla.

4 osumaa: Mahdotonta 4 Joulupukin tapauksessa mainituista syistä.

3 osumaa: On combin(5,3) = 10 tapaa valita 3 henkilöä viidestä ja löytää itselleen sopivat. On yksi tapa, jolla kaksi muuta voivat saada toistensa nimet. Joten 10 tapaa löytää 3 osumaa.

2 osumaa: On combin(5,2) = 10 tapaa valita 2 henkilöä viidestä pareiksi. Muiden 3 henkilön kohdalla on 2 tapaa, joilla he eivät pareiksi, kuten näemme 3 joulupukin tapauksesta. Joten 2 paria on 10 * 2 = 20.

1 osuma: On 5 tapaa valita itseään vastaava joulupukki. 4 joulupukin tapauksesta näemme, että on 9 tapaa, joilla muut 4 joulupukkia eivät ole sopivia, mikä olisi pakko tapahtua. Joten yhden osuman yhdistelmien määrä on 5 * 9 = 45.

0 osumaa: Jälleen vähennämme kaikki muut mahdollisuudet permutaatioiden kokonaismäärästä. 5! – 1 – 0 – 10 – 20 – 45 = 44.

Nyt olemme kohdassa:

Ottelut	5 joulupukkia	4 joulupukkia	3 joulupukkia	2 joulupukkia	1 Joulupukki
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
Kokonais	120	24	6	2	1

Samaa logiikkaa noudattaen saamme seuraavan taulukon jopa 10 joulupukille.

Matto.	10 joulupukkia	9 joulupukkia	8 joulupukkia	7 joulupukkia	6 joulupukkia	5 joulupukkia	4 joulupukkia	3 joulupukkia	2 joulupukkia	1 Joulupukki
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
Kokonais	3628800	362880	40320	5040	720	120	24	6	2	1

Huomaa, että 0 ja 1 osumien permutaatioiden lukumäärät ovat aina toistensa sisällä. 0 osuman kokonaismäärä on yksi enemmän kuin yksi osuma parillisella määrällä joulupukkeja ja yksi vähemmän parittolla määrällä. Jos oletamme, että näin on aina, kuten se on, voimme nopeasti määrittää 0 osuman määrän 11 tai useammalle joulupukille seuraavasti.

11 joulupukkia: Yhdelle osumalle on 11 sopivaa joulupukkia ja 10 muuta eivät ole 133 496 tapauksessa, 10 joulupukin tapauksessa. Yhden osuman permutaatioiden lukumäärä on siis 11 * 133 496 = 14 684 571. Koska 11 on pariton, 0 osuman permutaatioiden lukumäärä on yksi vähemmän eli 14 684 571 – 1 = 14 684 570.

12 joulupukkia: Yhdelle osumalle on 12 sopivaa joulupukkia ja 11 muuta eivät ole 14 684 570 tavalla, 11 joulupukin tapauksessa. Yhden osuman permutaatioiden määrä on siis 12 * 14 684 570 = 176 214 840. Koska 12 on parillinen luku, permutaatioiden määrä 0 osumalle on yksi enemmän eli 176 214 840 + 1 = 176 214 841.

Samaa logiikkaa jatkaen, tässä on permutaatioiden lukumäärä 0 osumalle 1–20 joulupukille, mukaan lukien kokonaispermutaatiot ja todennäköisyys.

Joulupukit	0 osumaa	Kokonaispermutaatiot	Todennäköisyys
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	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

Huomaa, kuinka 0 ottelun todennäköisyys lähestyy arvoa 0,367879. Näyttääkö luku tutulta? Sen pitäisi! Se on 1/e. Voisin kirjoittaa tässä vaiheessa lyhyen kirjan Poissonin estimaatista, mutta tämä uutiskirje on jo liian pitkä. Lisätietoja tästä saat Stanford Wongin kirjasta Sharp Sports Betting, jossa selitetään, kuinka Poisson-funktiota käytetään Super Bowl -vetojen analysointiin.

Palataanpa Deal or No Deal -peliin, joka vastaa 20 Santa -tapausta. Haluamme tietää yhdistelmien määrän 0–20 osumalla.

m osuman yhdistelmien lukumäärä 20 joulupukista on combin(20,m)*z(m), jossa z(m) = nollan osuman yhdistelmien lukumäärä m joulupukille. Seuraavassa taulukossa käytetään tätä menetelmää permutaatioiden lukumäärän löytämiseen 0–20 osumalla, kun joulupukkeja on 20.

Ottelut	Permutaatiot	Todennäköisyys
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	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
Kokonais	2 432 902 008 176 640 000	1.000000

Jos vertaat näitä todennäköisyyksiä Poisson-arvioihini 26. lokakuuta 2023 uutiskirjeessäni, huomaat, että kaikki ovat samaa mieltä annetuista kuudesta desimaalista, mikä osoittaa Poisson-funktion ja luvun e hyödyllisyyden.

Ensi viikolla aion käsitellä tätä aihetta tarkemmin ja näyttää yleisen kaavan permutaatioiden lukumäärälle mille tahansa määrälle joulupukkeja.

Kirjoittanut: Michael Shackleford