OBZORNIK ZA MATEMATIKO IN FIZIKO IZDAJA DRUŠTVO MATEMATIKOV, FIZIKOV IN ASTRONOMOV SLOVENIJE ISSN 0473-7466 SEPTEMBER 2021 STR 81-120 ŠT. 3 LETNIK 68 LJUBLJANA OBZORNIK MAT. FIZ. C K M Y 2021 Letnik 68 3 i i “kolofon” — 2021/10/25 — 11:05 — page 1 — #1 i i i i i i OBZORNIK ZA MATEMATIKO IN FIZIKO Glasilo Društva matematikov, fizikov in astronomov Slovenije Ljubljana, SEPTEMBER 2021, letnik 68, številka 3, strani 81–120 Naslov uredništva: DMFA–založništvo, Jadranska ulica 19, p. p. 2964, 1001 Ljubljana Telefon: (01) 4766 633, 4232 460 Telefaks: (01) 4232 460, 2517 281 Elektronska pošta: zaloznistvo@dmfa.si Internet: http://www.obzornik.si/ Transakcijski raˇ cun: 03100–1000018787 Mednarodna nakazila: SKB banka d.d., Ajdovšˇ cina 4, 1513 Ljubljana SWIFT (BIC): SKBASI2X IBAN: SI56 0310 0100 0018 787 Uredniški odbor: Peter Legiša (glavni urednik), Sašo Strle (urednik za matematiko in odgovorni urednik), Aleš Mohoriˇ c (urednik za fiziko), Mirko Dobovišek, Irena Drevenšek Olenik, Damjan Kobal, Petar Paveši´ c, Marko Petkovšek, Marko Razpet, Nada Razpet, Peter Šemrl, Matjaž Zaveršnik (tehniˇ cni urednik). Jezikovno pregledal Grega Rihtar. Raˇ cunalniško stavila in oblikovala Tadeja Šekoranja. Natisnila tiskarna COLLEGIUM GRAPHICUM v nakladi 1100 izvodov. ˇ Clani društva prejemajo Obzornik brezplaˇ cno. Celoletna ˇ clanarina znaša 24 EUR, za druge družinske ˇ clane in študente pa 12 EUR. Naroˇ cnina za ustanove je 30 EUR, za tujino 35 EUR. Posamezna številka za ˇ clane stane 6,00 EUR, stare številke 3,00 EUR. DMFA je vˇ clanjeno v Evropsko matematiˇ cno društvo (EMS), v Mednarodno matematiˇ cno unijo (IMU), v Evropsko fizikalno društvo (EPS) in v Mednarodno združenje za ˇ cisto in uporabno fiziko (IUPAP). DMFA ima pogodbo o reciproˇ cnosti z Ameriškim matematiˇ c- nim društvom (AMS). Revija izhaja praviloma vsak tretji mesec. Sofinancira jo Javna agencija za raziskovalno dejavnost Republike Slovenije iz sredstev državnega proraˇ cuna iz naslova razpisa za sofi- nanciranje domaˇ cih znanstvenih periodiˇ cnih publikacij. © 2021 DMFA Slovenije – 2144 Poštnina plaˇ cana pri pošti 1102 Ljubljana NAVODILA SODELAVCEM OBZORNIKA ZA ODDAJO PRISPEVKOV Revija Obzornik za matematiko in fiziko objavlja izvirne znanstvene in strokovne ˇ clanke iz mate- matike, fizike in astronomije, vˇ casih tudi kak prevod. Poleg ˇ clankov objavlja prikaze novih knjig s teh podroˇ cij, poroˇ cila o dejavnosti Društva matematikov, fizikov in astronomov Slovenije ter vesti o drugih pomembnih dogodkih v okviru omenjenih znanstvenih ved. Prispevki naj bodo zanimivi in razumljivi širšemu krogu bralcev, diplomantov iz omenjenih strok. ˇ Clanek naj vsebuje naslov, ime avtorja (oz. avtorjev), sedež institucije, kjer avtor(ji) dela(jo), izvle- ˇ cek v slovenskem jeziku, naslov in izvleˇ cek v angleškem jeziku, klasifikacijo (MSC oziroma PACS) in citirano literaturo. Slike in tabele, ki naj bodo oštevilˇ cene, morajo imeti dovolj izˇ crpen opis, da jih lahko veˇ cinoma razumemo tudi loˇ ceno od besedila. Avtorji ˇ clankov, ki želijo objaviti slike iz drugih virov, si morajo za to sami priskrbeti dovoljenje (copyright). Prispevki so lahko oddani v raˇ cunalni- ški datoteki PDF ali pa natisnjeni enostransko na belem papirju formata A4. Zaželena velikost ˇ crk je 12 pt, razmik med vrsticami pa vsaj 18 pt. Prispevke pošljite odgovornemu uredniku ali uredniku za matematiko oziroma fiziko na zgoraj na- pisani naslov uredništva. Vsak ˇ clanek se praviloma pošlje dvema anonimnima recenzentoma, ki morata predvsem natanˇ cno oceniti, kako je obravnavana tema predstavljena, manj pomembna pa je originalnost (in pri matematiˇ cnih ˇ clankih splošnost) rezultatov. ˇ Ce je prispevek sprejet v objavo, potem urednik prosi avtorja še za izvorne raˇ cunalniške datoteke. Le-te naj bodo praviloma napisane v eni od standardnih razliˇ cic urejevalnikov T E X oziroma L A T E X, kar bo olajšalo uredniški postopek. Avtor se z oddajo ˇ clanka strinja tudi z njegovo kasnejšo objavo v elektronski obliki na internetu. GEOMETRIJA TRIKOTNIKA, OROSLAN IN RAVELLO BOJAN HVALA Fakulteta za naravoslovje in matematiko Univerza v Mariboru Math. Subj. Class. (2010): 51M04, 51M15, 51N20 V ˇ clanku predstavimo Seebachov izrek iz geometrije trikotnika. Dogajanje, podobno kot pri vodenih ogledih filmov, poteka na dveh kanalih. Na enem poteka matematiˇ cna predstavitev tematike, na drugem pa klepet o moˇ znostih, dilemah in ozadjih. TRIANGLE GEOMETRY, OROSLAN AND RAVELLO In this article, we present Seebach’s theorem, which is a topic in triangle geometry. The events, as during guided online film screenings, take place on two channels. On one, there is a mathematical presentation of the topic, and on the other, a chat about possibilities, dilemmas, and backgrounds. Uvod Pred kratkim sem si ogledal slovenski film Oroslan reˇ ziserja Matjaˇ za Iva- niˇ sina. Film kot medij za prenaˇ sanje sporoˇ cil spremljam z velikim zani- manjem. Posebej rad imam evropski avtorski film. Oroslan mi je vzbudil zanimanje ˇ ze ob pripravah na snemanje. Zgodbo Zdravka Duˇ se, ki se je dogajala na Tolminskem, so avtorji prenesli v Porabje. Sledimo dolgim meditativnim posnetkom in dogajanju pripenjamo nabor lastnih asociacij. Film teˇ ce poˇ casi, ˇ casa za osebni prispevek je dovolj. Pozneje sem na spletu zasledilmoˇ znostvodenegaogledafilma. Filmteˇ ce,vzporednopasemodera- tor in avtor pogovarjata o ozadjih, idejah in moˇ znostih. Ogled se je izkazal za dragocenega. Pogosto je potrdil ustreznost lastne percepcije filma in jo razˇ siril v ˇ stevilne, prej neslutene smeri. Od tod ideja o podobni eksperimentalni predstavitvi, tokrat matema- tiˇ cne teme. Nivoja se loˇ cita po pisavi. Matematiˇ cni nivo je pisan v obiˇ cajni pisavi, nivo klepeta v ozadju pa boste prepoznali po zapisu v taki pisavi. *** Geometrija trikotnika je veja matematika, ki se ukvarja s fiksnim trikot- nikom ABC in z njim povezanimi znaˇ cilnimi toˇ ckami, premicami, kroˇ zni- cami in drugimi objekti. Nekatere teme iz geometrije trikotnika so bile v Obzorniku ˇ ze prisotne. Tako je bil v ˇ clanku [7] predstavljen pojem znaˇ cilne toˇ cke trikotnika, v [12] pa kubiˇ cne krivulje trikotnika. Obzornik mat. fiz. 68 (2021) 3 81 Bojan Hvala Izvrstna vstopna toˇ cka v geometrijo trikotnika je spletna stran ameri- ˇ skega matematika Clarka Kimberlinga [1], ki med drugim prinaˇ sa seznam znaˇ cilnih toˇ ck trikotnika z vsemi enciklopediˇ cno zbranimi podrobnostmi. V tem ˇ clanku bomo uporabljali tam nastopajoˇ ce oznake, ki so v geome- triji trikotnika standardne. Tako bomo notranje kote trikotnika oznaˇ cevali z ∠A,∠B,∠C, njihove velikosti pa kar z A,B,C. Povod za to izbiro je dejstvo, da bomo grˇ ske ˇ crke potrebovali za druge namene. Kimberling v svojih pojasnilih tudi ugotavlja, da je ta zapis praktiˇ cen in da sega nazaj vse do Eulerja. Na ta naˇ cin res z isto ˇ crko oznaˇ cimo dve stvari, ogliˇ sˇ ce trikotnika in velikost notranjega kota, a je verjetnost, da bi pri tem priˇ slo do nesporazuma, zelo majhna. Seebachov izrek Definicija 1. Naj boABC trikotnik v ravnini inP toˇ cka znotraj trikotnika. Poltraki AP,BP in CP sekajo stranice a,b,c trikotnika ABC v toˇ ckah A P ,B P in C P . Trikotnik A P B P C P imenujemo Cevov trikotnik trikotnika ABC glede na toˇ cko P. Slika 1. Levo: Cevov trikotnik glede na toˇ ckoP. Desno: srediˇ sˇ cni in antikomplementarni trikotnik. V problemski rubriki revije American Mathematical Monthly je bil leta 1995 objavljen problem, ki je spraˇ seval, ali znotraj trikotnika obstaja toˇ cka P, glede na katero bi bil Cevov trikotnik enakostraniˇ cen. Odgovor je pozi- tiven, reˇ sitev je bila objavljena leta 1997 v [3]. Pozneje se je izkazalo, da je veliko sploˇ snejˇ si rezultat v ˇ clanku [11] ˇ ze deset let prej objavil nemˇ ski matematik Karl Seebach. Rezultatu reˇ cemo Seebachov izrek. Izrek 2. Naj boA 1 B 1 C 1 poljuben trikotnik. Potem obstaja natanko ena taka toˇ cka P znotraj trikotnika ABC, da je Cevov trikotnik A P B P C P trikotnika ABC glede na toˇ cko P direktno podoben trikotniku A 1 B 1 C 1 . 82 Obzornik mat. fiz. 68 (2021) 3 Geometrija trikotnika, Oroslan in Ravello Direktna podobnost (oznaka A P B P C P ≈ A 1 B 1 C 1 ) pomeni, da sta tri- kotnika podobna na naˇ cin, da za ustrezne kote velja A P =A 1 , B P =B 1 in C P =C 1 . Iz izreka seveda takoj sledi, da je znotraj trikotnika natanko ena toˇ cka, katere Cevovov trikotnik je enakostraniˇ cen. Ta toˇ cka sodi med znaˇ cilne toˇ cke trikotnika. V zgoraj omenjeni Kimberlingovi Enciklopediji znaˇ cilnih toˇ ck trikotnika [1] nosi oznako X 370 . Na sliki 1 desno so razpoloviˇ sˇ ca stranic trikotnika ABC oznaˇ cena z A ′ ,B ′ ,C ′ , teˇ ziˇ sˇ ce pa z G. Trikotniku A ′ B ′ C ′ reˇ cemo srediˇ sˇ cni trikotnik trikotnika ABC. Znano dejstvo je, da velja A ′ B ′ C ′ ≈ ABC. Seveda je A ′ B ′ C ′ Cevov trikotnik trikotnikaABC glede na toˇ ckoG. Iz Seebachovega izreka torej izhaja, da je teˇ ziˇ sˇ ce G edina toˇ cka znotraj trikotnika, katere Cevov trikotnik je podoben osnovnemu trikotniku ABC. *** Znani so primeri pomembnih matematikov, ki so poleg svojih glavnih podroˇ cij z velikim veseljem gojili tudi geometrijo. Taka sta bila recimo Euler in Plemelj. Nekateri drugi mate- matiki pa geometriji niso naklonjeni. Geometrijske rezultate doživljajo nekako takole: Imamo neko družino geometrijskih objektov in potem dokažemo, da je lega neke toˇ cke glede na te objekte nekaj ˇ cisto posebnega. To je vˇ casih celo res. Seebachov izrek nam recimo sporoˇ ca informacijo o izjemnosti toˇ cke X 370 . Sporoˇ ca nam tudi dodatno informacijo o izjemnosti težišˇ ca. Vendar pa, ˇ ce pogledamo napravi naˇ cin, lahko v teh ugotovitvahpogosto zaznamo zelo lepe in globokerezultate. NarišimoslikovGeoGebriinpremikajmotoˇ ckoP. (Bralcaprijaznovabim,datodejansko naredi!) Rišejosenamrazliˇ cniCevovitrikotniki. IzSeebachovegaizrekasledi,danatanaˇ cin dobimogalerijopravvsehmožnihobliktrikotnikov. Vsakioblikipripadatoˇ cnodoloˇ cenatoˇ cka P. Znotrajpoljubnegatrikotnikajetorejnapreprostnaˇ cinzakodiranainformacijaopravvseh oblikah trikotnikov. *** Geometrija je nazorna in vizualno predstavljiva. To pomeni, da za raz- liko od nekaterih drugih vej matematike problem lahko hitro razumemo in ga sorazmerno zlahka predstavimo tudi nespecialistu. Izziv je zdaj, kako ta problem reˇ siti. Vˇ casih se izkaˇ ze, da kljub preprosti formulaciji dokaz niti pribliˇ zno ni lahek. To se zgodi tudi v primeru Seebachovega izreka. Originalni dokaz je dolg, nepregleden in kar kliˇ ce po izboljˇ savah. *** 81–99 83 Bojan Hvala Vˇ casih se v matematiˇ cnih raziskavah podajamo v zelo abstraktne daljne svetove, vendar pa potem tam niti ne poˇ cnemo kaj zares ekstremnega. Kot bi poslali vozilo na Mars in se potem veselili vsakega drobnega premika po njem. Seveda je, na primer, prvi marsovski polet z dronom velik dosežek. Sploh ob misli na možnost opazovanja in snemanja površja. A tako velikiprebojisoredki. PodrugistranipaimatudigibanjepostaridobriZemljisvojeprednosti. Vzaˇ cetkumordaekspedicijanividetitakospektakularna,zatopanamomogoˇ ca,daopravimo res izdaten sprehod do neznanih ˇ cudes bližnjih grebenov, sotesk in jam, z izjemnimi razgledi in z inovativno izbranimi prehodi. *** Kot reˇ ceno je originalni dokaz Seebachovega izreka raˇ cunski, dolgotra- jen in nepregleden. Velik napredek v smeri preglednosti je leta 2006 napra- vil jordanski matematik M. Hajja, ki je v ˇ clanku [4] predstavil nov dokaz. Osnovna ideja je naslednja. Slika 2. Dokaz M. Hajje, konstrukcija vˇ crtanega trikotnika. Imamo trikotnik A 1 B 1 C 1 in se spraˇ sujemo po toˇ cki P, da bo veljalo A P B P C P ≈ A 1 B 1 C 1 . Izberimo neki kot ϕ in trikotniku ABC vˇ crtajmo trikotnik A 2 B 2 C 2 tako, da bo A 2 B 2 C 2 ≈ A 1 B 1 C 1 in bo kot ∠BC 2 A 2 = ϕ (slika 2). To naredimo tako, da najprej izberemo neko toˇ cko C ′ 2 ∈ c, odmerimo kot ϕ, dobimo toˇ cko A ′ 2 ∈a, nato pa od daljice C ′ 2 A ′ 2 odmerimo kota A 1 in C 1 ter dobimo toˇ cko B ′ 2 . Tako je A ′ 2 B ′ 2 C ′ 2 ≈ A 1 B 1 C 1 . Zdaj pa naredimo razteg s srediˇ sˇ cem v toˇ cki B, ki trikotnik A ′ 2 B ′ 2 C ′ 2 preslika v podoben trikotnik A 2 B 2 C 2 tako, da toˇ cka B 2 leˇ zi na stranici b. Namesto uporabe raztega si lahko mislimo tudi, da izbrano toˇ cko C ′ 2 premikamo po stranici c toliko ˇ casa, da ustrezna toˇ cka B ′ 2 pade na stranico b. 84 Obzornik mat. fiz. 68 (2021) 3 Geometrija trikotnika, Oroslan in Ravello Na ta naˇ cin, s spreminjanjem kota ϕ, dobimo druˇ zino vseh v trikotnik ABC vˇ crtanih trikotnikov, ki so podobni trikotniku A 1 B 1 C 1 . Zdaj pa mo- ramo dokazati le ˇ se, da se samo pri enem trikotniku iz te druˇ zine daljice AA 2 ,BB 2 inCC 2 sekajo v neki skupni toˇ ckiP, kar pomeni, da je to Cevov trikotnik glede na neko toˇ ckoP (slika 3). Pri tem se opremo na Cevov izrek [14], ki pravi, da se daljiceAA 2 ,BB 2 in CC 2 sekajo v skupni toˇ cki natanko tedaj, ko velja SBA 2 S SA 2 CS ⋅ SCB 2 S SB 2 AS ⋅ SAC 2 S SC 2 BS =1. Avtor je nato izraˇ cunal levo stran zgornjega izraza kot funkcijo f spremen- ljivke ϕ, premislil, na katerem intervalu se giblje kot ϕ, in dokazal, da je f na tem intervalu monotono naraˇ sˇ cajoˇ ca funkcija, ki zavzame vse pozitivne vrednosti. Zato vrednost 1 zavzame natanko enkrat. Med vsemi v trikotnik ABC vˇ crtanimi trikotniki A 2 B 2 C 2 ≈ A 1 B 1 C 1 je torej natanko en Cevov trikotnik glede na neko toˇ cko P. *** Ena od prednosti geometrije je, da nam nudi možnost vizualizacije. Vsebino lahko pribli- žamo s sliko. Še posebej uˇ cinkovito to lahko storimo z raˇ cunalniškimi programi za dinamiˇ cno geometrijo,kisosepojavilipredkakimi30letiinsogeometrijidalimoˇ candodatnizagon. Zelo pomemben pri tem je pridevnik dinamiˇ cni, kar pomeni, da lahko že narisane objekte interak- tivno premikamo, ob tem pa dinamiˇ cno spremljamo spreminjajoˇ co se sliko. Med prvimi takimi programi sta bila Geometer’s Sketchpad in Cabri Geometry, v naših razmišljanjih pa smo že nekajkrat omenili GeoGebro. V nadaljevanjujo bomo ševeˇ ckrat. *** ObravnavaniHajjovdokazlahkospomoˇ cjoGeoGebreuˇ cinkovitoilustri- ramo, ob tem pa premislimo tudi nekatere detajle. Najprej na podlagi slike 2 premislimo, kako iz trikotnika A ′ 2 B ′ 2 C ′ 2 do- bimo trikotnik A 2 B 2 C 2 . Zagrabimo toˇ cko C ′ 2 in jo pomikamo na levo (oz. na desno), dokler toˇ ckaB ′ 2 ne zadene straniceb. Ker si to premikanje lahko predstavljamo kot delovanje raztegov s srediˇ sˇ cem v toˇ cki B in z razliˇ cnimi koeficienti, je jasno, da pri tem postopku toˇ cka B ′ 2 teˇ ce po poltraku z iz- hodiˇ sˇ cem v toˇ cki B. Zato je konˇ cna toˇ cka B 2 kar preseˇ ciˇ sˇ ce tega poltraka s stranico b. Argument z raztegi nam da tudi, da so stranice nastopajoˇ cih trikotnikov pri premikanju vzporedne. Zato je stranica B 2 A 2 vzporedna stranici B ′ 2 A ′ 2 . Pri narisanem trikotniku A ′ 2 B ′ 2 C ′ 2 torej v prvem koraku do- bimo toˇ cko B 2 , z nadaljnjima dvema vzporednicama pa ˇ se toˇ cki A 2 in C 2 . 81–99 85 Bojan Hvala Slika 3. Dokaz M. Hajje, funkcija f je naraˇ sˇ cajoˇ ca. VGeoGebrilahkotudioznaˇ cimodaljiceizizraza SBA 2 S SA 2 CS ⋅ SCB 2 S SB 2 AS ⋅ SAC 2 S SC 2 BS inpri danem kotu ϕ izpiˇ semo vrednost tega izraza, torej f(ϕ) (slika 3). Potem na drsniku spreminjamo kot ϕ in eksperimentalno doˇ zivimo dejstvo, da je funkcija f monotono naraˇ sˇ cajoˇ ca. Pri kotu ϕ, kjer funkcija f zavzame vrednost 1, tudi nazorno vidimo, da se ustrezne tri daljice sekajo v skupni toˇ cki. To je tistaedinatoˇ cka, ki jo trikotnikuA 1 B 1 C 1 zagotavljaSeebachov izrek. Slika v GeoGebri nam tudi omogoˇ ci premisliti in testirati drobne detajle v dokazu, kot je recimo interval, na katerem lahko pri danih podatkih izbi- ramo kotϕ. Upoˇ stevajoˇ c trikotnikC ′ 2 BA ′ 2 mora veljatiϕ<180 ○ −B. ˇ Ce to velja, lahko nariˇ semo daljico C ′ 2 A ′ 2 . V nadaljevanju od nje odmerimo kota C 1 in A 1 . ˇ Ce naj bo toˇ cka B ′ 2 znotraj kota ∠B, mora na spodnji strani ve- ljatiϕ+C 1 <180 ○ . Podoben razmislek na zgornji strani nam daϕ>A 1 −B. Potegnemo poltrak in dobimo toˇ cko B 2 ∈ b. Zdaj nam manjkata le ˇ se dve vzporednici. ˇ Ce ˇ zelimo, da bo toˇ ckaC 2 leˇ zala na stranicic in ne na njenem podaljˇ sku, morabitiϕ+C 1 zunanjikottrikotnikaAC 2 B 2 inzatoveˇ cjiodA. Odtodslediϕ >A−C 1 . Podobnopriobravnavitoˇ ckeA 2 dobimoϕ 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