Rekursiivinen rekursio

Kollegani Petri Kuukkanen antoi minulle melkoisen pirulaisen ratkottavaksi. Näin se kuuluu:

Järjestä luvut $1, 2, 3, \ldots, 9$ lukujonoksi $a_1, a_2, a_3, \ldots, a_9$ niin, että

$a_2=2$ ja
$a_n=a_{a_{n-1}}-1$ , kun $n=2, 3, \ldots, 9.$

Kuva: Bird Eye/Flickr (CC BY 2.0)

Ratkaisu: Pulma on varsin originaali, en ole törmännyt aiemmin tällaiseen, eikä ole Petrikään, joka pulman on laatinut. Hän on myös tarkastanut, ettei pulmaan löydy kuin yksi ratkaisu. Tietenkinhän pulma voidaan ratkoa myös kokeilemalla, mahdollisia järjestyksiä on vain $8!=40320$ kappaletta, mutta mekaaninen ratkaisu olisi vähän tylsä. Mennään siis loogisella päättelyllä tekemääni ratkaisuun.

Poimitaan helpot ensin. Jo tehtävänanto lupaa, että $a_2=2$ . Tästä seuraa heti, että $a_3=a_{a_2}-1=a_2-1=2-1=1.$

Seuraavaksi joudutaan jo vähän pohtimaan. Koska rekursiokaavan mukaan $a_n=a_{a_{n-1}}-1$ , kun $n=2, 3, \ldots, 9$ , on $a_n<a_{a_{n-1}}.$ Koska $a_1$ kuuluu rekursiokaavan ulkopuolelle, on tehtävä johtopäätös, että koko jonon suurin termi on $a_1=9$ . Tämän perusteella puolestaan ratkeaa, että $a_4=a_{a_3}-1=a_1-1=9-1=8.$ Edelleen, koska $a_2=a_{a_1}-1=a_9-1$ , saadaan termiksi $a_9=a_2+1=2+1=3$ .

Järjestämättä ovat vielä arvot $4, 5, 6$ ja $7$ termeiksi $a_5, a_6, a_7$ ja $a_8$ . Koska $a_5=a_{a_4}}-1=a_8-1$ ja koska $a_8=a_{a_7}-1$ , niin $a_5=a_{a_7}-2$ . Nyt minulle tuli hetkeksi tenkkapoo, ja myönnänkin edenneeni seuraavaan vaiheeseen arvaamalla¹. Käytettävissä olevien lukujen nojalla tämä jättää vaihtoehdot $a_5=4$ tai $a_5=5$ . Näistä vaihtoehto $a_5=4$ johtaa ristiriitaan (kokeile vain!).