0

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 arvaamalla1. 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!).

Kun a_5=5, on edellä olleen yhtälön nojalla a_8=6. Nyt myös a_6=a_{a_5}-1=a_5-1=5-1=4 ja vielä a_7=a_{a_6}-1=a_4-1=8-1=7.

Koko jono on siis

    \[a_1=9, a_2=2, a_3=1, a_4=8, a_5=5, a_6=4, a_7=7, a_8=6, a_9=3.\]