Monthly Archives: helmikuu 2017

0

Todennäköisyyksiä turnauskaaviosta

|

Pulmakulmassa järjestettiin pulmanratkontaturnajaiset. Lähes kaikki Pulmakulman tunnetut lukijat1 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ä.

2

Kolmion ja neliön piiri

|

Pitkän matematiikan tämänkeväisessä preliminäärikokeessa oli yksi kaunis tehtävä, josta saadaan mukava viikon vaikea pulma. Näin se kuuluu:

Neliöllä ja suorakulmaisella kolmiolla on sama pinta-ala. Kumman piiri on pidempi?

Kuva: Joost Markerink / Flickr (CC BY 2.0)

 

0

Torimyyjän tappio

|

Kuva: Phil Romans / Flickr (CC BY-NC-ND 2.0)

Seuraava pulma on kuuluisan amerikkalaisen ongelmanlaatijan Sam Loydin (1841–1911) käsialaa, ja se tunnetaan myös Covent Gardenin ongelmana. Näin se kuuluu:

Tolvanen ja Penttinen myyvät omenoita torilla. Heillä on yhtä paljon omenoita, mutta Penttisen omenat ovat isompia. Siispä Penttinen myy kaksi omenaa eurolla, kun taas Tolvaselta saa kolme omenaa eurolla.

Eräänä päivänä Penttisen piti mennä muualle, ja hän pyysi Tolvasta myymään hänenkin omenansa. Omenakasat sekoitettiin ja hinnaksi asetettiin viisi omenaa kahdella eurolla. Seuraavana päivänä kaikki omenat oli myyty, ja oli aika jakaa potti. He olivat sopineet jakavansa omenoista saatavat rahat tasan. Mutta nyt Tolvanen ja Penttinen huomasivat, että he olivat hävinneet seitsemän euroa siihen nähden, mitä he olisivat tienanneet, jos he olisivat myyneet omenansa erikseen.

Viikon vaikea kysymys on, paljonko Penttinen hävisi myyntijärjestelyssä.

Ratkaisu: Omenoiden kokonaismäärän on oltava viidellä jaollinen, jotta ne kaikki voidaan myydä viiden kappaleen erinä. Mutta jotta omenoista voitaisiin erotella Penttisen ja Tolvasen osuudet (tasaeuroina), on omenoita oltava vähintään 60, joista Tolvanen olisi itse myydessään saanut 10 euroa 30 omenasta ja Penttinen 15 euroa 30 isommasta omenasta.

Nyt 60 omenasta he saivat yhteensä 12\cdot 2=24 euroa, joten he häviävät yhden euron siihen nähden, että olisivat myyneet omenat erikseen. Näin ollen Tolvasen myydessä molempien omenat yhteensä seitsemän euron tappiolla on omenoita ollut alun perin 7\cdot 60=420. Kummallekin kauppiaalle jää siis käteen 7\cdot 12=84 euroa. Jos Penttinen olisi myynyt 210 omenaa itsekseen, olisi hän saanut niistä 210/2=105 euroa, joten Penttinen hävisi järjestelyssä 21 euroa.