i i \Marc" | 2021/10/29 | 8:52 | page 118 | #1 i i i i i i NOVEKNJIGE A. M. Hinz, S. Klav zar in C. Petr, The Tower of Hanoi { Myths and Maths, With a foreword by Ian Stewart, 2nd edition, Birkhauser, Cham, 2018, 458 strani. Hanojski stolp Problem Hanojskega stolpa je mitolo sko obarvana igra, dobro poznana tako lju- biteljem razvedrilne matematike kot stu- dentom matematike in ra cunalni skega programiranja. Navidez preprosta ugan- ka z elegantno re sitvijo skriva ve c vari- acij in posplo sitev, katerih analiza pre- sega lahkotno igranje in razkrije zani- mive matemati cne strukture in povezave. Dovolj, da so avtorji Andreas M. Hinz, Sandi Klav zar, Uro s Milutinovi c 1 in Ciril Petr izdali knjigo»The Tower of Hanoi { Myths and Maths« o matemati cnih izzi- vih, re sitvah in odprtih problemih te igre ter jo obarvali z zanimivimi miti in zgo- dovinskim ozadjem. Ob nedavnem izi- du druge izdaje knjige bralcem predsta- vimo nekaj zanimivih obravnavanih pro- blemov. V klasi cni igri Hanojski stolp imamo tri palice in n2N diskov, razvr- s cenih po velikosti na eni izmed palic, kot lahko vidimo na sliki 1. Cilj je premakniti vse diske na eno izmed preostalih palic z upo stevanjem bo zan- skih pravil: vrhnji disk lahko premaknemo na drugo palico le, ce ne polo zimo ve cjega diska na manj sega. Ena izmed re sitev zgornjega problema je klasi cen primer rekurzije, ne- stetokrat uporabljen za predstavitev mo ci rekurzivnega programiranja. Ce zelimo premakniti n> 1 diskov s prve palice na drugo, najprej premaknemo n 1 diskov s prve na tretjo (ob upo stevanju pravil), nato premaknemo naj- ve cji disk na drugo palico ter zaklju cimo s premikom n 1 diskov s tretje na drugo palico. Tak algoritem lahko implementiramo v nekaj vrsticah kode in nam vrne re sitev z 2 n 1 potezami, kar je optimalna re sitev. Vendar naj nas enostavnost re sitve in formulacije problema ne zavede, saj ga ze majhne spremembe lahko zelo ote zijo. Imenujmo postavitev diskov 1 Sodeloval samo pri prvi izdaji. 118 Obzornik mat. fiz.68 (2021) 3 i i \Marc" | 2021/10/29 | 8:52 | page 119 | #2 i i i i i i The Tower of Hanoi – Myths and Maths Slika 1. Za cetna postavitev, popolno stanje. na tri palice, v kateri ni noben disk polo zen na manj sega, regularno stanje. Ce so vsi diski na eni palici, stanju re cemo, da je popolno. Takoj smo so- o ceni z izzivom, kako (optimalno) preiti iz poljubnega regularnega stanja v popolno stanje. Lahko bi zeleli premakniti diske iz izbranega stanja 2 v poljubno regularno stanje. Kaj ce je palic ve c kot tri? Kaj se zgodi, ce na- klju cno prehajamo med stanji? Problemi, povezani s hanojskimi stolpi, so v zadnjih desetletjih navdahnili veliko matemati cnih znanstvenih prispevkov, ki igro pove zejo s teorijo grafov, razvojem ra cunalni skih algoritmov, teo- rijo stevil in drugimi znanstvenimi podro cji. Avtorji »The Tower of Hanoi { Myths and Maths« so zbrali zanimive in pomembne prispevke v knjigo, ki je primerna tako za ljubitelja razvedrilne matematike kot tudi za raziskovalca, ki zeli spoznati podro cje. Vsebuje tako uvod v vse potrebno znanje za ma- temati cno analizo problema, dokaze rezultatov, kot tudi vaje za utrjevanje in razmislek o prebranem. V nadaljevanju si oglejmo nekaj zanimivih smeri raziskovanja hanojskih stolpov v upanju, da bralca navdahnemo k branju predstavljene knjige. Hanojski gra, trikotnik Sierpi nskega in 466 885 Vsako regularno stanje lahko predstavimo s preprostim kodnim zapisom. Naj bo T mno zica palic: v igri s tremi palicami lahko torej ozna cimo T = f1; 2; 3g. Vsako regularno stanje lahko opi semo tako, da za vsakega izmed n diskov povemo, na katero palico je polo zen. Ker so diski na vsaki palici v regularnih stanjih urejeni po velikosti, nam tak opis enoli cno dolo ci stanje. Torej lahko regularna stanja predstavimo z elementi iz T n = T T . Ker poljuben elementT n kodira neko regularno stanje, vidimo, da lahkoT n ena cimo z mno zico vseh regularnih stanj in da je takih stanj natanko 3 n . Dodajmo se relacije med regularnimi stanji in ustvarimo graf. Hanojski 2 Denicija dovoljenih premikov nam celo dovoljuje za ceti v stanjih, ki niso regularna. Obzornik mat. fiz.68 (2021) 3 119 i i \Marc" | 2021/10/29 | 8:52 | page 120 | #3 i i i i i i Nove knjige graf H n 3 je graf, katerega vozli s ca so regularna stanja, dve stanji pa sta povezani, ce lahko z dovoljenim premikom preidemo iz enega v drugo. Kot lahko vidimo na sliki 2, dobimo grafe zanimivih oblik. Z grafa lahko opazimo rekurzivno strukturo hanojskih stolpov: H n 3 je sestavljen iz treh H n 1 3 , ter treh povezav med njimi. Slika H n 3 , ko n pove cujemo, postaja vedno bolj podobna trikotniku Sierpi nskega, fraktalni mno zici v ravnini. Pogled na igro Hanojski stolp kot gibanje po grafu H n 3 nam da nov vpogled, hkrati pa odpre nova vpra sanja, ki se pogosto pojavljajo v teoriji grafov: vpra sanja o simetrijah, metri cnih lastnostih, invariantah itd. (a)H 2 3 (b)H 3 3 (c) Trikotnik Sierpi nskega Slika 2. Hanojski gra in trikotnik Sierpi nskega. Omenimo vpra sanje, katerega odgovor je presenetljiv, dokaz pa zal pre- sega ta prispevek. Ce imamo graf H n 3 za n dovolj velik, bo tak graf imel 3 n vozli s c in nekateri pari vozli s c bodo precej oddaljeni med seboj. Na najve cji razdalji 2 n 1 bosta poljubni dve popolni stanji (na sliki 2 so to vozli s ca, ki ustrezajo ogli s cem zunanjega trikotnika). Ve cji kot bo n, ve cja bo tudi povpre cna razdalja med vozli s ci, vendar v kak snem razmerju sta povpre cna in najve cja razdalja v H n 3 ? Izka ze se, da to razmerje konvergira k nenavadnemu stevilu 466 885 , kon pove cujemo. Rezultat implicira, da je tudi v trikotniku Sierpi nskega z zunanjo stranico dol zine 1 povpre cna razdalja med to ckami 466 885 . To presenetljivo racionalno stevilo je bilo po ca s ceno z izborom med neverjetna stevila [2]. Frame-Stewartova domneva in druge variacije Nepri cakovano te zek zasuk osnovnega problema igre Hanojski stolp, tj. pre- hoda iz popolnega stanja v drugo popolno stanje s cim manj koraki, se zgodi, 120 Obzornik mat. fiz.68 (2021) 3 i i \Marc" | 2021/10/29 | 8:52 | page 121 | #4 i i i i i i The Tower of Hanoi – Myths and Maths ce dodamo se cetrto palico. Nova palica, imenovana tudi hudi ceva palica, nalogo prehajanja med popolnimi stanji seveda olaj sa, saj jo lahko prepro- sto ignoriramo. Vendar taka re sitev ni ve c optimalna, saj lahko hudi cevo palico uporabimo za re sitev z manj premiki. Imejmo n2N diskov polo zenih na prvo palico, ki jih zelimo premakniti na drugo. Strategija je naslednja: najprej m diskov, kjer je 0 m < n premaknemo na hudi cevo palico s cim manj premiki, nato preostalih n m diskov premaknemo na drugo palico brez uporabe hudi ceve palice in zaklju- cimo s premikom m diskov iz hudi ceve palice na drugo palico. Strategija motivira denicijo Frame-Stewartovih stevil : Denicija 1. Frame-Stewartova stevila FS n 4 , za vsak n2 N 0 , so denirana rekurzivno FS 0 4 =0 FS n 4 = minf2FS m 4 + FS n m 3 j 0 m