      P 51 (2023/2024) 6 7 Dvakrat skoraj 2n T K̌̌  P K̌ Bi znali nadaljevati zaporedje 2,4,8, . . .? Če ste kot odgovor podali geometrijsko zaporedje potenc števila 2, to seveda ni edina rešitev. Rešitev je tudi zaporedje, kjer se razdalja med sosednjima členoma povečuje za 2 ( 2,4,8,14,22,32, . . .); po- navljajoče se zaporedje 2,4,8,2,4,8,2 . . .; naključ- no zaporedje 2,4,8,15,´3, . . .; in še bi lahko našte- vali – v resnici je rešitev neskončno. Res je, da se potence števila 2 pogosto pojavljajo pri številnih problemih, vendar nas lahko včasih prehitro sklepanje tudi zavede. Predstavili bomo dva problema, pri katerih nas nekaj začetnih čle- nov hitro napelje na splošno formulo. Toda v enem primeru se sklepanje izkaže za pravilno, v drugem pa ne, zato moramo biti pri delanju zaključkov po- zorni, da vedno preverimo, ali naše domneve dr- žijo tudi na splošno. 1. Število potez za premik hanojskega stolpa Začnimo z legendo: V nekem indijskem mestu stoji velik tempelj. Pod njegovo kupolo je bronasta plo- šča, na kateri stojijo tri diamantne igle. Na eno teh igel je bilo ob nastanku sveta položenih – od največ- jega na dnu do najmanjšega na vrhu – 64 obročev iz čistega zlata. Brahmani, menihi hindujskega bo- žanstva Brahme, dan in noč neutrudno prestavljajo obroče z ene igle na drugo po naslednjih dveh pravi- lih: (1) premakne se lahko po en obroč naenkrat in (2) večji obroč ne sme biti položen čez manj- šega. Ko bodo vsi obroči v celoti prestavljeni na tretjo iglo, bo po starodavnem izročilu nastopil konec sveta. Le kdaj se bo to zgodilo? Problem je zelo znan in ste ga bralci verjetno že srečali ali pa ga celo imate v svoji škatli z igračami. To zanimivo matematično sestavljanko je leta 1883 izumil francoski matematik Édouard Lucas in jo po- imenoval hanojski stolpi1. Obstaja še več drugih po- imenovanj, na primer brahmanski stolpi (po božan- stvu iz legende). Ni pa znano, ali si je avtor sam izmislil legendo ali ga je le navdahnila. SLIKA 1. Radi bi izračunali, kdaj bi po legendi nastopil ko- nec sveta. Recimo, da menihi za vsako potezo po- trebujejo eno sekundo. Zdaj moramo izračunati še število potez za premik stolpa iz 64 obročev. Pa zač- nimo z manjšim številom obročev, ki ga označimo z n, in si oglejmo sliko 2: Pri n “ 3 lahko že opazimo vzorec: 1. na srednjo palico premaknemo stolp iz vrhnjih dveh obročev (za kar potrebujemo število po- tez pri n “ 2, torej tri), 1Hanoj je glavno mesto Vitenama, blizu katerega dejansko obstaja starodavna razvalina nekega budistǐcnega svetišča.       P 51 (2023/2024) 68 SLIKA 2. Najmanjše število potez za 1, 2 in 3 ploščice. 2. največji obroč premaknemo na tretjo palico (ena poteza) 3. spet premaknemo stolp iz manjših dveh obro- čev, tokrat na tretjo palico (zopet tri poteze za n “ 2) Skupaj res opravimo 3 ` 1 ` 3 “ 7 potez. Zapišimo še vzorec z oznakami za splošni n. Naj bo Sn najmanjše število potez, potrebnih za premik hanojskega stolpa iz n obročev. Kot prej opazimo, da stolp iz n obročev premaknemo tako, da najprej vrhnji stolp iz n´1 obročev premaknemo na srednjo palico, nato največji obroč na tretjo, čezenj pa zopet stolp iz srednje palice (gl. sliko 3). Dobimo rekurzivno formulo Sn “ 2Sn´1 ` 1 pri čemer je S1 “ 1. Izrazimo še eksplicitno formulo: Sn “ 2Sn´1 ` 1 “ “ 2p2Sn´2 ` 1q ` 1 “ 22Sn´2 ` 2 ` 1 “ “ 22p2Sn´3 ` 1q ` 2 ` 1 “ “ 23Sn´3 ` 22 ` 2 ` 1 “ “ . . . “ “ 2n´1S1 ` 2n´2 ` 2n´3 ` ¨ ¨ ¨ ` 22 ` 2 ` 1 “ “ 2n´1 ` 2n´2 ` ¨ ¨ ¨ ` 22 ` 2 ` 1 “ “ 2n ´ 1 Z dobljeno formulo sedaj izračun, koliko časa se premika 64 obročev (ena sekunda na premik), pre- pustimo bralcu. Za ovrednotenje rezultata dodajmo podatek, da je Zemlja stara približno 4,5 milijard SLIKA 3. Najmanjše število potez za n obročev.       P 51 (2023/2024) 6 9 let, vesolje pa 13,8 milijard let. Poleg tega ima naše Sonce še približno 5 milijarde let življenjske dobe. Za konec še opozorilo: kljub lahkemu izračunu najmanjšega števila potez pa samo premikanje pri večjem številu obročev ni enostavno in zahteva več koncentracije. Bralcu prepuščamo tudi premislek, na katero palico je treba postaviti najmanjši obroč, da bo končni stolp res stal na tretji palici. 2. Moserjev problem delitve kroga Imejmo krožnico, na katero na poljubnem mestu po- stavimo točko. Krog je ostal cel, nerazdeljen. Na krožnico dodamo še eno točko ter jo povežemo s prejšnjo, kot je prikazano na spodnji sliki 4. Krog smo s tem razdelili na dva dela oziroma na dve ob- močji. Dodamo še tretjo točko in ju povežemo s prej- šnjima. Tako dobimo krog, ki je razdeljen na štiri ob- močja. Postopno dodajamo točke in jih povezujemo z vsemi prejšnjimi. Zanima nas, koliko območij naj- več lahko dobimo, ko je na krožnici n točk. Ta pro- blem iskanja števila območij v odvisnosti od števila točk na krožnici imenujemo tudi Moserjev problem delitve kroga. Poglejmo si, kaj se zgodi, ko dodamo še četrto in peto točko. Ko dodamo četrto točko, do- bimo osem območij, ko dodamo peto točko pa 16 območij. SLIKA 4. Število območij pri delitvi kroga z 1, 2, 3, 4 oz. 5 točkami na krožnici. Iz prvih petih primerov bi lahko sklepali, da je za- porednje števila območij, ki jih dobimo, če na kro- žnico dodajamo točke in jih povežemo s prejšnjimi, enako zaporedju z eksplicitno formulo an “ 2n´1. Preverimo dobljeno eksplicitno formulo še na pri- meru s šestimi točkami. Po formuli bi morali dobiti 32 območij, saj je a6 “ 25 “ 32. Če se malo po- trudimo in res dodamo šesto točko, jo povežemo z vsemi preostalimi in preštejemo dobljena območja, kot je prikazano na sliki 5, opazimo, da smo dobili le 31 območij. Očitno smo iz začetnih petih členov prehitro sklepali na lastnosti zaporedja. SLIKA 5. Primer s šestimi točkami. Poskusimo sedaj poiskati pravilno eksplicitno for- mulo, ki bi nam povedala, koliko območij dobimo, ko imamo na krožnici razporejenih n točk. Na tem mestu moramo le opozoriti, da razporeditev točk na krožnici ni popolnoma poljubna. Neustrezna je vsa- ka razporeditev točk, ki privede do situacije, ko se tri ali več kot tri, daljice sekajo v isti točki. To se zgodi le v redkem primeru, ko so točke na krožnici raz- porejene preveč simetrično, kar lahko preprečimo z naključnim razporejanjem točk na krožnico. Ker z naraščanjem n-ja čedalje težje razporejamo točke na krožnico in štejemo območja, bomo posku- sili prešteti kaj drugega, kar nam bo morda poma- galo pri določanju števila območij. Na primerih, ki smo jih že narisali, preštejemo, koliko daljic smo narisali pri posameznem primeru ter v koliko pre- sečiščih znotraj kroga se te daljice sekajo. Preštete vrednosti vpišemo v tabelo 1. Morda bi daljice in presečišča znali prešteti tudi v       P 51 (2023/2024) 610 število točk število daljic število presečišč število območij 1 0 0 1 2 1 0 2 3 3 0 4 4 6 1 8 5 10 5 16 6 15 15 31 TABELA 1. Prvih šest primerov. splošnem primeru, ko imamo na krožnici razporeje- nih n točk. Vsaka daljica določa natanko en par točk na krožnici in vsak par točk določa natanko eno da- ljico. Iz tega sledi, da je število daljic enako številu možnih parov točk, torej ` n 2 ˘ . S podobnim premisle- kom lahko pridemo tudi do števila presečišč. Število presečišč je enako številu možnih četveric točk med n točkami, torej ` n 4 ˘ . Razmislimo, kako bi lahko s pomočjo števila da- ljic in presečišč prešteli vsa območja v primeru z n točkami. Na začetku je krog sestavljen iz enega ob- močja, ko narišemo prvo daljico, se krog razdeli na dve novi območji. Vsaka nova daljica, ki jo narišemo, razdeli eno staro območje na dve novi območji. Če nova daljica seka še kakšno drugo že narisano da- ljico, z vsakim takim presekom seka še eno dodatno območje, ki ga razdeli na dve novi območji. Začnemo torej z enim območjem in z vsako daljico, ki jo na- rišemo, dobimo novo območje. Prav tako z vsakim presečiščem dobimo novo območje. Lahko zaklju- čimo, da je skupno število območij enako 1 ` št. daljic ` št. presečišč “ “ 1 ` ˆ n 2 ˙ ` ˆ n 4 ˙ “ “ 1 ` npn´ 1q 2 ` npn´ 1qpn´ 2qpn´ 3q 4! “ “ . . . “ “ 1 24 pn4 ´ 6n3 ` 23n2 ´ 18n` 24q Namesto pričakovane eksponentne funkcije smo torej dobili polinom četrte stopnje. Moserjev problem delitve kroga je samo eden od primerov, ki nas uči, da se pri zaporedjih ne smemo zanašati le na lastnosti začetnih členov in iz njih sklepati na lastnosti celega zaporedja. Pomembno je, da ne delamo prehitrih zaključkov in se ne zado- voljimo z opazovanjem lastnosti na večjem številu začetnih členov. Če želimo z gotovostjo trditi, da za zaporedje velja neka lastnost, je nujno, da jo doka- žemo. Prispevek je nastal pri predmetu Matematika za nadarjene za študente programa Pedagoška mate- matika na Fakulteti za matematiko in fiziko Univerze v Ljubljani. Literatura [1] https://en.wikipedia.org/wiki/Tower_of_ Hanoi [2] https://www.puzzlemuseum.com/month/ picm07/2007-03_hanoi.htm [3] C. Petr, Posplošitev klasičnega problema hanoj- skih stolpov, magistrsko delo, IZUM, Maribor, 1998. Dostopno na: http://cirilpetr.com/ papers/magisterij.pdf [4] G. Sanderson, Moser’s circle problem, [ogled 25. 1. 2024] dostopno na https://www. 3blue1brown.com/lessons/moser-reboot. ˆ ˆ ˆ