matemaattinen induktio

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ä.

0

Ikä on vain numero

|

Koska maailma tuntuu siirtyneen faktojen jälkeiseen aikaan, myös täällä Pulmakulmassa lienee tarpeen venyttää totuuden rajoja. Osoitetaan matemaattista induktiota käyttäen, että kaikki suomalaiset ovat samanikäisiä.

Matemaattisessa induktioperiaatteessahan on kyse siitä, että jos voidaan osoittaa, että

  1. jokin luonnollisia lukuja tai jotain sen osajoukkoa koskeva väittämä pätee pienimmälle tarkasteltavalle luvulle, ja että
  2. väitteen totuudesta luvulle k seuraa väitteen totuus luvulle k+1,

niin tällöin väite pätee kaikille tarkasteltaville luvuille. Induktioperiaatteen hyvä havainnollistus löytyy esimerkiksi tästä.

No niin, sitten asiaan. Osoitetaan ensin, että yhden ihmisen joukossa kaikki ovat keskenään samanikäisiä. Tämä on tietenkin triviaalisti totta.

Tehdään seuraavaksi induktio-oletus, että k suomalaisen joukossa kaikki ovat samanikäisiä. Riittää osoittaa, että tästä seuraa se, että sattumanvaraisten k+1 suomalaisen joukossa kaikki ovat samanikäisiä. Tämä voidaan todistaa osoittamalla, että tämän joukon sattumanvaraiset henkilöt H ja S ovat samanikäisiä.

Poistetaan ensin k+1 suomalaisen joukosta henkilö H. Nyt jäljelle jääneet kaikki k suomalaista ovat induktio-oletuksen mukaan samanikäisiä. Siis S on samanikäinen kaikkien muiden kanssa, esimerkiksi henkilön M kanssa. Poistetaan seuraavaksi alkuperäisestä k+1 suomalaisen joukosta henkilö S. Nyt jäljelle jääneet k henkilöä ovat induktio-oletuksen mukaan samanikäisiä. Siis esimerkiksi H ja M ovat nyt samanikäisiä.

Mutta nythän toisaalta S ja M ovat samanikäisiä ja toisaalta H ja M ovat samanikäisiä, joten välttämättä H ja S ovat samanikäisiä. Olemme siis onnistuneet osoittamaan, että k+1 suomalaisen joukossa kaikki ovat samanikäisiä. Induktioperiaatteen mukaan kaikki suomalaiset ovat samanikäisiä!

No, tuota. Oikeasti minä en ole samanikäinen veljeni kanssa. Viikon vaikea pulma on selvittää, mikä meni pieleen. Onko matematiikka rikki?

Ratkaisu: Matematiikka ei onneksi ole rikki, vaan todistuksessa on ihan oikea virhe. Henkilöistä S ja H poikkeavan henkilön M olemassaoloa ei voida olettaa. Jotta näin voitaisiin tehdä, olisi pitänyt pystyä osoittamaan, että kaikissa kahden henkilön joukoissa on vain samanikäisiä. Ja tämähän ei tietenkään onnistu.