Paikkalippukaaos junassa

Kuva: Osupon. Lisenssi: CC-BY-SA 3.0.

Junan 100 istumapaikkaa on myyty sadalle matkustajalle. Paikat on numeroitu yhdestä sataan. Oletetaan, että matkustajat astuvat junaan paikkanumerojärjestyksessä.

Ensimmäisen lipun haltija ei kuitenkaan ymmärrä, että lipussa on paikkanumero, ja istuu satunnaiselle paikalle. Muut matkustajat tulevat yksitellen vaunuun ja istuvat omalle paikalleen, jos se on vielä vapaa. Jos paikka on jo varattu, valitsee matkustaja sattumanvaraisesti minkä tahansa muun vapaan paikan.

Mikä on todennäköisyys, että 100. matkustaja istuu lopulta omalla paikallaan?

Todennäköisyys on 1/2. Selitys:

Ensimmäisellä matkustajalla on 3 vaihtoehtoa:
1) Istuu paikalle 1, jolloin hänen jälkeensä tulevat matkustajat voivat myös kaikki istua omille paikoilleen. Myös 100. matkustaja saa oman paikkansa.
2) Istuu paikalle 100, jolloin matkustaja 100 ei saa omaa paikkaansa.
3) Istuu jollekin muulle vapaalle paikalle, jolloin sama valinta siirtyy kyseisen paikan oikealle haltijalle.

Esimerkki:

Jos ensimmäinen matkustaja päättää istua vaikkapa paikalle 49, on paikan 49 haltijan tehtävä sama yllä kuvattu valinta. Jos paikan 49 haltija päättää istua vaikkapa paikalle 71, on paikan 71 haltijalla edelleen sama valinta tehtävänään. Lopulta viimeistään paikan 99 haltija joutuu tekemään valinnan enää kahdesta vaihtoehdosta 1 ja 2, koska muita vapaita paikkoja ei enää ole.

Vaihtoehdon 3 valitseminen siis vain siirtää valinnan tekemisen myöhemmäksi. Siinä vaiheessa, kun joku valitsijoista valitsee vaihtoehdon 1 tai 2, valintaprosessi päättyy. Valinnan 1 jälkeen kaikki matkustajat numeroon 100 asti voivat istua omille paikoilleen. Valinnan 2 jälkeen kaikki matkustajat numeroon 99 asti voivat istua omille paikoilleen ja paikan 100 haltijalle jää vaihtoehdoksi vain istumapaikka numero 1.