torstai 8. maaliskuuta 2018

Poliittinen torniodraama

Aikojen alussa, jolloin Neuvostoliitto näytti ikuiselta ja markalla sai litratolkulla lyijyllistä bensiiniä, oli kaukana Lapissa pieni jalasmökki. Mökkiin oli kokoontunut salamyhkäinen joukko ihmisiä kolmen puutapin ympärille. Yhdessä tapeista oli kuusikymmentäneljä erikokoista rengasta täydellisessä suuruusjärjestyksessä.

Hahmot alkoivat siirtää renkaita yksi kerrallaan tapista toiseen, aina pienemmät isompien päällä pitäen. Kun koko pino olisi siirretty toiseen tappiin, maailma järkkyisi: Paavo Väyrynen jättäisi politiikan lopullisesti!

Se näillä mystisillä hahmoilla myös on tarkoituksena. (Kuten olet saattanut lukea uutisista, he eivät ole ainoita.) Miten heidän tulisi siirtää renkaita, jotta tavoite täyttyisi mahdollisimman nopeasti? Kuinka kauan Paavolla on aikaa jäljellä? Ja ennen kaikkea: mitä ihmettä tämänkin tarinan kirjoittaja on hengitellyt?

Ensimmäisiin kahteen ratkaisu saattaa löytyä pienellä päättelyllä, joten otapa tauko lukemisesta! Kannattaa tosin kokeilla neljällä renkaalla, ja muista säännöt: vain yhtä rengasta voi liikuttaa kerrallaan eikä yksikään rengas saa olla itseään pienemmän renkaan päällä.

Tervetuloa takaisin! (Myös sinä siellä, joka et pysähtynyt kokeilemaan.) Miltä vaikutti, montako siirtoa tarvitsit? Keksitkö yleisesti pätevän strategian?

Tämä pulma, joka tunnetaan yleisemmin Hanoin tornina, ratkeaa helposti rekursiivisella menetelmällä. Rekursio tarkoittaa tässä ongelman pilkkomista pienempiin osiin, kunnes ratkaisu on ilmiselvä. (Historiallisesti mainittakoon, että pulman popularisoi Édouard Lucas 1800-luvulla ja nykyään yleisimmässä muodossa tarinaan kuuluu temppeli, munkkeja ja maailmanloppu.)

Mitä tarvitaan, että neljän renkaan pino saadaan siirrettyä toiseen torniin? No ensin pitää siirtää kolme rinkulaa pois tieltä, sitten siirtää pohjimmainen kiekko ja lopuksi saada donitsikolmikko pinon huipulle.

No kuinkas ne kolme rengasta saadaan siirrettyä omaksi pinokseen? Helppoa: ensin siirretään kaksi päällimmäistä rengasta toiseen pinoon, siirretään kolmoskiekko haluttuun pylvääseen ja väliaikaismajoitetut kaksi kiekkoa sen päälle.

Harjoitukseksi lukijalle jätetään kahden ja yhden kiekon tapaukset.

Eihän tämä olekaan enää niin vaikea pulma! (Hankalampia variaatioita toki on olemassa, mikäli kiinnostuit.) Siirtojen määrä on samalla tavoin helppo laskea. Kaksikiekkoisen pinon siirtämiseen tarvitaan kolme siirtoa. Kolmen pinoon tarvitaan kahden siirto ($3$), pohjimmaisen kiekon siirto ($1$) ja kahden siirto takaperin ($3$), yhteensä siis $7$ siirtoa. Neljään taas tarvitaan $7+1+7$ eli $15$ siirtoa.

Yleisesti ottaen $n$ renkaan siirtämiseen tarvitaan $2^n - 1$ siirtoa. Siispä Paavon perikadoksi koituva operaatio koostuu yksinkertaisesti

\[ 2^{64} - 1 = 18~446~744~073~709~551~615 \]

siirrosta. Jos oletetaan, että yhteen siirtoon menee sekunti ja kellon ympäri joku on tekemässä työtä (uutisten perusteella ei kaukaa haettua), urakkaan menee ainoastaan 584 ja puoli miljardia vuotta. Se on suht paljon se, ottaen huomioon maailmankaikkeuden olevan itse alle 14 miljardia vuotta vanha.

Varoitus: eksistentiaalinen kriisi mahdollinen

Wikipediasta löytyy kaukaisen tulevaisuuden aikajana. Sivu on mielestäni yhtä aikaa ihastuttava ja kauhistuttava — toisaalta se on erittäin mielenkiintoinen, mutta toisaalta sen lukemisesta seuraa aina ahdistava olo ja pitkä linkkivaellus artikkelista toiseen.

Artikkeli tietää kertoa, että kuudensadan miljardin vuoden kuluttua Aurinko on ollut ikuajat hitaasti himmenevä valkoinen kääpiö. Jos Maapallo on selvinnyt Auringon jättiläisvaiheesta, se on kovin hiiltynyt ja äärimmäisen kylmä. Kaikki lähiseudun galaksit ovat pakkautuneet yhdeksi, mikä helpottaa kampanjamatkoja ja paikallisyhdistysten perustamista. Toisaalta maailmankaikkeuden laajenemisen myötä kauemmat galaksit ovat kadonneet valonnopeuden rajaaman horisontin taakse.

Voinemme siis olla varmoja, että Keminmaalta kuuluu vielä pitkään.

Ei kommentteja:

Lähetä kommentti

Kommentit ovat moderoituja — yritän hyväksyä kommenttisi mahdollisimman pian. Voit kirjoittaa kommenttiin LaTeX-koodia tai yksinkertaista HTML-merkintää: lue lisää Kommentointi-sivulta.