Todennäköisyyksiä turnauskaaviosta

Pulmakulmassa järjestettiin pulmanratkontaturnajaiset. Lähes kaikki Pulmakulman tunnetut lukijat¹ asetettiin turnauskaavioon, josta vain voitolla pääsee etenemään seuraavalle kierrokselle (katso esimerkki ohessa). Turnauskaavion todennäköisyysmatematiikasta saa aikaiseksi muutamia sangen mukavia pulmia. Seuraavat on poimittu Frederick Mostellerin kirjasta Fifty Challenging Problems in Probability.

Ensimmäisen kierroksen pulma on, millä todennäköisyydellä toiseksi paras ratkoja tulee kahdeksan pelaajan turnauksessa toiseksi, kun kaavion ensimmäinen kierros arvotaan.

Toisella kierroksella kysymme, millä todennäköisyydellä kaksi tiettyä pelaajaa (esim. Petri ja Toni) kohtaavat toisensa kahdeksan hengen pelaajan turnauksessa. Finaalikysymyksenä on, millä todennäköisyydellä kaksi tiettyä pelaajaa kohtaavat toisensa $2^n$ pelaajan turnauksessa.

Esimerkki turnauskaaviosta (Tehty osoitteessa http://www.freebracketgenerator.com)

Ratkaisu: Ensimmäinen kysymyksistämme on helppo: jos oletetaan, että ratkojilla on pysyvä paremmuusjärjestys (eli parempi voittaa aina heikomman), tulee toiseksi paras toiseksi vain, jos ei kohtaa parasta ennen kolmatta kierrosta eli finaalia. Näin ollen toiseksi parhaan pitää olla eri puolella kaaviota. Tämän todennäköisyys on $\frac{4}{7}$ .

Toisessa ja kolmannessa kysymyksessä ei enää ole paremmuusjärjestyksellä väliä, nyt oletamme, että kummallakin otteluparin osapuolella on yhtäläiset mahdollisuudet jatkaa seuraavalle kierrokselle.

Olkoon Petri sijoitettu sattumanvaraiseen paikkaan kahdeksanpaikkaisessa kaaviossa. Nyt todennäköisyys, että Toni tulee ensimmäisessä ottelussa häntä vastaan, on $\frac{1}{7}$ . Todennäköisyys sille, että Toni on viereisessä parissa (jolloin he kohtaisivat toisella kierroksella), on $\frac{2}{7}$ , ja todennäköisyys sille, että molemmat pääsevät toiselle kierrokselle on $\left(\frac{1}{2}\right)^2=\frac{1}{4}$ . Edelleen todennäköisyys sille, että Toni ja Petri ovat kaavion eri puolilla (jolloin he kohtaavat aikaisintaan finaalissa), on $\frac{4}{7}$ , ja todennäköisyys, että molemmat etenevät finaaliin saakka, on $\left(\frac{1}{4}\right)^2=\frac{1}{16}$ . Kaikkiaan Petrin ja Tonin kohtaamisen todennäköisyys on nyt

$\frac{1}{7}\cdot 1+\frac{2}{7}\cdot\frac{1}{4}+\frac{4}{7}\cdot\frac{1}{16}=\frac{1}{4}.$

Ratkaistaan sitten vielä viimeinen kysymys. Jos turnauksessa on kaksi osallistujaa, kohtaavat Petri ja Toni varmasti. $2^2=4$ osallistujan tapauksessa he kohtaavat todennäköisyydellä $\frac{1}{2}$ , ja äsken näytimme, että kohtaamistodennäköisyys $2^3=8$ osallistujan turnauksessa on $\frac{1}{4}$ . Voimme tehdä arvauksen, että $2^n$ osallistujan turnauksessa kohtaamistodennäköisyys olisi $\frac{1}{2^{n-1}}$ . Tämä voidaan osoittaa matemaattisella induktiolla.

Selvästi väittämämme pätee, kun $n=1$ , eli $2^1=2$ osallistujan turnauksessa Toni ja Petri kohtaavat todennäköisyydellä $\frac{1}{2^{1-1}}=1$ . Käytetään nyt induktio-oletuksena, että $2^k$ osallistujan turnauksessa kohtaamistodennäköisyys olisi $\frac{1}{2^{k-1}}$ . On osoitettava vielä, että $2^{k+1}$ osallistujan turnauksessa kohtaamistodennäköisyys olisi $\frac{1}{2^{(k+1)-1}}=\frac{1}{2^k}$ .

Aloitetaan toteamalla, että jos osallistujia on $2^{k+1}$ , ovat Petri ja Toni eri puolilla kaaviota (eli kohtaavat aikaisintaan finaalissa) todennäköisyydellä $\frac{2^k}{2^{k+1}-1}$ . Tämä on johdettavissa helposti kahdeksan pelaajan turnauksen mallinnuksen mukaisesti. Finaaliin päästäkseen Tonin ja Petrin on kummankin voitettava $k$ vastustajaa, minkä todennäköisyys on $\frac{1}{2^k}\cdot\frac{1}{2^k}=\frac{1}{2^{2k}}.$ Näin ollen todennäköisyys sille, että he ovat kaavion eri puolilla ja kohtaavat (finaalissa) on

$\frac{2^k}{2^{k+1}-1}\cdot\frac{1}{2^{2k}}.$

Todennäköisyys sille, että Toni ja Petri ovat samalla puolella kaaviota, eli kohtaamassa ennen finaalia on $\frac{2^k-1}{2^{k+1}-1}$ . Induktio-oletuksen mukaan heidän todennäköisyytensä kohdata tässä $2^k$ osallistujan (ali-)turnauksessa on $\frac{1}{2^{k-1}}$ . Näin ollen yhteenlasketuksi kohtaamistodennäköisyydeksi $2^{k+1}$ osallistujan turnauksessa saadaan

$\frac{2^k-1}{2^{k+1}-1}\cdot\frac{1}{2^{k-1}}+\frac{2^k}{2^{k+1}-1}\cdot\frac{1}{2^{2k}},$

joka toden totta sievenee muotoon

$\frac{1}{2^k}.$

Näin ollen induktioväite on osoitettu todeksi ja samoin koko väittämä.

Kössi ei mahtunut mukaan, koska käyttämäni sovellus ei tykännyt skandeista. Olen pahoillani.

Opettaja H:n pulmakulma

OpettajaH.fi

Todennäköisyyksiä turnauskaaviosta

Aiheeseen liittyy

Vastaa Peruuta vastaus

Pistä kiertoon:

Aiheeseen liittyy

Vastaa Peruuta vastaus