Päättymätön shakki

(Ricardo630/Wikimedia Commons. CC-BY-SA 3.0.)

Viime kerralla esitin ongelman:

Opiskelija haluaa käydä yhtä usein Helsingin yliopistolla ja Aallossa. Hän haluaa pitää yllätyksenä, milloin hän seuraavan kerran eksyy millekin yliopistolle. Jos hän noudattaa jotain kuviota kolmesti peräkkäin, häneen kohdistuu suuri sosiaalinen paine jatkaa samalla kuviolla. Mikäli hän käy kolmesti peräkkäin Aallolla, hänellä ei ole enää asiaa Helsingin yliopistolle. Puolestaan jos hän vuorottelee "HAHAHA", hänen on pakko jatkaa vuorottelua — kun taas "HAHA" ja jotain muuta ei tuota ongelmaa. Millainen sääntö opiskelijan pitäisi keksiä, ettei hän ikinä tee samaa kuviota kolmesti peräkkäin ja silti käy yhtä usein kummallakin yliopistolla?

Tämän ongelman ratkaisu kuuluu siihen joukkoon matematiikkaa, joka on niin yksinkertaista, että se hyppää esiin vähän kaikkialla. Sanalla sanoen kutsuisin sitä kauniiksi matematiikaksi.

Opiskelija aloittaa Helsingin yliopistolla. Seuraavana päivänä hän tekee päinvastoin eli menee Aallolle. Sitten hän tekee päinvastoin koko edelliseen nähden: käy Aallolla ja sitten Helsingissä. Sitten taas koko homma päinvastoin: Aalto, Helsinki, Helsinki, Aalto. Jos yliopistoja merkataan nollilla ja ykkösillä, tämä etenee

\[ 0~1~10~1001~10010110~\dots \]

Lopullinen äärettömän pitkä kuvio tunnetaan muun muassa (Prouhet'n-)Thuen-Morsen jonona. Sillä todellakin on haluttu ominaisuus: mikään yhden tai useamman merkin pötkö ei esiinny kolmesti peräkkäin. Kiinnostavampi ominaisuus on, kuinka monta kertaa se on löydetty.

Matemaatikoista siihen perehtyi ensin Eugène Prouhet lukuteorian saralla (1851), sitten Axel Thue kombinatoriikassa (1906) ja lopulta Marston Morse differentiaaligeometrian piirissä (1921). Thue oli ensimmäinen, joka tutki varsinaisesti tätä lukujonoa, mutta norjalaisten tiedejulkaisujen levikki oli sitä luokkaa, että useimmat eivät tienneet hänen tuloksistaan. Siksi Morse löysi samat ominaisuudet uudelleen, julkaisi ne laajalevikkisemmässä lehdessä ja sai nimensä mukaan löytöön.

Kaikki löytäjät eivät olleet matematiikan tutkijoita. Vuonna 1929 shakkimestari Max Euwe — hänkin tosin koulutukseltaan matemaatikko ja aineen opettaja — julkaisi artikkelin, jossa hän sovelsi lukujonoa shakkiin. Pelissä on sääntö, että samojen siirtojen tekeminen kolmesti peräkkäin tarkoittaa tasapeliä; Euwe osoitti, että lukujonomme voi esittää siirtoina, ja siten pelit voivat jatkua loputtomiin säännöstä huolimatta.

Entäs jos ei saisi olla edes kahta peräkkäin?

Ykkösistä ja nollista on mahdotonta luoda kolmea numeroa pidempi jono, jossa joku pötkö ei toistu kahdesti peräkkäin. Sen sijaan nollista, ykkösistä ja kakkosista sellaisen voi luoda. Mikä parasta, ratkaisuista on jo valinnan varaa, koska niitä on useampi.

Aloitetaan edellisestä tutusta jonosta:

\[ 01101001\ldots \]

ja lisätään numeroiden väliin epäyhtälömerkit. Nyt ei puhuta kunnon epäyhtälöstä vaan kahden vierekkäisen numeron välisistä suhteista:

\[ 0<1=1>0<1>0=0<1\ldots \]

Tästä saatava ketju ei sisällä ainuttakaan peräkkäistä toistoa. Ei yksimerkkistä, ei kaksimerkkistä, ei yhtään minkään pituista. Korvaa merkit haluamallasi tavalla numeroilla.

\[ <=><>=<\cdots \]

Mielivaltaisen termin löytäminen

Toistaiseksi olen puhunut vain kaavasta, joka tuottaa uusia numeroita aiemman jonon perusteella. Mutta olisiko jotain kaavaa, jolla saa välittömästi tiedon mistä vain termistä? No totta kai.

Lasketaan esimerkin vuoksi kahdeksas numero. Vähennetään yksi, jolloin saadaan $7$. Binääriluvuksi muutettuna se on $111_2$. Koska siinä on pariton määrä ykkösiä, kahdeksas termi on $1$. Ja niinhän se onkin! Thuen-Morsen jono siis kuvaa ykkösten määrän parillisuutta binääriluvuissa nollasta ylöspäin.

Lisää sovelluksia

Aiemmin jo nähtiin, että lukujonoa on tutkittu niin lukuteorian, kombinatoriikan kuin differentiaaligeometriankin piirissä. Sitä voi soveltaa myös analyysiin ja algebraan. (Jos nämä ovat täyttä hepreaa, vilkaise lyhyttä listaani matematiikan aloista!) Myös fyysikot ovat kiinnostuneita siitä, koska se on tavallaan hallitusti epäjärjestyksellinen, millä on merkitystä kvasikristallien tutkimuksessa. Minulla ei ole aavistustakaan, mitä kvasikristalli tarkoittaa, mutta se on varmasti jotain todella siistiä.

Näiden sijaan haluan kuitenkin esittää yhden kauniin sovelluksen.

Sovitaan, että $0$ tarkoittaa askelta eteenpäin ja $1$ puolestaan $60^\circ$ käännöstä. Mitä pidemmälle lukujonossa edetään...

(Fibonacci/Wikimedia Commons. CC-BY-SA 3.0.)

...sitä enemmän syntyvä kuvio muistuttaa Kochin lumihiutaletta, kauniisti kiemurtelevaa loputonta fraktaalia.

Aloitimme siis matkamme maanalaisella matkustamisesta ja päädyimme idylliseen talvimaisemaan. Sitä se matematiikka teettää.

---

Jos haluat välttämättä tietää ohittamani sovellukset eikä matemaattinen teksti pelota, vilkaise tätä akateemista artikkelia.