Vankilassa on 100 vankia, joilla on mahdollisuus vapautua – mutta vain, jos he onnistuvat yhdessä todella oudon pulman ratkaisemisessa.
Vankilanjohtaja kertoo säännöt:
Huoneessa on 100 laatikkoa, numeroitu 1–100.
Jokaisessa laatikossa on yksi paperilappu, jossa on jonkin vangin numero (myös 1–100).
Numerot on sekoitettu satunnaiseen järjestykseen.
Vangit viedään yksi kerrallaan huoneeseen.
Jokainen vanki saa avata enintään 50 laatikkoa (puolet kaikista).
Vanki ei saa:
siirtää tai vaihtaa lappuja
kertoa myöhemmin toisille, mitä näki
merkitä laatikoita millään tavalla
Kun vanki tulee ulos, seuraavaa ei ole vielä viety huoneeseen – eli he eivät näe toistensa yrityksiä.
Vangit voivat kuitenkin keskustella ja sopia strategiasta ENNEN kuin ensimmäinen viedään huoneeseen.
He voittavat vain, jos:
Kaikki 100 vankia onnistuvat löytämään oman numeronsa avaamalla enintään 50 laatikkoa kukin.
Jos yksikin epäonnistuu → kaikki epäonnistuvat ja vapautta ei tule.
Kysymys:
Onko olemassa strategia, joka tuottaa paremman tuloksen kuin satunnainen arpominen?
Ratkaisu
Jos jokainen vanki vain valitsisi 50 satunnaista laatikkoa, hänen mahdollisuutensa löytää oma numeronsa olisi täsmälleen 50 % (puolet laatikoista).
Mutta koska kaikkien 100 vangin pitää onnistua yhtä aikaa, todennäköisyys, että kaikki sattuisivat onnistumaan, olisi:
0,5^100
Se on käytännössä nolla – astronomisen pieni luku.
Näyttää siis siltä, ettei vangeilla olisi mitään mahdollisuuksia.
Mutta todellisuudessa on olemassa nerokas strategia, joka nostaa voittomahdollisuuden jonnekin 31 % tienoille.
Se on valtava parannus nollan tuntumasta.
Ratkaisu – “seuraa ketjua” -strategia
Yllättävä ratkaisu perustuu sykleihin eli “ketjuihin”, jotka muodostuvat laatikoiden ja lappujen numeroinneista.
Strategia:
-
Jokainen vanki aloittaa omaan numeroonsa merkitystä laatikosta.
-
Esim. vanki numero 37 avaa ensin laatikon 37.
-
-
Kun vanki avaa laatikon ja löytää sieltä numeron X:
-
jos X = oma numero → hän on valmis (onnistui)
-
jos X ≠ oma numero → seuraavaksi hän avaa laatikon X
-
-
Vanki jatkaa tätä:
-
aina avaa seuraavaksi sen laatikon, jonka numeron juuri löysi
-
pysähtyy, kun:
-
löytää oman numeronsa
-
tai on avannut 50 laatikkoa (ei saa avata enempää)
-
-
Tämä tarkoittaa, että jokaisen vangin reitti määräytyy täysin:
-
laatikkojen numeroinnista
-
lappujen sijoittelusta
Vangit eivät valitse laatikoita satunnaisesti, vaan seuraavat determinististä ketjua.
Miltä ketjut (syklit) näyttävät?
Ajattele laatikoita ja lappuja:
-
laatikko 1 sisältää jonkin numeron (esim. 73)
-
laatikko 73 sisältää jonkin numeron (esim. 4)
-
laatikko 4 sisältää jonkin numeron (esim. 1)
Jos jatkat tätä, huomaat saavasi ketjun:
1 → 73 → 4 → 1
Tästä muodostuu suljettu sykli.
Kun kaikki 100 numeroa on laitettu laatikoihin, kaikki muodostavat yhdessä joukon syklejä.
Esimerkiksi:
-
sykli A: 1 → 73 → 4 → 1 (pituus 3)
-
sykli B: 2 → 90 → 18 → 2 (pituus 3)
-
sykli C: 5 → 10 → 11 → 28 → 5 (pituus 4)
-
jne…
Kokonaisuus on aina jonkinlainen jakautuma sykleihin, joiden yhteenlaskettu pituus on 100.
Miksi ketjujen seuraaminen toimii?
Tärkeä havainto:
Vanki numero N kulkee täsmälleen sen syklin läpi, johon numero N kuuluu.
Jos vangin numero N on vaikkapa syklissä:
37 → 12 → 88 → 5 → 37
niin hän:
-
aloittaa laatikosta 37 → löytää 12
-
avaa laatikon 12 → löytää 88
-
avaa laatikon 88 → löytää 5
-
avaa laatikon 5 → löytää 37 (oman numeronsa)
→ hän onnistuu, jos syklin pituus ≤ 50.
Koska kaikkien vankien numerot kuuluvat johonkin syklin osaan, seuraa:
Kaikki vangit onnistuvat, jos ja vain jos yksikään sykli ei ole pidempi kuin 50.
Jos joku sykli olisi esim. pituudeltaan 60, niin sen syklin jäsenet:
-
joutuisivat avaamaan vähintään 60 laatikkoa
-
mutta saavat avata vain 50
→ he eivät voi löytää omaa numeroaan
Siksi onnistumisen ehto on:
Kaikki laatikkojärjestyksen muodostamat syklit ovat enintään 50 pitkiä.
Todennäköisyys: mistä ~31 % tulee?
Kun laatikoiden sisällöt (1–100) sekoitetaan satunnaisesti, kaikki 100! permutaatiota ovat yhtä todennäköisiä.
Näistä permutaatioista osassa kaikki syklit ovat pituudeltaan korkeintaan 50, osassa jokin sykli on pidempi.
Matematiikka (johon liittyy vähän combinatoriikkaa ja asymptoottista analyysiä) kertoo, että:
-
Todennäköisyys, että suurin sykli on enintään 50, on noin 31,18 %.
Eli:
Kun vangit käyttävät “seuraa ketjua omasta numerosta” -strategiaa, he voittavat noin 31 %:ssa kaikista mahdollisista laatikkojärjestyksistä.
Se on valtava parannus verrattuna satunnaiseen valintaan, jossa voittotodennäköisyys on käytännössä:
0,5¹⁰⁰ ≈ 0,0000000000000000000000000000008 (likimain nolla)
Intuitiivinen selitys – miksi tämä on niin paljon parempi?
Ilman strategiaa:
-
Jokaisen vangin kohtalo on riippumaton muiden kohtalosta
-
On “paljon” tapoja epäonnistua
-
Käytännössä aina joku epäonnistuu
Ketjustrategialla:
-
Vangit käyttävät samaa rakenteellista tietoa: permutaation syklirakennetta
-
Onni ei jakaudu satunnaisesti vankien kesken, vaan koordinoidusti
-
Jos permutaatio on “hyvä” (kaikki syklit ≤ 50), kaikki onnistuvat
-
Jos permutaatio on “huono” (jokin sykli > 50), liian moni epäonnistuu joka tapauksessa
Toisin sanoen:
Strategia ei muuta permutaation “hyvyyttä”,
mutta se varmistaa, että kaikilla vangeilla on sama kohtalo:
joko kaikki voittavat, tai lähes kaikki häviävät.
Ja koska noin kolmasosa permutaatioista on “hyviä” syklirakenteeltaan,
→ voittomahdollisuus ~31 %.
