UNIVERZA V MARIBORU PEDAGOŠKA FAKULTETA ODDELEK ZA MATEMATIKO IN RAČUNALNIŠTVO Ciril Petr KOMBINATORIKA POSPLOŠENIH HANOJSKIH STOLPOV Doktorska disertacija Maribor, 2004 Zahvala: Za nesebično pomoč, vzpodbude in podporo se iskreno zahvaljujem prof. dr. Sandiju Klavžarju in prof. dr. Urošu Milutinoviću. Izkazala sta se kot izjemna pedagoga, tako po strokovni plati, kot tudi po človeški širini in življenjski modrosti. Za vedno mi bo ostal topel spomin na naša številna srečanja, na katerih so se porajale mnoge ideje in rojevale rešitve problemov. Preko našega druženja sem spoznal matematiko, kakršne se z učenjem iz učbenikov in branjem člankov ne da. Zahvaljujem se svoji družini za veliko razumevanja in potrpljenja. Hvaležen sem podjetju IskraTEL, da sodeluje pri projektu Grafi in telekomunikacijska omrežja, katerega del so tudi rezultati te disertacije. Povzetek Vpeljemo popoln opis stanja posplošenih Hanojskih stolpov in delni opis, s katerim opišemo le razmestitev vrhnjih ploščic. Definiramo preslikavo iz popolnega v delni opis, ugotavljamo njeno surjektivnost, injektivnost, preštejemo elemente v sliki te preslikave, to je vse različne delne opise, računamo moč praslik, navedemo pogoj, kdaj delnemu opisu ustreza enoličen popolni opis, in preštejemo vse take delne opise stanj. Definiramo graf stanj posplošenih Hanojskih stolpov. Ogledamo si nekatere inducirane podgrafe. Na dva načina preštejemo vse povezave v grafu, preštejemo tudi število prestavitev posamezne ploščice ter izračunamo minimalno, maksimalno in povprečno stopnjo grafa. Definiramo pet strategij reševanja problema posplošenih Hanojskih stolpov, med katerimi sta tudi domnevno optimalni Framova in Stewartova strategija. Dokažemo, da so, glede na število premikov ploščic, enakovredne. Dokažemo obstoj in opišemo vse 1-popolne kode v grafih Sierpińskega, ki predstavljajo grafe stanj posplošenih Hanojskih stolpov s spremenjenim pravilom prestavljanja ploščic. Ta rezultat je posplošitev znanih rezultatov o grafih Hanoj-skih stolpov s tremi položaji, pri katerih pa je pristop bistveno drugačen. Podamo tudi optimalen dekodirni algoritem, ki za dano 1-popolno kodo in točko grafa ugotovi ali je kodna točka, in če ni, poišče njej najbližjo kodno točko. AMS Math. Subj. Class. (2000): 05A15, 05A19, 68R10, 90C35, 94B25, 94B35. Ključne besede: Hanojski stolpi, kombinatorika, algoritem, najkrajša pot, grafi Sierpińskega, 1-popolna koda. Abstract We introduce a complete description of the state of generalized Towers of Hanoi, and a partial description in which only positions of the top-most discs are specified. We define a mapping from the complete to the incomplete description, analyze its surjectivity and injectivity, count the elements in the image of this map, i.e. all the different partial descriptions, compute the cardinality of the preimages, give the condition for a partial description to have the unique complete description, and count all such partial descriptions. We define a state graph of generalized Towers of Hanoi. We look at some of the induced subgraphs. We count the number of edges in the graph in two different ways. We also count the number of moves of a certain disc, and calculate the minimum, maximum and average degree of the graph. We define five strategies for solving the generalized Towers of Hanoi problem, including the presumed optimal strategies of Frame and Stewart. We prove that they are equivalent with respect to the number of discs moves. We prove the existence and describe all 1-perfect codes in Sierpiński graphs, which represent the state graphs of the generalized Towers of Hanoi with modified rules for moving discs. This result is a generalization of previously known results about the graphs of Towers of Hanoi with three pegs, where the approach is intrinsically different. We also present the optimal decoding algorithm, which for a given 1-perfect code and a vertex of a graph decides whether it is a code vertex, and if not, finds its nearest code vertex. AMS Math. Subj. Class. (2000): 05A15, 05A19, 68R10, 90C35, 94B25, 94B35. Keywords: Towers of Hanoi, combinatorics, algorithm, shortest path, Sierpiński graphs, 1-perfect code. Kazalo 1 Uvod 1 2 Kombinatorika Hanojskih stolpov 9 2.2 Vrhnje ploščice ............................. 12 2.3 Praslike funkcije Tn>p.......................... 16 2.4 Stopnja stanj . . .'........................... 21 3 Grafi Hanojskih stolpov 25 3.1 Zapis oznak točk z osnovo p...................... 27 3.2 Konstrukcija grafa HL......................... 28 3.3 Nekateri podgrafi grafa HL....................... 31 3.3.1 Ploščice zasedajo fiksno podmnožico položajev........ 31 3.3.2 Razporeditev k največjih ploščic je fiksirana......... 37 3.4 Število povezav............................. 37 3.5 Število prestavitev posamezne ploščice ................ 42 3.6 Stopnje točk............................... 43 4 Enakost nekaj domnevno optimalnih rešitev 45 4.1 Rekurzivne definicije.......................... 46 4.1.1 Framov algoritem........................ 46 4.1.2 Stewartov algoritem ...................... 47 4.1.3 Vse particije........................... 49 4.2 Dokaz A' = F' = S........................... 50 4.3 Eksplicitne formule........................... 53 4.4 Dokaz X = S.............................. 56 4.5 Enakost vseh .............................. 59 5 1-popolne kode v grafih Sierpińskega 61 5.1 Teorija kodiranja in popolne kode v grafih.............. 61 5.2 Grafi Sierpińskega............................ 63 ix X KAZALO 5.3 Nekateri podgrafi grafa S(n, k) ..................... 65 5.4 Enolična 1-popolna koda ........................ 68 5.5 Dekodirni algoritem ........................... 77 6 Zaključek 85 A Dekodiranje 1-popolnih kod v grafih Sierpińskega 89 Literatura 93 Slike 99 Stvarnoinimensko kazalo 101 Poglavje 1 Uvod Verjetno ni študenta matematike ali računalništva, ki še ni slišal za Hanojske stolpe (slika1 1.1). Večina se z njimi sreča kot s primerom problema, ki ga je Slika 1.1: Klasični Hanojski stolpi 1Slika Hanojskih stolpov je s prijaznim dovoljenjem Andreasa M. Hinza vzeta z njegove domače strani. 1 2 POGLAVJE 1. UVOD mogoče elegantno rešiti z rekurzijo. Skoraj vsak osnovni učbenik algoritmov, diskretne matematike, umetne inteligence, kombinatorike, ki obravnava rekurzi-jo, navaja tudi Hanojske stolpe. Uporabljajo jih celo za psihološke teste, merjenje zmogljivosti nekaterih mentalnih funkcij [54] in prodajajo kot miselno igrico. V (dinamičnem) preglednem članku o kombinatoričnih igrah Fraenkel [10] med več kot tisoč viri navaja kar 83 člankov o Hanojskih stolpih. Leta 1883 je v Franciji prišla na tržišče igrica z naslovom Hanojski stolpi. Kot Slika 1.2: Pokrov škatle z igrico Hanojski stolpi avtor igrice je bil na sliki na pokrovu škatle (slika 1.2) napisan profesor N. Claus (de Siam), mandarin s kolegija “Li-Sou-Stian”. Leta 1884 je de Parville razkril [61], da je to pravzaprav anagramski psevdonim za “Lucas (d’Amiens)” iz “Saint-Louis” - znanega francoskega matematika Édouarda Lucasa [60]. Skenirano fotokopijo naslovnice, besedilo igrice v originalu in prevod v angleščino najdemo na domačih straneh Stockmeyerja [75]. Sicer pa naslovnico podrobno razišče in se pri tem ?599999999999999999999999999999945 3 sklicuje na ustrezno literaturo Hinz v članku [19]. Velik delež popularnosti igrice lahko nedvomno pripišemo legendi, ki jo je priložil Lucas. V Indiji, v mestu Benares, je velik tempelj s kupolo, ki označuje center sveta. Pod kupolo je bronasta plošča, v katero so učvrščene tri diamantne igle. Na eno teh igel je bilo ob nastanku sveta položenih 64 plošč iz čistega zlata. Dan in noč menihi neumorno prestavljajo plošče z ene igle na drugo, po danih pravilih. Ko bodo prestavili vseh 64 plošč, bo konec sveta. Brahmanski stolp je seveda le domiselna zgodba, Hanojski stolp pa res obstaja, in to kot starodavna razvalina na tleh budističnega svetišča blizu mesta Hanoi [63]. Seveda pa je povezava z Lucasovo igrico le domneva. Lucas je problem zastavil takole: Imamo tri palice. Na eno je nasajenih osem plošč, od katerih so vse različnih velikosti in urejene padajoče po velikosti od spodaj navzgor. Prestavljamo lahko le po eno ploščo naenkrat. Večja plošča ne sme nikoli prekrivati manjše. Cilj je prestaviti vseh osem plošč na drugo palico . V tolažbo, da ni bojazni za skorajšnji konec sveta, je Lucas navedel podatek, da morajo menihi opraviti kar 18446 744 073 709 551 615 prestavitev. Če bi za vsako prestavitev potrebovali le po eno sekundo, bi prestavili stolp šele po več kot pet milijardah stoletij. Na sliki 1.3 so shematično prikazani klasični Hanojski stolpi, kot jih je zastavil Lucas. Sestavljeni so iz treh položajev in n ploščic. Položaje označimo z oznakami A, B in C, ploščice pa s števili od 1 do n. Število 1 predstavlja najmanjšo ploščico in število n največjo. 1 2 n-1 n ABC Slika 1.3: Shematično predstavljeni klasični Hanojski stolpi Za definicijo problema klasičnih Hanojskih stolpov je treba podati naslednja pravila: 4 POGLAVJE 1. UVOD 1. prestaviti je treba vseh n ploščic s položaja A na položaj C; 2. nalogo moramo opraviti z minimalnim številom potez; 3. naenkrat lahko prestavimo le eno ploščico; 4. prestavimo lahko le vrhnjo ploščico; 5. večje ploščice ne smemo postaviti na manjšo. Druga zahteva je marsikje le implicitno predpostavljena. Že sam Lucas je podal izraz 2n - 1 za minimalno število potez, da se prestavi stolp z enega položaja na drugega. V večini člankov o klasičnih Hanojskih stolpih je za potrebno število potez podan ta izraz. Ponekod je omenjen tudi kot minimalno število potez, vendar do članka [82], ki je bil objavljen leta 1981, ni dokaza minimalnosti nihče objavil. Dokaz je sicer tako trivialen, da smo lahko prepričani, da so ga imeli mnogi - zelo verjetno že Lucas. 1 2 n-1 n 0 1 2 … p-2 p-1 Slika 1.4: Shematično predstavljeni posplošeni Hanojski stolpi Na sliki 1.4 so shematično predstavljeni posplošeni Hanojski stolpi. V nadaljevanju bomo z izrazom posplošeni Hanojski stolpi, označevali Hanojske stolpe z več položaji in enakimi pravili prestavljanja kot pri klasičnih Hanojskih stolpih, spremeni se le besedilo prvega pravila: “Prestaviti je treba vseh n ploščic s položaja 0 na položaj p - 1.” Klasični Hanojski stolpi so tako le poseben primer posplošenih Hanojskih stolpov. V tem delu se bomo omejili na obravnavo posplošenih Hanoj-skih stolpov. Od postavitve klasičnega problema Hanojskih stolpov je minilo že več kot 120 let. V zadnjem obdobju se je zanimanje za različice in posplošitve klasičnega problema močno povečalo. Do sedaj je bilo napisanih že veliko člankov, v kar se lahko prepričamo, če si ogledamo sicer že nekoliko neažurno bibliografijo o Hanojskih stolpih [77], v kateri je navedeno preko dvesto člankov in knjig, ki podrobneje obravnavajo Hanojske stolpe in njihove variacije ter posplošitve. V bibliografijo so vključeni le računalniški in matematični teksti. Izpuščena so besedila iz psiholoških revij in mnogih knjig, ki le površno omenjajo Hanojske stolpe. Kljub starosti 5 problema še vedno ostaja precej odprtih vprašanj in domnev [22]. Obstaja veliko variacij osnovnih pravil in posplošitev. Ploščicam lahko poleg velikosti dodeljujemo dodatne atribute (recimo barvo [56]), položaje lahko razmeščamo v krog ali ravno linijo, gibanje ploščic omejimo le v določeno smer, le na sosednje položaje, dovolimo paralelne premike ploščic [83, 84], Poole v [62] predstavi tako imenovane stolpe z ozkim grlom, Minsker v [57] stolpe iz Antwerpna, Sapir pred kratkim v [66] stolpe s prepovedanimi prestavitvami itd. Znanih je mnogo povezav med Hanojskimi stolpi in pomembnimi matematičnimi pojmi, kot so recimo hiperkocke, ter z njimi povezana pojma Hamiltonov obhod in Grayevo kodiranje [15], trikotna krivulja Sierpińskega [29, 74] in Pascalov trikotnik [63]. Leta 1908 je Dudeney v prvem poglavju svoje znamenite knjige [8] prvi opisal verzijo Hanojskih stolpov s štirimi položaji in jo poimenoval Revova uganka (ang. Reve’s puzzle). V zgodbi je namesto ploščic in položajev uporabljal kolobarje sira in stole. Da bi Reve, junak zgodbe, zabaval romarje v Canterburyju, jim je zastavil uganko, pri kateri so morali prestaviti kup kolobarjev sira različnih velikosti z enega stola na drugega po pravilih klasičnega problema Hanojskih stolpov. Na voljo so imeli štiri stole. Za število sirov je Dudeney postavil vrednosti 8, 10 in 21. V razdelku z rešitvami je brez dokaza navedel število potez za prestavitev sirov: 33, 49 in 321. Skiciral je tudi odgovor za vse primere, kjer je število sirov trikotniško število (glej stran 42). Če označimo z M(n) minimalno število potez za prestavitev stolpa iz n sirov in definiramo trikotniško število s tk = 12k(k+1), je po Dudeneyu M(tk) = 2M(tk-1)+ 2k -1. Iz te formule lahko izračunamo vrednosti M(10) in M(21), vendar Dudeney ni opisal algoritma, niti ni povedal ničesar o netrikotniških številih, kot je na primer 8. Revova uganka se je ponovno pojavila v literaturi leta 1939 kot problem št. 3918 v American Mathematical Monthlyju [71], kjer je bila posplošena na poljubno število položajev. Leta 1941 sta bili istočasno objavljeni dve rešitvi, Frama [11] in Stewarta [72]. Takratni urednik problemov v reviji American Mathematical Monthly Dunkel je že v isti številki [9], kjer sta bili objavljeni rešitvi Frama in Stewarta, opozoril, da dokazi optimalnosti veljajo le za predstavljeno strategijo prestavljanja ploščic. Avtorja sta pokazala, katere vrednosti parametrov predstavljenega algoritma mi-nimizirajo število potez, nista pa dokazala, da je to tudi v splošnem optimalni algoritem. Takega dokaza še danes ni, zato moramo Frame-Stewartovo rešitev označevati le kot domnevno optimalno rešitev. Od leta 1941 ni glede optimalnosti algoritma nobenih novih rezultatov. Mnogi avtorji le ponovno odkrivajo Frame-Stewartov algoritem in ga predstavljajo v ra- 6 POGLAVJE 1. UVOD zličnih oblikah. Da so mnoge od domnevno optimalnih strategij dejansko enakovredne, je dokazano v [33], kar je tudi vsebina poglavja 4. Mnogi so napačno mislili, da so z izpeljavo optimalne vrednosti parametrov algoritma dokazali tudi optimalnost samega algoritma. V člankih zadnjih dveh desetletij so se avtorji precej ukvarjali tudi z iterativnimi algoritmi [4, 18, 42, 43, 44, 64], ki so glede na strategijo prestavljanja ploščic enakovredni Frame-Stewartovemu algoritmu. Dostopnost problema in njegova popularnost ima tako tudi negativne posledice, objavljenih je precej prispevkov, ki rezultate obravnavajo matematično nekorektno, ne vpeljejo stroge formulacije, navajajo trditve brez dokazov, domnevo obravnavajo kot resnico itd. Mnogo rezultatov se tudi ponavlja brez ustreznega sklicevanja na njihov izvor. Med prispevki, ki ne prinašajo nič bistveno novega, v katerih se vsebina izjemno ponavlja, bi lahko izpostavili Majumdarja [27, 46–52]. Med temi še posebej izstopa članek [47], v katerem avtor trdi, da je dokazal optimal-nost Frame-Stewartovega algoritma za štiri položaje, kljub temu pa kasneje napiše še celo vrsto člankov o isti temi, vendar se v njih ne sklicuje na svoj “rezultat”. Hinz je s člankom [19] dobro razčistil neurejeno stanje tako v zgodovinskem kot tudi v formalnem matematičnem smislu. Problem Hanojskih stolpov je dobro matematično formuliral, navedel znane rezultate, podal domneve ter definiral nekaj odprtih problemov. Lep pregleden članek o Hanojskih stolpih predstavi leta 1994 tudi Poole v [63]. Nekaj avtorjev je že izrazilo dvom, da bo sploh komu uspelo dokazati optimal-nost algoritma. Tako npr. Lunnon v [45] omenja korespondenco med Donaldom Knuthom in Martinom Gardnerjem, v kateri Knuth izrazi dvom in pove, da je problem res težak. V uvodnem poglavju knjige Concrete Mathematics [13] je pri nalogah v razdelku “raziskovalni problemi” podan problem dokaza minimalnega števila premikov ploščic pri štirih položajih. V enem od svojih znamenitih nastopov pod naslovom All Questions Answered je Knuth za primer s štirimi položaji omenil, da obstaja mnogo različnih minimalnih poti, problem pa je v tem, da ne poznamo načina, kako podati karakterizacijo vseh teh rešitev [34, stran 321]. Hinz je glede rešitve bolj optimističen [21] in pravi, da je pač potrebno še nekaj dela. Zdi se mu, da je prava usmeritev nadaljnjega iskanja odgovora v preučevanju grafov posplošenih Hanojskih stolpov. Zaenkrat ni znano niti to, ali je premer grafa enak razdalji med popolnima stanjema. Tako kot domnevno optimalni algoritem se veliko avtorjem tudi ta domneva zdi samoumevna in je ne izpostavljajo kot odprt problem [45]. Disertacija je v nadaljevanju sestavljena takole. V drugem poglavju bomo vpeljali pojem stanja posplošenih Hanojskih stolpov in predstavili popoln opis stanja, s katerim opišemo razmestitev vseh ploščic. Predstavili bomo tudi delni opis stanja, s katerim opišemo le razmestitve vrhnjih ploščic. Definirali bomo 7 preslikavo, ki popoln opis preslika v delni opis. To preslikavo bomo obravnavali z različnih vidikov, ugotavljali njeno surjektivnost in injektivnost. Navedli bomo pogoj, kateremu mora zadostiti delni opis, da je v sliki preslikave. S pomočjo tega pogoja bomo na dva načina prešteli vse elemente v množici slik preslikave, to je število vseh različnih možnih delnih opisov. Vpeljali bomo funkcijo, s pomočjo katere bomo izračunali število vseh različnih popolnih opisov stanj, katerim ustreza isti delni opis. Navedli bomo pogoj, kdaj delnemu opisu ustreza enoličen popolni opis in prešteli število takih stanj. Ugotovili bomo, da je delni opis zadosten, da poznamo vse možnosti za naslednjo prestavitev ploščice. Izpeljali bomo funkcijo, s katero bomo izračunali stopnjo stanja in jo podrobneje obravnavali. V tretjem poglavju bomo definirali graf stanj posplošenih Hanojskih stolpov. Opisali bomo označevanje točk s števili z osnovo p. Razmišljali bomo o strukturi grafa, ter prikazali njegovo rekurzivno konstrukcijo. Vpeljali bomo dva tipa indu-ciranih podgrafov. Prvi tip podgrafov bomo dobili z omejitvijo razmestitve ploščic na podmnožico položajev, drugi tip pa s fiksiranjem razmestitve določenega števila največjih ploščic. Glavni rezultat tega poglavja je preštetje vseh povezav grafa. Prešteli jih bomo na dva načina, prvič s preštevanjem točk z enako stopnjo, drugič z rekurzivnim nastavkom, ki ustreza strukturi grafa. Iz izraza za število povezav bomo dobili nekaj zanimivih številskih zaporedij. Prešteli bomo tudi prestavitve posamezne ploščice. Izpeljali bomo minimalno, maksimalno in povprečno stopnjo grafa. V četrtem poglavju definiramo pet strategij reševanja problema posplošenih Hanojskih stolpov, med katerimi sta tudi domnevno optimalni Framova in Stewar-tova strategija iz leta 1941 [11, 72]. Dokažemo, da so, glede na število premikov ploščic, enakovredne. Optimalnost teh strategij ni dokazana, zato še vedno veljajo za domnevno optimalne strategije. Dokaz optimalnosti je sicer med najbolj zanimivimi odprtimi problemi posplošenih Hanojskih stolpov. V petem poglavju spoznamo najnujnejše o teoriji kodiranja in popolnih kodah v grafih. Predstavimo zgodovino nastanka grafov Sierpińskega ter omenimo rezultate, ki so motivirali raziskovanje popolnih kod v grafih Sierpińskega. Predstavimo posplošitev teh rezultatov, obstoj 1-popolnih kod v grafih Sierpińskega. Predstavljeni pristop je bistveno drugačen od znanega pristopa za grafe klasičnih Hanojskih stolpov. Podrobneje si ogledamo tudi optimalen algoritem za dekodi-ranje, katerega implementacija je priložena v dodatku A. 8 POGLAVJE 1. UVOD Poglavje 2 Kombinatorika Hanojskih stolpov V tem poglavju bomo obravnavali nekatere kombinatorične lastnosti posplošenih Hanojskih stolpov. V prvem razdelku bomo vpeljali pojem stanja posplošenih Hanojskih stolpov in predstavili popoln opis stanja, s katerim opišemo razmestitev vseh ploščic. Nekatera posebna stanja bomo poimenovali. V drugem razdelku bomo predstavili delni opis stanja, s katerim opišemo le razmestitve vrhnjih ploščic. Vpeljali bomo preslikavo, ki popoln opis preslika v delni opis. To preslikavo bomo obravnavali z različnih vidikov, ugotavljali njeno surjektivnost in injektivnost. Navedli bomo pogoj, kateremu mora zadostiti delni opis, da je v sliki preslikave. S pomočjo tega pogoja bomo na dva načina prešteli vse elemente v množici slik preslikave, to je število vseh različnih možnih delnih opisov. V tretjem razdelku bomo vpeljali funkcijo, s pomočjo katere bomo izračunali število vseh različnih popolnih opisov stanj, katerim ustreza isti delni opis. Navedli bomo pogoj, kdaj delnemu opisu ustreza enoličen popolni opis in prešteli število takih stanj. V zadnjem, četrtem razdelku, bomo ugotovili, da je delni opis zadosten, da poznamo vse možnosti za naslednjo prestavitev ploščice. Izpeljali bomo funkcijo, s katero bomo izračunali stopnjo stanja in jo podrobneje obravnavali. 2.1 Stanja Pri posplošenih Hanojskih stolpih velja pravilo, da večja ploščica ne sme ležati nad manjšo, in ker so vse ploščice različnih velikosti, je vrstni red ploščic razmeščenih na posamezen položaj vedno enolično določen. Razvrščene so po velikostnem redu, od največje spodaj do najmanjše zgoraj. Torej je informacija o razmestitvi ploščic po položajih zadostna za popoln opis posplošenih Hanojskih stolpov. V literaturi se ponekje obravnava tudi stanja, kjer so lahko ploščice na posameznem položaju razvrščene v poljubnem vrstnem redu. V takih primerih se razlikuje med stanji, ki upoštevajo pravilo “manjša ploščica nad večjo” in stanji, ki 9 10 POGLAVJE 2. KOMBINATORIKA HANOJSKIH STOLPOV to pravilo kršijo. Prva so poimenovana regularna in druga neregularna. Ker bomo obravnavali le regularna stanja, bomo v nadaljevanju z izrazom stanje posplošenih Hanojskih stolpov vedno razumeli regularno stanje. Naj bo D = {1,2,...,n} množica vseh ploščic in P = {0,1,... ,p- 1} množica vseh položajev. Vsaka podmnožica kartezičnega produkta RCDxP predstavlja neko relacijo med ploščicami in položaji. Število vseh takšnih različnih relacij je 2|D|.|P| = 2ap. Ker ploščice razmeščamo po položajih in mora vsaka ploščica ležati na natanko enem položaju, nas bodo od vseh relacij zanimale le tiste, pri katerih kot prvi element urejenih parov nastopijo vse ploščice in sicer natanko enkrat. Taki relaciji pravimo funkcija ali preslikava. Število vseh različnih preslikav iz množice ploščic v množico položajev je pn, saj imamo za vsako od n ploščic natanko p možnosti, razporedimo (preslikamo) jo lahko na kateregakoli od p položajev. Vsaka preslikava / iz D v P tako predstavlja stanje posplošenih Hanojskih stolpov. Ker so elementi množice D naravna števila od 1 do n, lahko preslikavo / opišemo z urejeno n-terico (/(l),/(2),...,/(n)). Če z Zp označimo množico števil od 0 do p - 1, lahko stanje enolično opišemo z n-terico r G (Zp)n = {0,1,...,p- l}n. Bolj natančno, r = (n, r2,... , rra_i,rra), kjer komponenta rd označuje položaj, na katerem leži ploščica d. Primer stanja na p = 5 položajih z n = 6 ploščicami je prikazan na sliki 2.1. Podana je ustrezna 6-terica r, kot tudi 5-terica s, ki pa jo bomo definirali v naslednjem razdelku. r=(3,3,3,0,2,0) s=(4,0,5,1,0) 5 1 0 12 Slika 2.1: Stanje Stanje imenujemo popolno, če vse ploščice ležijo na istem položaju. Na sliki 2.2 je prikazan primer popolnega stanja z vsemi ploščicami na položaju 3. Stanje imenujemo razgrnjeno, če nobeni dve ploščici nista na istem položaju. Primer razgrnjenega stanja je prikazan na sliki 2.3. Za n > p seveda razgrnjeno stanje ni možno. Stanje imenujemo delno razgrnjeno stanje, če so za določen k > 1 ploščice 1,... , k na skupnem položaju, medtem ko so ploščice k + l,...,n vsaka na svojem položaju. Primer delno razgrnjenega stanja je prikazan na sliki 2.4. 2 6 3 3 4 2.1. STANJA 11 r=(3,3,3,3,3,3) s=(0,0,0,1,0) 1| 5 6 0 123 Slika 2.2: Popolno stanje r=(1,4,0,2) s=(3,1,4,0,2) 3 1 4 r=(3,3,3,2,4,0) s=(6,0,4,1,5) 0 123 Slika 2.3: Razgrnjeno stanje 6 1 2 4 3 5 0 123 Slika 2.4: Delno razgrnjeno stanje Delno razgrnjeno stanje, v katerem je k = n, je popolno stanje in delno razgrnjeno stanje, v katerem je k = 1, je razgrnjeno stanje. Naj bo r = (r1, r2, . . . , rn-1, rn) stanje posplošenih Hanojskih stolpov. Stanje r je popolno natanko takrat, ko so vse komponente ri enake. Stanje r je razgrnjeno natanko takrat, ko velja ri = rj za vse i = j. In nazadnje, stanje r je delno razgrnjeno natanko takrat, ko obstaja tak k ? 1, da so vse komponente ri za i ? k enake in velja ri = rj = r1 za vse i,j > k,i = j. 2 3 4 2 4 4 12 POGLAVJE 2. KOMBINATORIKA HANOJSKIH STOLPOV 2.2 Vrhnje ploščice Ker prestavimo naenkrat le eno od vrhnjih ploščic, informacija o vseh vrhnjih ploščicah zadošča, da poznamo vse možnosti za naslednjo prestavitev ploščice, in s tem vse prehode iz danega stanja v naslednje, sosednje stanje. Zaradi tega razloga vpeljemo funkcijo Tn>p : (Zp)n -> (Zn+l)p na naslednji način. Definicija 2.2.1. Naj bon>linp>3. Funkcija Tn>p preslika urejeno n-terico r E (Zp)n v urejeno p-terico s G (Zn+1)p TntP: (ri,r2,...,rra)i->(so,Si,...,sp_i) tako, da velja si 0; rk ^ i za 1 < k < n, min {k I rk = i}: sicer. l 1 in p > 3 vedno velja pn < (n + If. Torej funkcija Tn>p ne more biti surjektivna. Funkcija Tn>p ni surjektivna tudi zaradi tega, ker se nobena n-terica ne preslika v p-terico (0,.'..,0), kar bi pomenilo, da so vsi položaji prazni. Tudi p-terici (2,3,4,5) in (2,1,4,4) nista nikoli v sliki funkcije Tn>p. V prvem primeru najmanjša _ 1 3 2 0 1 2 2.2. VRHNJE PLOŠČICE 13 ploščica 1 ni vrhnja na nobenem položaju in v drugem primeru naj bi bila ploščica 4 istočasno vrhnja na dveh položajih. Funkcija Tns> v splošnem tudi ni injektivna, saj lahko eni p-terici ustreza več različnih ra-teric. Na sliki 2.5 sta za primer prikazani dve različni razmestitvi treh ploščic po treh položajih, (0,1, 0) in (0,1,1), za kateri je opis vrhnjih ploščic enak (1,2,0). Opis vrhnjih ploščic je enak za vse take razmestitve ploščic, pri katerih so vrhnje fiksirane na svojih položajih, vsaka nevrhnja ploščica pa lahko leži pod katerokoli manjšo vrhnjo ploščico. Funkcija Tn>p je injektivna le za n < 2, saj je v tem primeru lahko nevrhnja ploščica le 2, leži pa lahko le pod vedno vrhnjo ploščico 1. Naj K{TntP) označuje sliko funkcije Tn>p in \K{TntP)\ število njenih elementov. Navedimo naslednjo lemo, ki jo bomo koristno uporabili pri izračunu \K{TntP)\. Lema 2.2.2. Če imamo s = (s0, s1}..., sp_i) G {Zn+lf, potem je s G K{TntP) natanko takrat, ko veljata naslednja pogoja: (u): 3ie{0,...,p-l}:Si = 1, (v): Vi, j G {0,... ,p - 1}: st = s, ^(i = jVs, = 0). Dokaz. O potrebnosti obeh pogojev razmislimo takole. Prvič, najmanjša ploščica mora biti ena izmed vrhnjih ploščic, saj nanjo ne moremo položiti nobene druge. Drugič, nobena ploščica ne more biti istočasno vrhnja na dveh različnih položajih. Razmislimo sedaj še o zadostnosti obeh pogojev. Predpostavimo, da p-terica s = (s0, si,... , sp_i) zadošča obema pogojema. Pokazati moramo, da potem obstaja tak r = (n,r2,..., rn) G (Zp)n, za katerega velja Tn>p{r) = s. Komponente n definirajmo v dveh korakih takole: 1. Za vsak neprazen položaj i, z vrhnjo ploščico Si ^ 0, lahko določimo komponento rSi = i. Po pogoju (v) je tak i enolično določen. 2. Za vse druge ploščice j, ki niso vrhnje, določimo komponento Tj = n, torej jih postavimo na položaj, kjer leži najmanjša. Ker pogoj (u) zahteva, da je najmanjša ploščica vedno ena izmed vrhnjih ploščic, je bila komponenta n gotovo že določena v prejšnjem koraku. Po takem postopku smo vsem komponentam n-terice r določili vrednost, to pomeni, vsako ploščico smo razmestili na določen položaj. Tako definirana n-terica r predstavlja stanje, za katero velja Tn>p{r) = s. D V naslednji trditvi bomo potrebovali zmnožek oblike n(n - l)(n - 2) ¦ ¦ ¦ (n-k + 1), ki ga imenujemo padajoča fakulteta in označujemo z nk [13, stran 47]. Izračunajmo sedaj število p-teric, ki so slike vsaj ene n-terice, to je velikost slike funkcije %tP. 14 POGLAVJE 2. KOMBINATORIKA HANOJSKIH STOLPOV Trditev 2.2.3. Za vsak p > 3 in n > p velja p—i fc=0 Dokaz. Po pogoju (u) leme 2.2.2 je najmanjša ploščica vedno vrhnja. Razdelimo množico vseh p-teric iz K{Tn>p) na množice, v katerih je najmanjša ploščica fiksirana na določenem položaju. Tako dobimo p disjunktnih in enako velikih podmnožic. S k označimo število nezasedenih položajev, kar v p-terici pomeni število ničel. Število vseh izborov k nezasedenih položajev izmed preostalih p - 1 položajev je enako f;1). Če je k položajev nezasedenih, potem je p- k zasedenih. Na enem od zasedenih položajev je najmanjša ploščica, na vsakega od preostalih p - k - 1 pa lahko razporedimo katerokoli ploščico razen najmanjše. Po pogoju (v) leme 2.2.2, ki pravi, da so vse vrhnje ploščice različne, imamo (n - l) ((n - 1) - l) • • • ((n - 1) - (p - 1 - k - 1)) = (n - l)S=h=l možnosti za izbor p-k-l vrhnjih ploščic. Če upoštevamo še pravilo produkta pri izračun vseh možnosti, dobimo za k nezasedenih položajev p{^~kl){n - l)2ds=l različnih p-teric. Iz najmanjšega faktorja (n - 1) - (p - 1 - k - 1) vidimo, da mora veljati n-l>p-l-k-l, da dobimo vrednost večjo od 0. V primeru, da je n < p, mora torej za najmanjši faktor veljati k > p - n. D p Za primere 1 < n < p tečejo vrednosti k v vsoti trditve 2.2.3 od p - n do 1. Izraz (n - l)Ez*zi kombinatorično predstavlja število urejenih izbir brez ponavljanja p-k-l vrhnjih ploščic izmed n - 1 ploščic. Izraz (n - l)2zhzl lahko interpretiramo še drugače, to je število vseh injektivnih preslikav množice p-k-l nepraznih položajev v množico n - 1 ploščic. Posledica 2.2.4. Naj bop>3, potem velja \K(Tn>p)\ = pnp~l + 0(np~2). Dokaz. Razvijmo izraz za velikost slike funkcije Tn>p iz trditve 2.2.3 v polinom: \n(Tn,p)\ =p(p~ XV- iy—+p(p~ XV-1)^+ ...+p(P~1\n- 1)^±± +...+pfP-1\n-i)l + pfP-1\n- i)fi p~1 'p- r p(n - l)(n - 2)... (n - p + 1) + J] P l\n - l)Ez*zi fc=i pnp-1 + O(np-2). _ _ 2.2. VRHNJE PLOŠČICE 15 Vodeči člen polinoma dobimo pri k = 0. D Videli smo, da predstavlja slika funkcije %tP pravo podmnožico množice vseh p-teric, saj nekatere p-terice zaradi pogojev (u) in (v) iz leme 2.2.2 ne morejo biti v sliki funkcije Tn>p. V posledici 2.2.4 vidimo, da je število p-teric v polinomski odvisnosti od števila ploščic, medtem ko je število vseh n-teric, to je vseh stanj, v eksponentni odvisnosti od števila ploščic. Torej je ta posledica potencialno zanimiva z algoritmičnega stališča, saj je eksponentno število stanj vir številnih težav pri reševanju problemov posplošenih Hanojskih stolpov. V lemi 2.2.2 smo pokazali potrebna in zadostna pogoja (u) in (v), da je p-terica s = (s0, s1}... , sp_i) G (Zn+1)p v sliki funkcije Tn>p. Navedimo sedaj lemi 2.2.2 ekvivalentno formulacijo za p-terice, ki niso v sliki funkcije Tn>p. Če lemo 2.2.2 zapišemo z logičnim izrazom w ^^ (u) A (v), jo lahko zapišemo tudi z besedilom, ki ustreza ekvivalentnemu logičnemu izrazu -w ^^ ((-u) V (-t;)). Lema 2.2.5. Če imamo s = (s0, su..., sp_i) G (Zn+i)p, potem s i n(%tP) natanko takrat, ko velja vsaj eden od naslednjih dveh pogojev: (-u): V« G {0,...,p-l} :st^ 1, (-v): 3i, 3j G {0,... ,p - 1}: i ^ j A st ^ 0 A st = sr D Pogoj (u) opisuje p-terice, kjer najmanjša ploščica ne nastopa kot vrhnja. Pogoj (t;) opisuje p-terice, kjer sta vsaj dva položaja z enakima vrhnjima ploščicama. Preštejmo vse p-terice, ki ustrezajo pogoju («) A (v). To so p-terice, kjer najmanjša ploščica ni vrhnja, na vseh zasedenih položajih pa so različne vrhnje ploščice. Število teh p-teric je \{s | (-«) A (v)}\ = J2 (f) (n ~ l) k- Indeks k predstavlja število zasedenih položajev. Vrednost k = 0 predstavlja p-terico (0, 0,... , 0) in vrednost izraza v vsoti je 1. Izmed vseh p položajev lahko k zasedenih položajev izberemo na g) različnih načinov. Za izbor k različnih vrhnjih ploščic izmed n - 1 največjih, imamo (n - l)k možnosti, to je toliko, kot je število injektivnih preslikav iz množice k zasedenih položajev v množico n - 1 ploščic. Preštejmo vse p-terice, ki ustrezajo pogoju (w). To so p-terice, kjer sta na vsaj dveh zasedenih položajih vrhnji ploščici enaki. Število teh p-teric je \{s i ->i = Yl i1!) Yl {k j n~- fc=2 i=\ 16 POGLAVJE 2. KOMBINATORIKA HANOJSKIH STOLPOV V zgornjem izrazu smo s J označili Stirlingova števila druge vrste [13, stran 258]. Z njimi označujemo število particij množice s k elementi v i nepraznih podmnožic. Indeks k predstavlja število zasedenih položajev. Indeks i predstavlja število ploščic, ki jih uporabimo za vrhnje, zavzame pa vse vrednosti manjše od k, to je od 1 do k - 1. Izmed n ploščic lahko i vrhnjih izberemo na Q) različnih načinov. Število surjektivnih preslikav k zasedenih položajev na množico i vrhnjih ploščic je i\ { k. }. Če oba izraza zmnožimo, dobimo (")«!{•} = { • } n. Tako smo prešteli elemente slike preslikave Tn>p še na drug način \n(Tn,p)\ = (n+l)p-\{s | (-u) A (v)}\ - \{s | (-t;)}| P /\ p /\ fc-i k k k % fc=0 fc=2 i=\ in obenem dobili naslednjo kombinatorično enakost vy(V~l\n- l)E=*zi + f^ (V\ (n - 1)* + L Q J] ^ (n+ir = pj]pfc1)^-i)Lz^i+ž^^-i)-+ž^5]H^ fc=0 ' fc=0 fc=2 i=\ fc=l fc=2 v kateri ločeno preštejemo tri različne tipe p-teric. Število 1 v zgornji enakosti predstavlja p-terico (0, 0,... , 0), prva vsota predstavlja število p-teric z različnimi vrhnjimi ploščicami, druga vsota predstavlja število p-teric z vsaj dvema položajema z enakima vrhnjima ploščicama. 2.3 Praslike funkcije TU)P Naj bo s G n(Tn>p). S %>p-l{s) bomo označevali množico vseh n-teric, ki jih funkcija Tn>p preslika v s. Zanima nas, koliko je vseh takih n-teric, ki jih funkcija Tn>p preslika v s. Torej, izračunati želimo število elementov v prasliki p-terice s, to'je \Tn,p~\s)\. V ta namen bomo vpeljali naslednjo funkcijo. Definicija 2.3.1. Za število d e N0 in p-terico s = (sQ, s1}..., sp_i) G (Zn+l)p naj bo h(d, s) = \{i G {0,... ,p - 1} | 0 < st < d}\. Za vsak d G N in s G (Zn+l)p velja 0 < h(d, s) < p. Funkcija h(d, s) je sicer definirana za vse p-terice s G (Zn+i)p, vendar pa nas bo zanimala le za tiste, ki so v sliki funkcije Tn>p, to je s G K{Tns>). 2.3. PRASLIKE 17 Za s G K(Tn>p) lahko vrednost h(d, s) interpretiramo kot število tistih vrhnjih ploščic p-terice s, ki so manjše od ploščice d. Funkcija h(d, s) nam torej pove, pod koliko vrhnjih ploščic bi lahko razmestili ploščico d. Vrednost h(d, s) je enaka 0 le v primeru d = 1. Ploščica 1 je najmanjša, zato je vedno vrhnja, in je ne moremo razmestiti pod nobeno drugo. Ko za vsak i velja 0 < si < d, je h(d, s) = p. V tem primeru imamo zasedenih vseh p položajev in vse vrhnje ploščice so manjše od d. Za s G K{TntP) vrednost h(n+l, s) pove, koliko vrhnjih ploščic je manjših od števila n+1, in ker so seveda vse ploščice manjše odn+1, je h{n + 1, s) število vrhnjih ploščic v p-terici s, to je neničelnih komponent v s. Lema 2.3.2. Naj bo s G n{Tn>p), potem velja (1; h(n+l,s) = n, n J] h(i,s); sicer. Dokaz. Če je h(n+l,s) = n, je vsaka ploščica v p-terici s vrhnja. Razporeditev ploščic je natanko določena, na položaju i leži ploščica si. V množici %tp-l{s) je torej v primeru h(n + 1, s) = n ena sama n-terica r = (s0, su ... , sp_i), iz česar sledi, da je praslika s enolična, \Tn>p-l{s)\ = 1. Predpostavimo sedaj, da vsaj'ena ploščica v Tn^\s), recimo i, ni vrhnja. Potem je vrednost h{i,s) neničelna in predstavlja število položajev, na katerih so manjše vrhnje ploščice in pod katere je lahko ploščica i razmeščena v stanjih, katerim ustreza s. Torej je \Tn>p-l{s)\ vsaj f]* h{i, s), kjer i teče preko vseh nevrh-njih ploščic. Če razmislimo drugače, ploščico i lahko razmestimo na položaj j le v primeru, da velja i > sj. Če obstaja več ploščic, ki jih lahko razmestimo na isti položaj, morajo biti na tem položaju urejene po velikosti, kar pomeni, da so lahko razmeščene na en sam način. Torej je IT^"1s)! največ f]* h i, s). D Pogoj, da je praslika s enolična, je karakteriziran v naslednjem izreku. Izrek 2.3.3. Naj bo Tns>{r) = s, potem velja Tntp-\s) = {r} natanko takrat, ko je r delno razgrnjeno stanje. Dokaz. Predpostavimo najprej, da je r delno razgrnjeno stanje. Videli smo že, da sta popolno in razgrnjeno stanje tudi delno razgrnjeni stanji (stran 10). Potem lahko z uporabo leme 2.3.2 enostavno pokažemo, da velja \Tn^\s)\ = 1. Pri delno razgrnjenem stanju namreč ploščice, ki niso vrhnje, lahko ležijo le na položaju z najmanjšo vrhnjo ploščico, saj so vse vrhnje ploščice, razen najmanjše, večje od nevrhnjih. Dokažimo trditev še v drugo smer. Predpostavimo, da velja Tn>p-l{s) = {r}. Iz leme 2.3.2 sledi, da imamo v tem primeru ali h(n + l,s) = n ali f h{i, s) = 1. 18 POGLAVJE 2. KOMBINATORIKA HANOJSKIH STOLPOV V prvem primeru je n vrhnjih ploščic manjših odn + 1, torej imamo razgrnjeno stanje, ki je tudi delno razgrnjeno stanje. Predpostavimo sedaj, da imamo Uih(i,s) = 1. Sledi, daje množica indeksov tega produkta neprazna, predstavlja množico nevrhnjih ploščic, in za vsak tak indeks i velja h{i,s) = 1. Naj bo i tako število, da velja h{i,s) = 1. Seveda je z > 1, saj iz leme 2.2.2 sledi, da vedno obstaja tak položaj j, za katerega velja Sj = l, najmanjša ploščica je vedno vrhnja. Torej velja i > Sj in ker je h(z, s) = 1, mora ploščica i ležati na položaju j. Torej, vse nevrhnje ploščice z, za katere velja h(i,s) = 1, morajo ležati na istem položaju, to je na položaju, na katerem je najmanjša ploščica vrhnja. Če je število takih ploščic i enako n - 1, je r popolno stanje, ki je tudi delno razgrnjeno stanje. Sicer pa za vsako drugo ploščico k obstaja tak t, da velja k = st, torej vse druge ploščice so vrhnje in seveda ležijo na drugih položajih kot j, iz česar sklenemo, da imamo delno razgrnjeno stanje. D Glede na to, da so delno razgrnjena stanja nekaj posebnega, jih preštejmo. Trditev 2.3.4. Označimo z ap>n število vseh delno razgrnjenih stanj posplošenih Hanojskih stolpov s p položaji in n ploščicami. Velja Wn>l : a1>n=l, Vp > 1 : apA = p, Wp>l,Wn>l : ap,n=p(l + ap.1,n.1). Dokaz. Če imamo en sam položaj, imamo tudi eno samo stanje in sicer popolno, ki je hkrati tudi delno razgrnjeno, zato velja a1>n = 1. Če imamo eno samo ploščico, imamo toliko stanj, kot je položajev, vsako od teh stanj je popolno, ki je hkrati tudi delno razgrnjeno, zato velja apA = p. Delno razgrnjeno stanje je stanje, ko za nek k velja, da so ploščice 1,2,...,n-fc + lna skupnem položaju z najmanjšo na vrhu, medtem, ko za preostalih k - 1 največjih ploščic velja, da je vsaka na svojem položaju. V tem primeru k predstavlja število zasedenih položajev. Če je n < p, lahko k zavzame vrednosti iz {1,2,...,n), če pa je n > p, lahko k zavzame vrednosti iz {1, 2,...,p}. Število delno razgrnjenih stanj s k zasedenimi položaji je enako številu injektivnih preslikav iz množice k vrhnjih ploščic v množico p položajev, torej jA Množica k vrhnjih ploščic je pri delno razgrnjenem stanju enolično določena, v njej so najmanjša in k-l največjih ploščic, {l,n - k + 2, n - k + 3,..., n}. Če je n > p, je lahko nepraznih položajev katerokoli število od 1 do p, zato 2.3. PRASLIKE 19 velja p p k—l k=\ k=\i=0 = p + p(p-l)+p(p-l)(p-2) + ...+p(p-l)...2+p\ p! p! p! p! + + +...+ +p! (p-1)! (p-2)! (p-3)! .....2! / (p-1)! (p-1)! (P-1)! p I 1 + j------ + j------ + ... + + (p - 1)! P i + J]^-1)") =P(1 + «P-I,n)- (2.1) fc=l Če je n < p, je lahko nepraznih položajev največ n, zato velja n n k—l k=\ k=\ i=0 p n—l 1 + J](p-1)^ =p(l + ap_1)„_1). (2.2) fc=i V primeru n > p pravzaprav indeksa n v ap>n sploh ne bi potrebovali, saj velja enakost \/n > p,\/m > p : ap,n = Op>m, in ker za n > p velja n>p-linn-l>p-l, sledi n > P : ap_i)ra = ap_i,n_i. Tako lahko obe rekurzivni formuli (2.1) in (2.2) zapišemo z eno samo, aP,n = p(l + aP-i,n-i). D Rekurzivno formulo ap>ra = p(l+ap_1>ra_1) = p+pap_1)ra_! si lahko razložimo tudi takole. Za razmestitev ploščic v popolno stanje imamo p možnosti. Za razmestitev v delno razgrnjeno stanje, ki ni popolno, imamo pap_i,ra_i možnosti. Delno razgrnjeno stanje, ki ni popolno, ima vsaj eno največjo ploščico na svojem položaju. Za razmestitev največje ploščice imamo p možnosti, za razmestitev preostalih n - 1 ploščic na preostale p - 1 položaje v delno razgrnjeno stanje pa imamo ap_i,ra_i možnosti. _ _ _ 20 POGLAVJE 2. KOMBINATORIKA HANOJSKIH STOLPOV Celoštevilsko zaporedje ap,n = p(1 + ap-1,n-1) za n ? p najdemo v Sloanovi bazi celoštevilskih zaporedij [70] pod identifikacijsko številko A007526. Zapisano je z rekurzivno formulo an = n(1 + an-1) in velja Op,n ap; an; n> p, n < p. Vrednost an lahko interpretiramo kot število permutacij elementov nepraznih podmnožic {1,2,..., n}. Za primer v tabeli 2.1 navedimo vseh 15 permutacij elementov nepraznih podmnožic množice treh elementov {1,2, 3}: podmnožica permutacije elementov število permutacij 1 1 1 2 2 2 6 15 Tabela 2.1: Permutacije elementov nepraznih podmnožic {1,2,3} {1} 1 {2} 2 {3} 3 {1,2} 12, 21 {2,3} 23, 32 {1,3} 13, 31 {1,2,3} 123, 132, 213, 231, 312, 321 V množici z n elementi imamo za izbor k elementov Q možnosti. Število permutacij k elementov je k\, zato lahko zapišemo an fc=i fc=i V našem primeru preštevanja delno razgrnjenih stanj smo iskali število per-mutacij elementov nepraznih podmnožic množice p položajev. Pri k zasedenih položajih razmeščamo enolično določeno množico k vrhnjih ploščic na k položajev, torej vsaka razmestitev k vrhnjih ploščic na izbrano podmnožico k položajev ustreza eni od permutacij teh k položajev. Navedimo še prvih deset členov zaporedja an: n 12345 6 7 8 9 10... an 1 4 15 64 325 1956 13699 109600 986409 9864100 ... _ _ 2.4. STOPNJA STANJ 21 2.4 Stopnja stanj V prejšnjem razdelku smo spoznali, da je velikost slike funkcije %tP v polinom-ski odvisnosti od števila ploščic. Torej se ponuja naravno vprašanje, do kakšnih sklepov nas lahko pripelje le informacija o sliki funkcije Tns>. Dve stanji sta sosednji, če lahko med njima preidemo z'eno samo prestavitvijo ploščice. Število sosedov stanja imenujemo stopnja stanja. Sedaj bomo pokazali, kako lahko izračunamo stopnjo stanja r le z uporabo informacije o Tn>p{r). Trditev 2.4.1. Naj bo Tn>p(r) = s, potem je stopnja stanja r enaka h(n+l,s)(p--) --h(n+l,s) 2 . Dokaz. Vse dovoljene prestavitve ploščic iz stanja r bomo razdelili v dva tipa in jih ločeno prešteli: (i) prvi tip bodo prestavitve ploščic z zasedenega na nezasedeni položaj, (ii) drugi tip bodo prestavitve ploščic z zasedenega na zasedeni položaj. (ad i) Število zasedenih položajev je enako h(n+l, s) in število nezasedenih položajev je enako p-h(n+l,s). Vsako vrhnjo ploščico lahko prestavimo na katerikoli nezaseden položaj, torej imamo h(n + l, s)(p-h(n + l, s)) prestavitev tega tipa. (ad ii) Premisliti moramo še o prestavitvah, pri katerih prestavimo vrhnjo ploščico na zasedeni položaj. Spomnimo se, da so vse h(n + l, s) vrhnje ploščice različne, zato lahko najmanjšo prestavimo na katerokoli od preostalih h(n + 1, s) - 1 večjih, drugo najmanjšo na katerokoli od preostalih h(n + l,s)-2 večjih in tako dalje, vse do predzadnje najmanjše, ki jo lahko prestavimo le še na največjo vrhnjo ploščico. Če vse prestavitve tega tipa seštejemo, dobimo izraz h{n+l,s)-l l +l,s)-l)h(n + V i=-(h(n+l,s)-l)h(n+l,s) %=\ za število različnih prestavitev z zasedenega na zasedeni položaj. Če seštejemo števili obeh tipov prestavitev, dobimo izraz za stopnjo stanja r v trditvi. 22 POGLAVJE 2. KOMBINATORIKA HANOJSKIH STOLPOV Število vrhnjih ploščic, ki jih lahko prestavimo na zasedeni položaj i, je enako h{si, s). Če je Si = 0, to pomeni, da je položaj i nezaseden in po definiciji funkcije h velja h(0, s) = 0. Torej lahko število prestavitev drugega tipa, pri katerem prestavimo vrhnjo ploščico na zaseden položaj, izrazimo tudi z vsoto EiM«*,«) in velja p—i V h(si, s) = -(h(n + 1, s) - l)h(n +l,s). i=0 V nadaljevanju bomo podrobneje analizirali izraz za stopnjo stanja iz trditve 2.4.1. Ker ga bomo pogosto potrebovali, definirajmo funkcije dp, tako da bomo izraz iz trditve 2.4.1 lahko zapisali kot dp(h(n + 1, s)). Definicija 2.4.2. dp(k) = -\k2 + (p - \)k . V dp(k) s p označujemo število vseh položajev in s k število zasedenih položajev. Vidimo, da so funkcije dp(k) polinomi druge stopnje. Na sliki 2.6 so narisani grafi funkcij dp{k) za vrednosti p G {1, 2, 3, 4,5, 6} in vsa realna števila k, ki zadoščajo 0 < k < p. Za našo interpretacijo ima dp(k) pomen le nad vrednostmi k G {1, 2,..., p-l,p} in za vrednosti {1, 2,... ,p- 1} je strogo naraščajoča. Ker je vodilni člen polinoma negativen, ima funkcija maksimum in sicer pri tisti vrednosti k, kjer je odvod dp{k) enak 0. Ker je (dp(k))' = -k + p - |, je fcmax = p - \. Vrednost p-\ za število zasedenih položajev ni smiselno. Ker je graf kvadratnega polinoma simetričen okoli vertikalne osi y = fcmax, in ker je maksimum pri vrednosti p - \, velja dp{p - 1) = dp(p). Maksimalno število dovoljenih prestavitev je torej enako pri p in p - 1 zasedenih položajih in sicer dp(p-l) = dp(p) = \p(p - 1) = g). Do te ugotovitve bi seveda lahko prišli tudi z drugačnim premislekom. Na nezaseden položaj lahko prestavimo katerokoli vrhnjo ploščico, zato je nezaseden položaj za prestavljanje vrhnjih ploščic enakovreden največji ploščici, če pa je nezaseden en sam položaj, je to s stališča števila možnih prestavitev vrhnjih ploščic enako, kot če so zasedeni vsi položaji. Izraz g) za maksimalno stopnjo stanja lahko interpretiramo takole. Ob prestavitvi ploščice poimenujmo položaj od koder ploščico vzamemo izvorni položaj in položaj kamor jo prestavimo ciljni položaj. V primeru, ko je p ali p- 1 položajev zasedenih, je z vsako izbiro para položajev, prestavitev ploščice natanko določena. Položaj, kjer je vrhnja ploščica manjša, ali je drugi položaj nezaseden, je izvorni. Položaj, kjer je vrhnja ploščica večja, ali je nezaseden, je ciljni. Število izbir dveh položajev izmed p je g). 2.4. STOPNJA STANJ 23 d(k) "p ^ 15 14 13 12 11 10 9 8 7 5 4 3 2 1 p=6 2 3 4 > k Slika 2.6: Grafi funkcije dp(k) Za funkcijo dp{k) velja naslednja lastnost dp(k) - dp(k - 1) k2 + (P- l-)k- -l- -)(k-l) 2 --k 2 + pk - -k + -k 2 - k + -222 2 p — k. 2 pk + p + -k----- 22 Pri povečanju števila zasedenih položajev za en položaj, iz k - 1 na k, se stopnja stanja poveča za število nezasedenih položajev p - k. Funkcijo dp(k) lahko tako za diskretne vrednosti p in k zapišemo kot vsoto p, k e N, k < p : dp(k) = ^ (p - «)• (2.3) i=1 6 0 0 6 1 5 _ _ _ 24 POGLAVJE 2. KOMBINATORIKA HANOJSKIH STOLPOV Če k predstavlja število zasedenih položajev in indeks i v zgornji vsoti interpretiramo kot i-to vrhnjo ploščico po naraščajoči velikosti, potem izraz (p - i) predstavlja število možnih prestavitev i-te vrhnje ploščice. Vsoto (2.3) lahko zapisemo tudi kot k k V(p -i) = pk-sTi = Pk- -k(k +1). i=\ i=\ Vseh urejenih parov (ploščica za prestavitev, ciljni položaj) je pk. Od teh pk urejenih parov moramo odšteti število tistih, ki ne ustrezajo pravilom prestavljanja. To so, prestavitev največje na katerokoli od k zasedenih položajev, prestavitev druge največje na k - 1 zasedenih položajev, ..., prestavitev najmanjše na isti položaj. Za funkcijo ?p(k) velja tudi naslednja lastnost dp(k) - dp-!(k) 2 1 2k + (p - 2)k k2 + pk 112 k+ k 22 k2 + (p pk+ k 2 2 k. Pri povečanju števila vseh položajev za ena, se ob k zasedenih položajih stopnja stanja poveča za k, vsako izmed k vrhnjih ploščic lahko prestavimo na novi položaj. Pri k zasedenih položajih imamo 12k(k + 1) možnih prestavitev drugega tipa. Z vsakim dodatnim položajem se število prestavitev prvega tipa poveča za k, torej lahko zapišemo p-k djk) = -k(k+i) + y^k. Razdelek zaključimo z ugotovitvijo, da zaradi trditve 2.4.1 za izračun števila dovoljenih prestavitev v določenem stanju zadošča informacija o številu zasedenih položajev. _ _ _ Poglavje 3 Grafi Hanojskih stolpov V tem poglavju bomo definirali graf stanj posplošenih Hanojskih stolpov. V prvem razdelku bomo opisali označevanje točk s števili z osnovo p. V drugem razdelku bomo razmišljali o strukturi grafa, ter prikazali njegovo rekurzivno konstrukcijo. V tretjem razdelku bomo vpeljali dva tipa induciranih podgrafov. Prvi tip podgrafov bomo dobili z omejitvijo razmestitve ploščic na podmnožico položajev, drugi tip pa s fiksiranjem razmestitve določenega števila največjih ploščic. Glavni rezultat tega poglavja bomo predstavili v četrtem razdelku, v katerem bomo prešteli vse povezave grafa. Prešteli jih bomo na dva načina, prvič s preštevanjem točk z enako stopnjo, drugič z rekurzivnim nastavkom, ki ustreza strukturi grafa. Iz izraza za število povezav bomo dobili nekaj zanimivih številskih zaporedij. V petem razdelku bomo prešteli prestavitve posamezne ploščice. V zadnjem, šestem razdelku, bomo iz prej dobljenih rezultatov izpeljali minimalno, maksimalno in povprečno stopnjo grafa. Definirajmo osnovne pojme teorije grafov, ki jih bomo potrebovali. Za vir bomo uporabili Diestel [7]. Vsi grafi, obravnavani v tem delu, so neusmerjeni, končni in enostavni, torej brez zank in večkratnih povezav. Množico točk grafa G bomo označevali z V {G) ali z V, njegovo množico povezav pa z E{G) ali z E. E{G) je množica neurejenih parov uv = {u,v}, pri čemer sta uinv različni točki iz V (G). E{u) je množica vseh povezav z enim od krajišč v točki u. Parameter, ki označuje graf, bomo pri označevanju množice točk V in povezav E izpustili povsod, kjer bo nedvoumno, o katerem grafu govorimo. Če je uv povezava, pravimo, da sta točki u in v sosednji v grafu G. Množico vseh točk grafa G, ki so sosednje s točko u G V (G), označimo z NG{u), pri čemer velja NG(u) = {v G V (G) | uv G E(G)}, in imenujemo soseščina točke u. Če v soseščino vključimo tudi točko u, dobimo zaprto soseščino, ki jo označimo z NG[u]. Število sosedov točke u (moč soseščine) imenujemo stopnja točke u in jo zapišemo kot dG(x), torej dG(x) = \NG(x)\. Če bo jasno, o katerem grafu govorimo, potem bomo stopnjo točke zapisali krajše z d(x). Indeks, ki označuje graf, bomo izpustili 25 26 POGLAVJE 3. GRAFI HANOJSKIH STOLPOV povsod, kjer bo nedvoumno o katerem grafu govorimo. Število S(G)=imn{d(v)\veV} (3.1) je minimalna stopnja grafa G, število A(G) = mzx{d(v)\v E V} (3.2) je maksimalna stopnja grafa G in število <*(«) = M L*) = lW (3.3) i i veV i i je povprečna stopnja grafa G. Velja 5(G) < d{G) < A(G). Naj bo dan graf G in njegovi točki x in y. Zaporedje povezav, ki nas privede iz točke x v točko y, imenujemo sprehod med točkama x in y. Sprehod, na katerem so vse točke različne, imenujemo pot. Dolžina poti je število povezav na poti. Dolžino najkrajše poti v grafu G med točkama x in y imenujemo razdalja med točkama in jo označimo z dG(x,y), oziroma z d(x,y). Graf imenujemo povezan, če je s potjo povezan vsak par njegovih točk. V nasprotnem primeru je graf nepovezan. Če so vse točke grafa G paroma sosednje, potem G imenujemo polni graf. Polni graf na n točkah označimo s Kn. Število povezav v polnem grafu je enako številu parov točk, kar pa je ™ = \n{n - 1). Grafa G = (V, E) in G' = (V',E') imenujemo izomorfna in pišemo G ^ G', če obstaja taka bijektivna preslikava / : V -> F', da velja f(x)f(y) E E{G') <& xy E E(G) za vsak par točk x,y E V. Preslikavo / imenujemo izomorfizem. Če velja G = G', f imenujemo avtomorfizem. Graf H je podgraf v G, če velja V(#) C V {G) in L(#) C L(G). Graf H je inducirani podgraf v G, če je V(#) C V (G) in je F maksimalni podgraf na množici V {H), glede na povezave grafa G. Z drugimi besedami, za vsak par x,y E V {H) velja xy E E{H) ^^ xy E E(G). Inducirani podgraf grafa G dobimo tako, da iz množice točk grafa G izberemo neko podmnožico in obdržimo vse tiste povezave, ki imajo obe krajišči v tej pod-množici točk. Pravimo, da je podgraf H induciran s to podmnožico točk iz V (G). Če je V {H) = V (G), za podgraf H pravimo, da je vpeti podgraf v G. Navedimo še tako imenovano prvo lemo teorije grafov (imenovana tudi “lema o rokovanju”), ki smo jo že uporabili v (3.3) J2 d(x) = 2\E(G)\. (3.4) xev{G) 3.0. ZAPIS OZNAK TOČK 27 Na levi strani enakosti seštejemo vse stopnje točk grafa G in na tak način dobimo dvakratno število povezav v grafu, saj v vsoti vsako povezavo štejemo dvakrat. Definicija 3.1. Točke grafa HL = (V,E) naj bodo vse možne razporeditve ploščic posplošenih Hanojskih stolpov s p položaji in n ploščicami. Dve točki sta sosednji, če lahko preidemo iz enega stanja v drugega z dovoljeno prestavitvijo ploščice. Graf H™ imenujemo graf stanj posplošenih Hanojskih stolpov. 3.1 Zapis oznak točk z osnovo p Iz enoličnosti kvocienta in ostanka med dvema celima številoma [1, izrek 1.5] sledi, da lahko vsako celo število x enolično predstavimo v poljubnem številskem sestavu t takole x=(rnrn-1...r1r0)t, pri čemer velja x = rntn + rwif1"1 + • • • + nt + r0. Število x smo predstavili z zaporedjem ostankov dobljenimi po naslednjem postopku x = tq0 + r0 1 in p > 3 velja En fc=l i=0 _ 38 POGLAVJE 3. GRAFI HANOJSKIH STOLPOV Dokaz. Prva lema teorije grafov (3.4) pravi, da za graf G = (V, E) velja V prejšnjem razdelku, v trditvi 2.4.1, smo pokazali, kako lahko izračunamo stopnjo točke grafa HL. Videli smo, da je stopnja točke odvisna le od števila zasedenih položajev. Če s k označimo število zasedenih položajev, potem je stopnja točke enaka k(p - \) - \k2, kar smo označili s funkcijo dp(k). Za izračun števila vseh povezav je dovolj, da poiščemo še izraz za število vseh različnih stanj z natanko k zasedenimi položaji, to je število točk z enako stopnjo. Izmed vseh p položajev lahko k zasedenih izberemo na g) različnih načinov. Po izbranih k položajih moramo porazdeliti vseh n ploščic tako, da vsakemu zasedenemu položaju dodelimo vsaj eno ploščico. Število takih porazdelitev n ploščic na k različnih položajev je enako številu surjektivnih funkcij iz množice n ploščic na množico k položajev, za kar s pomočjo principa vključitve in izključitve dobimo naslednji izraz y(_1)*f k )(k-i)n. (3.6) ^ k- i Za število stanj s k zasedenimi položaji uporabimo pravilo produkta in dobimo Vsoto v izreku moramo deliti na pol, ker se pri seštevanju stopenj točk vsaka povezava šteje dvakrat. D Posledica 3.4.2. Za vsak n > 1 in p > 3 velja P \E'«\ = -y^d(k){n\p k . i pi 2^ p k Dokaz. Če število vseh surjektivnih funkcij (3.6) delimo s k!, dobimo Stirlingovo število druge vrste, ki v našem primeru pove, koliko je vseh takih razmestitev n različnih ploščic na k položajev, pri katerih vsakemu položaju dodelimo vsaj eno ploščico in ne razlikujemo med različnimi razvrstitvami položajev. Tako dobimo 3.4. ŠTEVILO POVEZAV 39 Število vseh surjektivnih funkcij (3.6) lahko tako zapišemo tudi z izrazom k\ , Za število točk z enako stopnjo iz izreka 3.4.1 velja naslednja enakost ^)D-i)<(Jfc*i)(fc-°B=(rrni (n ti(-~i)tk k -i(-k~z) n =dfc!{fc}={fc}^ D Faktor jA v posledici 3.4.2 interpretiramo kot število injektivnih preslikav iz množice k vrhnjih ploščic v množico p položajev. Videli smo, da je število stanj, kjer je natanko k položajev zasedenih, enako {L} jA Vemo tudi, da je število vseh stanj enako pn. Tako smo mimogrede dobili naslednjo znano identiteto [38, izrek 13.5]. Posledica 3.4.3. p n k=\ k=\ Izbor zgornje meje v vsotah ne predstavlja nobene razlike, saj velja nk = 0, če je n < k, in pk = 0, če je p < k. Izrek 3.4.4. Za vsak n ? 1 in p ? 3 velja \K\ = -v (pn- (p- 2D i p i 2 2 ; ; Dokaz. Razdelimo množico vseh stanj posplošenih Hanojskih stolpov na p dis-junktnih podmnožic. V vsaki od njih je največja ploščica fiksirana na določenem položaju. Točke, ki ustrezajo stanjem v taki podmnožici, inducirajo podgraf grafa Hpn izomorfen Hpn -1. V grafu Hpn imamo p takih podgrafov, ki inducirajo particijo množice vseh točk Vpn na p delov z enakim številom elementov. Dve točki iz dveh različnih takih podgrafov sta sosednji natanko takrat, ko se razlikujeta le v položaju največje ploščice. Da je možna prestavitev največje ploščice, morajo vse ploščice, razen največje, ležati na preostalih p - 2 položajih, to je tistih, ki niso vpleteni v prestavitev največje. Stanja, ko so vse ploščice, razen največje, na izbranih p-2 položajih, inducirajo podgraf grafa Hpn -1 izomor-fen Hpn --2 1. Med dvema podgrafoma izomorfnima Hpn -1 je torej |Vp n--2 1| = (p 40 POGLAVJE 3. GRAFI HANOJSKIH STOLPOV 2)n-1 povezav, ki predstavljajo prestavitev največje ploščice. Izraz za število vseh povezav grafa Hpn lahko rekurzivno zapišemo takole \K p\K n—l + (p\ w (p - 2)n-1 (3.7) Prvi del vsote predstavlja povezave v p disjunktnih podgrafih izomorfnih H™~1. Drugi del predstavlja vse povezave, ki pomenijo prestavitev največje ploščice. Število vseh parov podgrafov izomorfnih H™~1 je g), oziroma toliko je izbir dveh izmed p položajev med katerima prestavimo največjo ploščico, (p - 2)n~l pa je število povezav med vsakim parom podgrafov izomorfnih H™~1. Graf Hlp je izomorfen polnemu grafu Kp, zato velja l pi| (p\ (3.8) Zapišimo n - 1 enačb rekurzivnega izraza (3.7) I Wn\ I J?™_ 11 \% I I TH T) Vi FI ^i = P\E n—l I P I -21 P I (p (P) 2)n~1 2)n~2 / ' P I P3| I P2| p|L2| + g)(p p\Ep\ + ©O5 2)2 2) / • vn~3 I ¦ vn~2 Po množenju enačb s potencami p dobimo \e; p\k n—l I P I r)\En~l\ + (^(o — 2)n~1 p2\E;-2\+pi)(P-2)n-2 ra-3| 77131 F J-^p I jr/i-21^21 -P I V I pra"2|L2|+pra-3g)(p-2)2 pra-1|JBp1|+pra-2g)(p-2). Če seštejemo zgornje enačbe, se okrajšajo vsi členi pn-k|Epk| za k in upoštevamo še začetno vrednost (3.8), dobimo 2, 3,...,ra-l, I 77^1 \^p i (p _ 2)™"1 +p(p - 2T~2 + ¦¦¦ +pn~3(p - 2)2+pn-2(p - 2) +pn~l J2pl(p-2Yn-^-\ (3.9) n—l i=0 _ _ _ _ _ _ _ _ 3.4. ŠTEVILO POVEZAV 41 Ker velja ra—1 ra—1 ra—1 f/j _ h) \~^ nihn~i~l — V^ ni+lhn~i~l — V^ ni b n~i i=0 i=0 i=0 ra ra—1 V^ „ivn-i / CL 0 i=\ i=0 „n in ft — 0 in, če v zgornjo enakost namesto a vstavimo p, namesto b pa p - 2, lahko izraz (3.9) zapišemo takole 1 P bra - (p - 2)ral 2 2 kar smo tudi morali dokazati. D Formulo za število povezav v izreku 3.4.4 definirajmo kot zaporedje določeno s parametrom p takole. Definicija 3.4.5. Za n > 1 in p > 3 naj bo xv(n) = -(P\ \p n -(v-2) n ] . Celoštevilsko zaporedje x3(n) = (3ra+1-3)/2 najdemo v Sloanovi bazi celoštevil-skih zaporedij [70] pod identifikacijsko številko A029858. Zapisano je z eksplicitno formulo ara=-(3ra-3), in velja an = x3(n-l). Navedimo prvih deset členov zaporedja an: n 12345 6 7 8 9 10... an 0 3 12 39 120 363 1092 3279 9840 29523 ... Vrednost an za n ? 2 je rešitev naslednje naloge [12, 53]: Imamo kovance enake teže in med njimi enega, ki je na pogled enak drugim, vendar pa je po teži različen od njih (je lažji ali težji). Imamo tudi tehtnico, na kateri lahko z enim tehtanjem primerjamo teži dveh skupin kovancev. Katero je maksimalno število kovancev, da lahko z n tehtanji odkrijemo ponarejenega? 42 POGLAVJE 3. GRAFI HANOJSKIH STOLPOV Formulo za število povezav definirajmo kot zaporedje določeno s parametrom n takole. Definicija 3.4.6. Za n > 1 in p > 3 naj bo Vnip) = ~ (P^ \pn -(p- 2) n ] . yn\F 2 2 IF Celoštevilsko zaporedje yi(p) najdemo v Sloanovi bazi celoštevilskih zaporedij pod identifikacijsko številko A000217. Zapisano je z eksplicitno formulo < = Q , in velja a'n = y1(n). Števila a'n so znana pod imenom trikotniška števila. Celoštevilsko zaporedje y2(p) najdemo v Sloanovi bazi celoštevilskih zaporedij pod identifikacijsko številko A011379. Zapisano je z eksplicitno formulo a"n = n2 + n3 , in velja a'^ = y2(n + l) za n > 2 . Za števila a'^ velja, da so enaka zmnožku n-tega trikotniškega števila in n-tega sodega števila a" = -n(n - 1) • 2n. n 2 3.5 Število prestavitev posamezne ploščice Trditev 3.5.1. Število povezav v grafu H™, ki ustrezajo prestavitvi ploščice n - % zaOlinp>% velja 8(HL) =p-l, Dokaz. Izraza za minimalno stopnjo S(H^) in maksimalno stopnjo A(HL) sledita neposredno iz izraza trditve 2.4.1, ki smo ga uporabili tudi pri definiciji 2.4.2 funkcij 44 POGLAVJE 3. GRAFI HANOJSKIH STOLPOV dp(k), če za k vstavimo najmanjše ali največje možno število zasedenih položajev, 1 ali p. Enak rezultat za A{HL) dobimo tudi pri p - 1 zasedenih položajih, kot smo videli pri analizi funkcije dp{k) v razdelku 2.4. D Trditev 3.6.2. Za vsak n>linp>% velja d{H ) = 1 — ------- . Dokaz. Izračun povprečne stopnje grafa bomo naredili s pomočjo formule (3.3) 2\Ep\ fj{ hI ] = ------------ V izreku 3.4.4 smo pokazali, da velja 1 (p IKI = -P (pn-(p-2)n)) , i P\ 22 vemo pa tudi, da je število vseh točk \V™\ = pn, torej lahko zapišemo (p\ 22222222222222222222222222222222222222222222222 V pn 22© (P" ~ (P ~ 2)ra) d[H ) = ----------------- P P — * 1 -------- 2 P Če imamo eno samo ploščico, je pri fiksnem številu položajev povprečna stopnja enaka minimalni stopnji di^Hp) = 8(Hp) = p — 1, če pa gre število ploščic proti neskončno, se pri fiksnem številu položajev vrednost povprečne stopnje asimptotično približuje maksimalni stopnji lim d{H?) = A{H?) = (P) . n—>oo 2 Graf stanj posplošenih Hanojskih stolpov z neskončno ploščicami statistično ustreza regularnemu grafu s stopnjo (L). _ Poglavje 4 Enakost nekaj domnevno optimalnih rešitev V tem poglavju bomo dokazali, da je pet različnih pristopov k posplošenemu problemu Hanojskih stolpov med seboj enakih glede na število premikov ploščic. Med njimi je tudi klasični pristop Frama in Stewarta iz leta 1941 [11, 72]. Oba pristopa sta bila objavljena kot rešitev problema 3918 v reviji American Mathematical Monthly [71]. Že v isti številki je urednik problemov O. Dunkel izpostavil [9], da morata biti oba pristopa označena le kot domnevno optimalna, saj sta predstavljeni le dve možni strategiji prestavljanja ploščic izmed mnogih drugih, njuna optimalnost pa ni dokazana. Dokazati bi bilo potrebno, da so vse druge strategije slabše ali le toliko dobre, kot ti dve. Večina raziskovalcev verjame, da sta oba pristopa optimalna, vendar pa je zanimivo, da mnogi ne čutijo potrebe po dokazovanju tega. Oba pristopa sta v literaturi kasneje mnogokrat omenjena. Stockmeyer v obsežni bibliografiji [77] navaja kar 13 referenc, ki le ponovno odkrivajo prispevka Frama in Stewarta. Pristopa sta predstavljena v različnih oblikah in celo označena kot “v bistvu enaka” [76], vendar do sedaj tudi dokaza te trditve še nismo zasledili. V prvem razdelku tega poglavja bomo predstavili pet rekurzivnih definicij, od katerih vsaka odraža neko strategijo reševanja posplošenih Hanojskih stolpov. V treh podrazdelkih nekoliko podrobneje opišemo Framov in Stewartov pristop ter pristop z vsemi particijami. V drugem razdelku dokažemo enakost teh treh pristopov glede na število potrebnih prestavitev ploščic. V četrtem razdelku vpeljemo eksplicitno formulo za število potrebnih prestavitev ploščic, ki jo je predstavil že Frame, in petem razdelku dokažemo, da eksplicitna formula res izraža število prestavitev po Stewartovem pristopu. V zadnjem, šestem razdelku povzamemo rezultate in dokažemo enakost vseh. 45 46 POGLAVJE 4. ENAKOST REŠITEV 4.1 Rekurzivne definicije V tem razdelku bomo vpeljali naslednje rekurzivne funkcije: F(n,p) — odraža Framov algoritem; F'{n,p) — enako kot F{n,p) , le monotonost ni zahtevana; S{n,p) — odraža Stewartov algoritem; A'{n,p) — odraža algoritem z vsemi particijami; A{n,p) — enako kot A'{n,p) , toda monotonost je zahtevana. Naj bo M(n,p) minimalno število prestavitev, ki jih moramo opraviti, da rešimo problem posplošenih Hanojskih stolpov z n ploščicami in p položaji, to je z minimalnim številom prestavitev ploščic preiti iz enega popolnega stanja v drugega. Le za p > 4 položaje in n > p ploščic je problem težak. Dokazano je, da velja M(n, 3) = T - 1, in M(n,p) = 2n-lzan 2. Definicija 4.1.1. Za p = 2, 3 ali n < p velja F(n,p) = F'{n,p) = A{n,p) = A'{n,p) = S{n,p) = M(n,p). Vseh pet definicij rekurzivnih izračunov domnevno optimalnih rešitev bomo podali le za netrivialne primere, za n,p G N,p > 4 in n > p. Po potrebi bomo začetne vrednosti izbrali iz trivialnega območja. Med dokazovanjem rezultatov o teh funkcijah in eksplicitnih formulah bo potrebna pazljivost glede trivialnega območja. 4.1.1 Framov algoritem Naslednja definicija odraža Framov algoritem [11] za problem posplošenih Hanojskih stolpov, vendar pa se razlikuje od originalne definicije, ker ne zahteva, da so particije n monotone. Definicija 4.1.2. Za p > 4 in n > p je F'(n,p) minimum od {2F'(m,p) + 2F'(n2,p- 1) + • • • + 2F'(np_2, 3) + 1 | m + • • • + np_2 + 1 = n}, pri čemer meN. 4.1. REKURZIVNE DEFINICIJE 47 Enico v zgornji vsoti lahko interpretiramo kot F'(l, 2). Originalna Framova definicija je naslednja. Definicija 4.1.3. Za p > 4 in n > p je F(n,p) minimum od {2F(nl}p) + 2F(n2,p- 1)+ • • • + 2F(np-2, 3) + 1 | ni-\--------h np-2 + 1 = n, ni > n2 > ¦ ¦ ¦ > np-2} pri čemer meN. Enico v zgornji vsoti lahko interpretiramo kot F'(1,2). Na sliki 4.1 predstavljamo posamezne faze strategije prestavljanja ploščic, katero odražata rekurzivni formuli F(n,p) ali F'(n,p). Na začetku imamo vseh n ploščic na izvornem položaju 0. Z upoštevanjem pravil prestavljanja ploščic jih bomo prestavili na ciljni položaj p - 1. Zgornjih n - 1 ploščic razdelimo na p - 2 skupin ploščic zaporednih velikosti nl} n2,..., np.2. Zgornjih m najmanjših ploščic prestavimo z izvornega položaja 0 na položaj 1 z uporabo vseh p položajev. Naslednjih n2 najmanjših ploščic prestavimo z izvornega položaja 0 na položaj 2 z uporabo p - 1 položajev. Tako nadaljujemo s prestavljanjem skupin ploščic z izvornega položaja na pomožne položaje. Vsako naslednjo skupino ploščic prestavimo z uporabo enega položaja manj. Zadnjo skupino np.2 ploščic prestavimo iz izvornega položaja na položaj p- 2 z uporabo preostalih treh dopustnih položajev. Največjo (ra-to) ploščico nato prestavimo z izvornega položaja 0 na ciljni položaj p - 1. Po prestavitvi največje ploščice prestavimo skupine ploščic s p- 2 pomožnih položajev na ciljni položaj p-Iv obratnem vrstnem redu, od skupine np.2 do skupine m ploščic. 4.1.2 Stewartov algoritem Sedaj bomo predstavili funkcijo S(n,p), ki odraža Stewartov algoritem [71] za problem posplošenih Hanojskih stolpov. Definicija 4.1.4. Za p > 4 in n > p je S{n,p) minimum od {2S{nup) + S(n2,p - 1) | nx + n2 = n}, pri čemer nh n2 G N. Na sliki 4.2 predstavljamo posamezne faze strategije prestavljanja ploščic, katero odraža rekurzivna formula S(n,p). Na začetku imamo vseh n ploščic na izvornem položaju 0. Z upoštevanjem pravil prestavljanja ploščic jih bomo prestavili na ciljni položaj p-l. Vseh n ploščic razdelimo na dve skupini. Prvo skupino sestavlja 48 POGLAVJE 4. ENAKOST REŠITEV n1+n2+1 . . . n1+n2+...+np 3-+1 . . . n1+n2+...+np 2-n «,+1 n1+n2 n,+1 n1+n2 n,+1 n1+n2 W W p-2 nj+n2+...+np_3+l n1+n2+-+n 2 n+n+...+n +i "p-3 n]+n2+'...+n 2 p-2 p-1 p-1 p-1 p-1 n1 «+1 rtj+n n+n+...+n +i n,+r,2+...+n 2 n p-2 p-1 1 2 n, 1 2 1 nl 0 2 n, n 0 1 2 1 1 0 2 1 0 1 2 Slika 4.1: Prestavljanje ploščic po Framovem algoritmu 4.1. REKURZIVNE DEFINICIJE 49 n1-1 n1 r1 +1 n-l n n-l n «1-1 p-2 p-1 p-2 p-1 n-l n p-2 />-; 1 «1-1 /!-/ n p-2 />-; Slika 4.2: Prestavljanje ploščic po Stewartovem algoritmu n1 najmanjših ploščic in drugo skupino sestavlja preostalih n-n1 ploščic. Zgornjih n1 ploščic prestavimo z izvornega položaja 0 na pomožni položaj 1 z uporabo vseh p položajev. Preostalih n - n1 ploščic prestavimo z izvornega položaja na ciljni položaj p - 1 z uporabo p - 1 pomožnih položajev (vseh, razen položaja 1). V zadnji fazi prestavimo n1 ploščic s položaja 1 na ciljni položaj p - 1 z vseh p položajev. uporabo Na preprostih primerih lahko pokažemo, da S(n, k) nima monotone inačice, ker le-ta da drugačno funkcijo. Na primer, minimum 2S(n1, 5) + S(n2, 4) preko vseh parov n1,n2 z n1 +n2 = 9 je 27, medtem ko je minimum preko parov, ki zadoščajo pogoju n1 ? n2, enak 31. 4.1.3 Vse particije u 2 o 2 0 2 0 2 Definirajmo sedaj še rekurzivno funkcijo, ki odraža algoritem, pri katerem upoštevamo vse particije. 50 POGLAVJE 4. ENAKOST REŠITEV Definicija 4.1.5. Za p > A in n > p je {2A'(n1,p) + 2A'(n2,p-l)+ {2A'(nl,p) + 2A'(n2,p-l)+ {2A'(nl,p) + A'(n2,p-l) \ pri čemer meN. Monotona inačica A'(n,p) je naslednja. Definicija 4.1.6. Zap>4inn>pje A(n,p) minimum od {2A(nl,p) + 2A(n2,p {2A(m,p) + 2A(n2,p {2A(n1}p) + A(n2,p pri čemer meN. 4.2 Dokaz Af = Najprej bomo navedli dve lemi o funkciji A'(n,p). Prva je več ali manj očitna, sledi iz dejstva, da velja A'(n,p) > M(n,p) >2n-l. Druga obravnava le trivialne primere. Lema 4.2.1. Za vsak n > 1 in p > 3 velja A'(n,p) >2n-l. Dokaz. Zan

3 velja A'(n, 3) = 2n-l>2n-l. In končno, za p > 4 in n > p je A'(n,p) = 2A\m,p) + 2A'(n2,p - 1) + • • • + 2A\np.l}i + 1) + A\np.l+l,i), pri čemer m + n2 + • • • + np_m = n in 2 < i < p - 2. Z indukcijo imamo A'{n,p) > 2[(2m-l) + --- + (2np_i-l)] + 2np_i+i-l = 2(m + • • • + np_t + np_m) + 2(m + • • • + np_,) - 2(p - i) - 1 = 2n + 2(ni + • • • + np_i) - 2{p - i) - 1 > 2n - 1, kar smo morali dokazati. D A'(n,p) minimum od ¦¦¦ + 2A'(np_2,3) + l | ni-\--------h np_2 + 1 = n} U ••• + 2A'(np_3,4) + A,(np_2,3) ft-i + • • • + np_2 = n} U • • • U ni + n2 = n}, 1)+ ••• + 2A(np_2,3) + l | ni-\--------h np_2 + l = n, rii>n2> ¦¦¦} U 1)+ ••• + 2A(np_3,4) + A(np_2,3) | ni + • • • + ^p-2 = ^, n\ > n2 > • • • } U • • • U 1) | ni + n2 = n, ni > n2}, F' = S 4.2. DOKAZ A'= F'= S 51 Lema 4.2.2. Za vsak n > 1 in p > 3 ter i,nu ..., np_i+l, kjer je 2 < i < p - 1 m n = n1 + n2^--------h np_i+1, velja A'(n,p) < 2A'(ni,p) + 2A'(n2,p- 1) + • • • + 2A'(np_t, i + l) + A'(np_t+l,i). Dokaz. Če je p > 4 in n > p, sledi lema neposredno iz definicije. Iz p = 3 sledi i = 2, in dokazati moramo le A'(n,3) < 2A'(m, 3) +A'(n2, 2), kar pa je neizrojeno le za n2 = 1. Torej moramo dokazati A'(n, 3) < 2A'(n -1,3) + A'(l,2), kar je trivialno (glede na dejstvo 2n < 2(2ra"1 - 1) + 1). Za zadnji primer, ko je n < p, p > 4, bomo lemo dokazali z indukcijo po n. Če je n = 2, potem imamo 2 = n = nx + n2 + ¦ ¦ ¦ + np_i+1 >p-i + l. Torej je p-i < lin, ker je po drugi strani p- i > 1, sledi p-i= 1. Torej velja m = n2 = 1. Sedaj je dovolj, če pokažemo, da velja A'(2,p) < 2A'(l,p) + A'(l,p- 1), kar pa je res, saj je 3 < 2 • 1 + 1. Induktivni korak je sledeč 2A'(m,p) + (2A'(n2,p-l) + --- + 2A'(np_t,i + l) + A'(np_t+l,i)] > 2A\nup) + A'(n -nup-l)> A'(n,p) , s čimer je dokaz zaključen. D Trditev 4.2.3. Za vsak n > 1 m p > 3 velja A'(n,p) = S(n,p). Dokaz. Trditev bomo dokazali z indukcijo po n, in sicer le za netrivialno območje. Tako bomo v nadaljevanju dokazali, da trditev velja za vse n > 4 in tudi, da pri fiksnem n velja za vse p, 4 < p < n. Za n = 4 je dovolj, če preverimo za p = 4. Neposredni izračun pokaže, da imamo v tem primeru A'(4,4) = S(4,4) = 9. Predpostavimo sedaj, da indukcijska predpostavka velja za vse m, 4 < m < n. Naj bo p poljubno celo število, ki zadošča pogoju 4 < p < n. Iz indukcijske predpostavke sledi, da za vse m, n2 G N, za katere je m + n2 = n, velja 2S{nup) + S(n2,p- 1) = 2A'{nup) + A'(n2,p- 1). Torej je množica, za katero definiramo S(n,p) (kot njen minimum), podmnožica množice, za katero definiramo A'{n,p) (kot njen minimum). Sledi, daje A'{n,p) < S(n,p). Pokazati moramo še, da velja A'(n,p) > S(n,p). Če obstajata taka m in n2 z nx + n2 = n, da velja A'{n,p) = 2A'(n1}p) + A'(n2,p- 1), potem smo končali, saj 52 POGLAVJE 4. ENAKOST REŠITEV je v tem primeru A'(n,p) v množici, katere minimum je S(n,p). Predpostavimo zato, da velja A'(n,p) = 2A'(nup) + 2A'(n2,p - 1) + • • • + 2A\np.t,i + 1) + A\np.l+l,i), pri čemer m + n2 + • • • + np_m = n in 2 < i < p - 2. Za poseben primer i = 2 imamo np_m = np_i = 1 in A'(nn-i, 2) = 1. Sledi, n2 + n3 + -••+np_m = n-ni. Po lemi 4.2.2 imamo A'(n - m,p - 1) < 2A'(n2,p - 1) + • • • + 2A'(np_t, i + 1) + A'(np_m, i), in zato lahko z uporabo indukcijske predpostavke zaključimo A'{n,p) > 2A'{m,p) + A'(n - m,p - 1) = 25(m,p) + ^(n - nl}p - 1) > 5(n,p). D Trditev 4.2.4. Za vsak n>l,p>3 velja A'(n,p) = F'(n,p). Dokaz. Kot v dokazu izreka 4.2.3 bomo dokazovali z indukcijo po n. Za n = 4 imamo F'(4,4) = min{2F,(n1,4) + 2F,(n2,3) + l | m + ra2 + 1 = 4} = min{2A,(n1, 4) + 2A'(n2, 3) + 1 | m + n2 = 3} = min{2A,(l, 4) + 2A'(2, 3) + 1,2A'(2,4) + 2A'(1, 3) + 1} = min{2(l + 3) + 1, 2(3 + 1) + 1} = 9 = A'(A, 4). Predpostavimo sedaj, da velja F'(m,p) = A'(m,p) za vse m, 4 < m < n. Množica, za katero definiramo F'{n,p) (kot njen minimum), je podmnožica množice, za katero definiramo A'(n,p) (kot njen minimum), ker za vse m,... , np.2, za katere je ni H--------h np-2 + 1 = n, velja 2F\m,p) + ¦¦¦ + 2F'(np.2, 3) + 1 = 2A'(nhp) + ¦¦¦ + 2A'(np.2, 3) + 1. Torej velja F'{n,p) > A'{n,p). Da dokažemo še drugo neenakost, bomo uporabili naslednji argument dinamičnega programiranja. Po izreku 4.2.3 lahko napišemo A'(n,p) = 2A'(nhp) + A'(n2,p - 1), za m + n2 = n. S ponovno uporabo tega argumenta imamo A'(n2,p - 1) = 2A'(n2,p - 1) + A'(n3,p - 2), kjer je n2 + n3 = n2 in tako dobimo A'{n,p) = 2A'(n1}p) + 2A'(n2,p - 1) + A'(n3,p - 2). 4.3. EKSPLICITNE FORMULE 53 Kako dolgo lahko ta postopek izvajamo? Razlikujemo med dvema primeroma. Primer 1: A'{n,p) = 2A'{m,p) + ¦¦¦ + 2A'(np.t, % + 1) + A'(np.t+l,z) ,zi>2in rip-i+i = I. Postavimo r = max{fc | nk > 1} in omenimo, da velja r < p - i. Potem imamo A(n,p) = 2A(nl,p) + --- + 2A(nr,p-r + l) + 2A(l,p-r) + ¦¦¦ + 2A(l,i + l) + 2A(l,i) = 2A(nl}p) + ¦¦¦ + 2(2 A{rir, p - r - 1) + A{rir+1,p - r)) + 2A(l,p- r - 1) + • • • + 2,4(1,i) + A{l,i- 1) > 2A(m,p) + ¦¦¦ + 2A(n'r,p- r + 1) + 2A(n'r+1,p- r)) + 2A(l,p- r - 1) + • • • + 2,4(1,i) + A(l,i- 1) > A{n,p). V zgornjem izračunu je zamenjava spremenljivk v drugi enakosti možna zato, ker so vse vrednosti A'(l,p- r),..., A'(l, 1) kot tudi A'(l,p - r - 1),..., A'(l, i-1), enake 1 in je i - 1 > 2. Torej imamo protislovje, iz česar sledi, da ta primer ni možen. Primer 2: A'{n,p) = 2A'(nl}p) + ¦¦¦ + 2A'(np.t, % + 1) + A'(np.t+l,z) ,zi = 2in np-i+i = 1. Sedaj imamo A'(n,p) = 2A\ni,p) + --- + 2A\np.2,?y) + l = 2F'(n1,p) + --- + 2F'(np.2,3) + l > F'(n,p) in dokaz je končan. D S kombinacijo izrekov 4.2.3 in 4.2.4 dobimo naslednjo posledico. Posledica 4.2.5. Za vsak n>l,p>3 velja A'(n,p) = F'(n,p) = S(n,p) > M(n,p). 4.3 Eksplicitne formule Eksplicitne formule, o katerih bomo govorili v tem razdelku, so se pojavile že v [11], toda obravnavane so bile hevristično, in kar je še največja pomanjkljivost 54 POGLAVJE 4. ENAKOST REŠITEV Framovega pristopa, navedene so bile kot dejstva o M(n,p). Zato je še posebej pomembno, da jih obravnavamo neodvisno. Z upoštevanjem le njihovih lastnosti, kot tudi lastnosti funkcij A', F', S, bomo dokazali, da res predstavljajo iste funkcije. Definicija 4.3.1. Naj bo n > 2 in p > 3, potem definiramo X(n,p) takole s~l T (p-3 +s)! 1 + 2s n X(n,p) = Y, 2t(j" * + tf + Y t=o ^ >' (p-3)!t! (p-2)!(s-l)! kjer je s največje celo število, za katerega je zadnji člen na desni strani pozitiven, kar pomeni f, , (p-3 + fc)! 1 s = max k G Z n ------; > 0 . ' (p-2)!(fc-l)! X(l,p) definiramo kot X(l,p) = l. Z uporabo binomskih koeficientov lahko zan>2 zgornjo definicijo napišemo na sledeč način X(n,p) = Y2 t(p-3 + t)+ s\n-(p-3 + S)}, z-^/ p —3 p—2 kjer je s = max k G Zln - ( > 0 . p — 2 Ta definicija nam daje zadostno motivacijo, da uvedemo funkcije hp(x), p G N. Definicija 4.3.2. Za p>3 in x eR,x >0 naj bo hp(x)=(p-3 + X). p — 2 Iz predstavitev v obliki x(x + l)---(x+p- 4){x+p- 3) Kkx) - (p-2)! je očitno, da so za p > 3 te funkcije strogo naraščajoči polinomi na svojih definicijskih območjih. Ker so strogo naraščajoče, obstajajo inverzne funkcije gp = h~x , ki so prav tako strogo naraščajoče na svojih definicijskih območjih. 4.3. EKSPLICITNE FORMULE 55 Definicija 4.3.3. Za p > 3 in x > O naj bo Ux) = \9P{x)~\ , kjer je gp = h'1. Lema 4.3.4. Število s iz definicije 4.3.1 (za n>2) lahko pišemo kot s = fp(n) - 1. Dokaz. Očitno je s = mzx{keZ\n-hp(k) >0}. Ker je funkcija hp strogo naraščajoča, je število s tisto enolično število, ki zadošča pogojema hp{s) < n, hp(s + \)>n ali enakovredno sgp(n), kar pa je enako gP(n) 2) sedaj zapišemo z eno samo formulo takole / (n) — 2 X(n,p) = V ^(p-3 + t)+2M^\n-(P + fp{n)-4)}. p —3 p—2 Lema 4.3.5. Za vsak n>2,p>3 velja X(n,p) - X(n - l,p) = 2^ra)"1. Dokaz. Velja enakost X(2,p) - X(l,p) = 2^2)"1, ker je /p(2) = 2. Za n > 3 bomo razlikovali med dvema primeroma. Primer 1: fp(n-l) = fp(n). V tem primeru je X(n,p) - X(n - l,p) enako 2/PW-i L (P + fp(n)-4\] 2Mn)-i\„ , (P + fp(n)-4\] L p —2 L p—2 to pa je nadalje enako l,p>3 velja n k=\ 4.4 Dokaz X =S V tem razdelku bomo dokazali naslednji izrek. Izrek 4.4.1. Za vsak p ? 3, n ? 1 velja _ _ _ X(n, p) = S(n, p) . 4.4. DOKAZ X = S 57 Dokaz. Izrek bomo dokazali induktivno, skupaj z naslednjo enakostjo S{hp{k),p) = 2S(hp(k - l),p) + S{hp{k) - hp(k - l),p - 1), za p > 4, in k > 2. Ta dodatna trditev ne le, da tvori pomemben del našega induktivnega dokaza izreka, temveč jo skupaj s predstavitvijo S{n,p) v obliki 2S{m,p) + S(n2,p - 1), podani v dokazu, lahko uporabimo za računske namene. Omenimo, da velja hp(k) - hp(k - 1) = hp_x(k) — kar imamo tu, so prikriti binomski koeficienti. S trivialnim delom hitro opravimo. S{n, 3) = 2ra-l = l + 2 + --- + 2n~l = X(n, 3), saj je /3(fc) = k. Tudi za p > 4 in n < p imamo X{n,p) = 1 + (n - 1)2 = 2n - 1 = S{n,p). Poleg navedenega vidimo, da je 2S(hp(l),p) + %_1(2),p - 1) = 2 • 1 + 2(p -2) - 1 = 2p - 3 = 2(p - 1) - 1 = S(hp(2),p). Naj sedaj n zadošča neenakosti hp{k) + l 2. Naša induktivna predpostavka je, da velja S(m,p) = X(m,p) za vse m, 1 < m < n, in da je S(hp(k),p) = 2S(hp(k -l),p) + S(ViW,P - 1). Potem je fp(n) = k + l, fP(hp(k)) = k, in fp(L) > k + 2, za vse L > hp(k + 1). Če je nx > hp{k), potem velja /p(m) > k (pravzaprav je /p(m) = k + 1), in zato imamo 2S(nl}p) + S(n-nl}p-l) = 2X(nl}p) + X{n -nl}p-l) = 2(x(ni - l,p) + 2f^n^-1)+X(n - nup - 1) > 2S(m - l,p) + ^(n - m,p - 1) + 2k = S(n - l,p) + 2k = S(n - l,p) + 2f^~l = X(n,p). Če je nx < hp(k - 1), potem je n - nx > n - hp(k - 1) > hp(k) - hp(k - 1) = hp-tik), in zato velja f^n - m) > k + 1. Sledi 2S(nl}p) + S(n-nl}p-l) = 2X(nl}p) + X{n -rn,p- 1) = x(ni,p) + 2X(n - m - i,P - i) + 2/?-i(ra-rai)-1 > 5(n-l,p) + 2fc = X(n,p). V preostalem primeru hp(k - 1) < n < hp(k), ker je fp(m) = k, imamo 2S{n1,p) + S{n-n1,p-l) = 2X(n1}p) + X(n -nup-l) = 2(x(m - l,p) + 2W"l)-1)+I(n - m,p - 1) = 25(711 - l,p) + S{n - nup - 1) + 2k > S(n - l,p) + 2k = X(n,p) 58 POGLAVJE 4. ENAKOST REŠITEV Ker ti trije primeri pokrijejo vse možnosti, sledi S(n,p) > X(n,p). Tudi če nek m zadosti pogoju 2S{n1,p) + S(n - nup - 1) = X{n,p), pomeni, da je S(n,p) = X(n,p) = 2S(nup) + S(n - nup - 1). Predpostavimo S(n-l,p) = X(n-l,p) = 2S(mup) + S(n - 1 - mup - 1), kjer hp{k - 1) < mi, mi + 1 < hp(k). V tem primeru /„(mi + 1) = k in 2S(mi + l,p) + S(ra - (mi + l),p - 1) = 2(s{ml,p) + 2/*(m1+1)-1W(ra - (mi + l),p - 1) = 2S(ml}p) + S(n-l- ml}p - 1) + 2k = S(n - l,p) + 2k = X(n-l,p) + 2f^-l = X(n,p) in sledi S{n,p) = X{n,p) = 2s(mi + l,p) + S{n - 1 - mi,p - 1). Če uporabimo ta rezultat in začnemo z induktivno predpostavko S{hp{k),p) = X{hp{k),p) = 2S(hp(k - l),p) + S(hp(k) - hp(k - l),p - 1), dobimo S{hp{k) + l,p)=X{hp{k) + l,p) = 2S(hp(k - 1) + l,p) + S{hp{k) - hp(k - l),p - 1) S(hp(k) + 2,p)=X(hp(k) + 2,p) = 2S(hp(k - 1) + 2,p) + S{hp{k) - hp(k - l),p - 1) S{m,p) = X{m,p) = 2S{hp{k),p) + S{hp{k) - hp(k - l),p - 1), kjer je m = hp(k) + (hp(k) - hp(k - 1)). Očitno je m < hp(k + 1) (saj je to ekvivalentno hp(k) - hp(k - 1) < hp(k + 1) -hp{k), oziroma hp.x{k) < hp.x{k + 1)). Preostane nam še, da izpolnimo induktivni korak v preostalem primeru, ko n zadošča pogoju m < n < hp{k + 1). “Induktivni dokaz” sedaj pomeni, da induktivno dokažemo S{t,p) = X{t,p) = 2S(hp(k),p) + S {t - hp(k)) za vse t, ki zadoščajo pogoju m < t < hp(k + 1). Pri izbranem m je to res za t = m. Naj n zadošča pogoju m < n < hp(k + 1) in naj predpostavka velja za n - 1. V tem primeru je hp(k) -hp(k- 1) = m-hp(k) < n-hp(k) < hp(k + l)-hp(k). To pomeni hp_x(k) < n-hp(k) < Vi(fc + 1), in zato sledi f^n-h^k)) = k + l. 4.5. ENAKOST VSEH 59 Sedaj imamo 2S{hp{k),p) + S{n - hp{k),p - 1) = 2X{hp{k),p) + X(n - hp{k),p - 1) = 2X(hp(k),p) +X(n-l- hp(k),p- 1) + 2f^{n-h^{k))-1 = X(n-l,p) + 2k = X(n,p). Kot poseben primer (za n = hp(k + 1)) dobimo 2S{hp{k),p) + S{hp{k + l)-hp{k),p-l) = S(hp(k + l),p), torej smo končali tudi induktivni dokaz dodatne trditve, ki smo jo navedli na začetku dokaza. D V [18] Hinz uporabi podoben pristop za dokaz X(n,A) = S(n,4). 4.5 Enakost vseh V zadnjem razdelku poglavja bomo pokazali, da sta tako originalna Framova funkcija F, kot tudi naša funkcija A, enaki vsem ostalim. Lema 4.5.1. X{n,p) - X(n - l,p) < X{n,p - 1) - X{n - l,p - 1). Dokaz. To pomeni 2^ra)"1 < 2^-^~, kar je ekvivalentno fp(n) < fP-i(n). Za slednje je enostavno videti, da je resnično. D Posledica 4.5.2. X{m,p) + X{n,p- 1) > X{n,p) + X{m,p- l), če m < n. Dokaz. Trditev je ekvivalentna naslednji neenakosti X{n,p)-X{m,p) < X(n,p-l)-X(m,p-l), ki pa jo dobimo, ko seštejemo neenakosti X{n,p)-X{n-l,p) < X(n,p-l)-X(n-l,p-l), X(n-l,p)-X(n-2,p) < X(n - l,p - 1) - X(n - 2,p - 1), X(m + 2,p)-X(m+l,p) < X(m + 2,p - 1) - X(m + l,p - 1), X(m+l,p)-X(m,p) < X(m+l,p-l)-X(m,p-l), in le-te veljajo po lemi 4.5.1. D Trditev 4.5.3. Za vsak n>l,p>3 velja F'(n,p) = F(n,p). 60 POGLAVJE 4. ENAKOST REŠITEV n Dokaz. Za trivialno področje zgornje velja že po definiciji. Enakost bomo dokazali z indukcijo ponzap>4inn>p. Očitno je F'(n,p) < F(n,p), saj je na levi strani upoštevanih več particij. Naj bo F'(n,p) = 2F'(m,p) + - ¦ ¦ + 2F'(np.2, 3) + l, kjer je m + - ¦ -+np_2 + l in m < ni+i, za nek i. Potem z uporabo posledice 4.5.2 in induktivne predpostavke dobimo F'(n,p) = 2(F{m,p) + (x{ni,p) (x{m,p) 2(F(n1}p) + + + +F(ni-1,p-i+2) + F(ni,p - i + 1) + F(ni+1,p - i) + +X(ni-1,p-i+2) + X(ni,p - i + 1) + X(ni+1,p - i) + +X(ni-1,p-i+2) + X(ni+1,p - i) + X(ni,p - i + 1) + +F(ni-1,p-i+2) + +1 )+l > )+l > F(ni+1,p - i) + F(ni,p - i + 1) + ··· +1. Po končno mnogo ponovitvah tega postopka dobimo, da je F'(n,p) vsaj tako velik, kot ena izmed vsot za F{n,p), torej F'{n,p) > F{n,p). D Trditev 4.5.4. Za vsak n>l,p>3 velja A'(n,p) = A(n,p). Dokaz. Za trivialno področje trditev velja. V netrivialnem področju pa velja neenakost A'{n,p) < A{n,p), saj je množica particij na desni strani podmnožica particij na levi strani. Zaradi istega razloga imamo tudi A{n,p) < F{n,p), vemo pa že, daveljaA'(n,p) = F(n,p). D Tako smo zaključili z dokazovanjem naslednjega izreka. Izrek 4.5.5. Za vsak n>l,p>3 velja A{n,p) = A'{n,p) = F{n,p) = F'{n,p) = S{n,p) = X{n,p) > M{n,p). _ Enakost A'(n,p) = S(n,p) smo pokazali v izreku 4.2.3, enakost A'(n,p) F'(n,p) v izreku 4.2.4, enakost X(n,p) = S(n,p) v izreku 4.4.1, enakost F'(n,p) F{n,p) v izreku 4.5.3 in enakost A'{n,p) = A{n,p) v izreku 4.5.4. Poglavje 5 1-popolne kode v grafih Sierpińskega V prvem razdelku tega poglavja bomo iz teorije kodiranja vpeljali osnovne pojme, ki jih bomo potrebovali kasneje. Definirali bomo tudi popolne kode in omenili nekaj znanih rezultatov. V drugem razdelku bomo spoznali zgodovino nastanka grafov Sierpińskega, ter omenili nekaj rezultatov o obstoju oziroma neobstoju popolnih kod v grafih klasičnih Hanojskih stolpov, ki so motivirali raziskovanje popolnih kod v grafih Sierpińskega. V tretjem razdelku bomo vpeljali notacijo za nekatere podgrafe grafa Sierpińskega, s pomočjo katere bomo v četrtem razdelku predstavili našo posplošitev do sedaj znanih rezultatov, obstoj 1-popolnih kod v grafih Sier-pińskega. Predstavljeni pristop je bistveno drugačen od znanega pristopa za grafe H3n. V zadnjem razdelku si bomo ogledali učinkovit algoritem za dekodiranje, katerega implementacija je priložena v dodatku A. Prikazali bomo tudi nekaj slik konstrukcij 1-popolnih kod v grafih Sierpińskega. 5.1 Teorija kodiranja in popolne kode v grafih Navedli bomo nekaj osnovnih pojmov, definicij in izrekov, ki jih bomo kasneje potrebovali. Za vir bomo uporabili Klavžar [28] in Kratochvíl [36]. Omejili se bomo le na obravnavo kod v grafih. motnja pošiljatelj sporoeila > kodiranje prenos po kanalu > dekodiranje prejemnik sporoeila Slika 5.1: Prenašanje sporočil s kodiranjem in dekodiranjem 61 62 POGLAVJE 5. 1-POPOLNE KODE Po komunikacijskem kanalu, ki je lahko na primer žica, optični kabel, vesoljski prostor, želimo prenesti sporočilo. Pri prenašanju lahko pride do motenj, ki sporočilo pokvarijo, zato potrebujemo mehanizem, ki sprejemniku omogoči, da napake pri prenosu odkrije in jih celo popravi. Pred prenosom po kanalu sporočilo zakodiramo in ga po prenosu dekodiramo. Shematično je ta proces prikazan na sliki 5.1. Osnovni princip kod za odkrivanje in popravljanje napak je princip bližnjega soseda, ki pravi naslednje. Naj bo w beseda, ki jo prejmemo prek kanala, in naj bo u kodna beseda, za katero je d{w,u) < d{w,v) za poljubno kodno besedo v = u. Tedaj besedo w dekodiramo v kodno besedo u. Z drugimi besedami, preneseno besedo dekodiramo v najbližjo kodno besedo glede na Hammingovo razdaljo. Hammingova razdalja d(u,v) med besedama u in v je število mest v katerih se besedi razlikujeta. Princip bližnjega soseda deluje le tedaj, ko napak pri prenosu ni veliko. Naj bo t naravno število. V skladu s principom bližnjega soseda pravimo, da koda popravlja t napak, če za vsako besedo w velja, da obstaja kvečjemu ena kodna beseda u z lastnostjo dH{w,u) < t. Drugače povedano, če je pri prenosu besede prišlo do kvečjemu t napak, bomo s principom bližnjega soseda prejeto besedo pravilno dekodirali. Koda v grafu G = (V, E) je podmnožica C C V. Element m G C v tem primeru imenujemo kodna točka. Razdalja med dvema točkama v grafu je definirana kot dolžina najkrajše poti med njima. Po komunikacijskem kanalu se, v primeru uporabe kode v grafu, kot kodne besede pošiljajo oznake kodnih točk. Definicija 5.1.1. Množica C C V je t-koda v grafu G = (V,E), če za vsak par različnih točk u,v G C velja d{u, v)>2t+l. Definicija 5.1.2. Množica C C V je t-popolna koda v grafu G = (V,E), če za vsak ueV obstaja natanko enveC, da velja d{u,v) < t. C je torej 1-popolna koda v grafu G = (V, E) natanko takrat, ko množica vseh zaprtih soseščin njenih elementov tvori particijo množice V. Množica točk D C V je v grafu G = (V, E) dominantna, če je vsaka točka w G V - D sosednja vsaj eni točki v e D. Dominantno število grafa G, 7(G), je enako velikosti najmanjše dominantne množice V. Znan je naslednji rezultat, ki je bil večkrat neodvisno dokazan [17, Izrek 4.2]. Trditev 5.1.3. Naj bo C 1-popolna koda v grafu G, potem velja |C| = 7(G). D 5.2. GRAFI SIERPIŃSKEGA 63 Iz zgornjega izreka sledi, da imajo vse 1-popolne kode v G enako moč, ta rezultat pa posplošen velja tudi za vse t-popolne kode [36, Posledica 4.6]. Odločitveni problem ali v poljubnem grafu za izbrano število t > 1 obstaja t-popolna koda, sodi v razred iVP-polnih problemov [36, Izrek 7.0.1]. 5.2 Grafi Sierpińskega Lipscomb je leta 1974 v [39, 40] na množici neskončnih zaporedij z vrednostmi iz poljubne množice vpeljal relacijo ~ in na ta način študiral določene topološke prostore. Leta 1992 je Milutinović v [55] razširil definicijo relacije ~ na urejene n-terice in med drugim pokazal, da je Lipscombov prostor posplošitev trikotne krivulje Sierpińskega. Leta 1997 sta Klavžar in Milutinović v [29] z relacijo ~ na urejenih n-tericah definirala dvoparametrične grafe S(n, k), ki so bili kasneje v [32] poimenovani grafi Sierpińskega. Definirajmo to relacijo ~ na množici (Zfc)ra. Definicija 5.2.1. Dve različni n-terici u = (ul}u2, ...,un) in v = (vl}v2,... ,vn) iz množice {0,1,... , k - l}n, sta v relaciji ~ natanko takrat, ko obstaja tak h G {l,2,...,n}, da velja (i) ut = vt, zat=l,...,h-l; (ii) uh^vh; (iii) ut = vh invt = uh, za t = h + 1,..., n. Na sliki 5.2 je prikazana shematična vizualizacija relacije ~, na sliki 5.4 pa je za primer prikazan graf S(2, 4). h u = • • • • • • U^^ v= • • • • • • Slika 5.2: Vizualizacija relacije Definirajmo grafe Sierpińskega . Definicija 5.2.2. Graf S {n, k) je definiran na množici točk {0,1,..., k- l}n. Dve različni točki u = (iui2,... ,zn) in v = (juj2,... ,jn) sta sosednji natanko takrat, ko velja u~v. 64 POGLAVJE 5. 1-POPOLNE KODE V nadaljevanju bomo namesto (u1, u2, . . . , un) pisali krajše u1u2 . . . un. Oglejmo si naslednjo inačico Hanojskih stolpov z n ploščicami in k položaji. Dovoljena stanja so enaka stanjem posplošnih Hanojskih stolpov, ki smo jih obravnavali v poglavju 2. To pomeni, da so na vsakem položaju ploščice razvrščene po velikosti od večjih spodaj do manjših zgoraj, oziroma enakovredno, manjša ploščica vedno leži nad večjo. Legalne poteze so definirane takole. Predpostavimo, i j Slika 5.3: Dovoljena poteza Hanojskih stolpov z zamenjavami da imamo stanje, v katerem je t vrhnjih ploščic na položaju i tudi t najmanjših. Če je na položaju j vrhnja ploščica (t + 1), lahko v eni potezi medsebojno zamenjamo položaj ploščice (t + 1) in položaj t najmanjših ploščic (slika 5.3). Zaradi pravila prestavljanja to inačico imenujemo Hanojski stolpi z zamenjavami. 00 03 02 30 11 n ^J 32 22 Slika 5.4: Graf Sierpińskega S(2, 4) V [29] je dokazan naslednji izrek. Izrek 5.2.3. Naj bo n ? 1 in k ? 1. Graf Hanojskih stolpov z zamenjavami je izomorfen grafu S(n, k). 5.2. NEKATERI PODGRAFI 65 Leta 1999 so Cull, Li in Nelson [5, 6, 37] obravnavali popolne kode v grafih klasičnih Hanojskih stolpov. V [5] je pokazano, da graf H3n vsebuje v bistvu enolično 1-popolno kodo. Poleg tega so kodne točke opisane z enostavnim pogojem, kar omogoča implementacijo učinkovitega algoritma za dekodiranje. Kodne točke so tista stanja, ki jih opisuje n-terica, definirana na strani 10, s sodim število enic in sodim številom dvojk. Ti rezultati so ponovljeni v [6]. V [37] je dokazano, da poleg 1-popolnih kod in trivialnih t-popolnih kod drugih popolnih kod v H3n ni. Trivialne popolne kode v H3n imajo eno kodno točko pri lihem n in tri kodne točke pri sodem n. V [29] je dokazan naslednji izrek. Izrek 5.2.4. Za vsak n ? 1 je graf S(n,3) izomorfen grafu H3n. Grafi Sierpińskega S(n, k) torej predstavljajo posplošitev grafov klasičnih Ha-nojskih stolpov. Za k = 3 so grafi S(n, k) sicer res izomorfni grafom H3n, vendar pa 000 000 111 112 102 100 200 201 221 222 111 U2 121 122 211 212 221 222 H33 S(3,3) Slika 5.5: Grafa H33 in S(3, 3) je označevanje njihovih točk bistveno drugačno od označevanja v grafih klasičnih Hanojskih stolpov (slika 5.5). Zaradi tega se pogoja (sodo število enk in sodo število dvojk v n-terici) za kodno točko ne da enostavno posplošiti na grafih Sier-pińskega. 5.3 Nekateri podgrafi grafa S(n, k) V tem razdelku bomo vpeljali notacijo za nekatere podgrafe grafa S(n, k), ki so analogni podgrafom posplošenih Hanojskih stolpov, ki smo jih opisovali v podraz- 66 POGLAVJE 5. 1-POPOLNE KODE delku 3.3.2. Oglejmo si najprej soseščino poljubne točke grafa S(n, k). Spomnimo se definicije 5.2.1, v kateri smo definirali kdaj sta dve n-terici u = (u1}u2,... ,un) in v=(v1}v2,...,vn)iz množice (Zk)n v relaciji ~. V nadaljevanju bomo uporabljali oznako h z enakim pomenom, kot ga ima v tej definiciji. Recimo, da imamo graf S(5, 3), zanima pa nas točka (0, 2, 0,1,1). Tej točki sta sosednji točki (0, 2, 0,1, 0) in (0,2,0,1,2), pri obeh je h = 5. Točki (0,2,0,1,1) je poleg navedenih dveh sosednja le še točka (0,2,1,0,0), pri kateri je h = 3. Če posplošimo, vsaka točka (Ul,u2,...,un) G S(n,k) ima k- 1 sosednjih točk oblike (u1}u2,... ,un_1}vn), vn ^ un, za katere velja h = n. Vse točke oblike (uu u2,..., uh, c,... , c) imajo poleg omenjenih k-1 sosednjih točk za sosedo še točko (ul}u2,..., uh.l}c, uh...,uh). Izjema so le točke oblike (c,c,...,c), te imajo natanko k - 1 sosedov. Iz povedanega lahko povzamemo naslednja spoznanja. Graf S(n, k) vsebuje |{0,1,... , k - l}n\ = kn točk in je povezan. Naj bo i G {0,1,... , k - 1}, potem točko iz... z grafa S(n, k) imenujemo ekstremna točka. Graf S(n, k) vsebuje k ekstremnih točk, ki imajo stopnjo k - 1 in k(kn~l - 1) preostalih točk, ki so stopnje k. Naj bo r G {1, 2,..., n} in iu z2,..., ir G {0,1,..., k - 1}. Podgraf S(n, k) induciran s točkami, katerih prve r koordinate so enake %x%2 ...ir, bomo označili z S(n,k;i1}i2,...,ir). Graf S{n, k;n,i2,..., ir) je izomorfen grafu S(n - r, k). V primeru r = n - 1 je graf S(n, k; n, i2,..., ira_i) izomorfen grafu S(n, 1), ki pa je izomorfen polnemu grafu Kk. S(n, k; n, i2,... , in) je graf na eni točki. Opazimo tudi, da lahko točke grafa S(n, k) pokrijemo s točkami kr disjunktnih podgrafov S(n, k; i1} i2,..., ir), ki jih dobimo iz vseh možnih izbir za %x%2 ...%r. Uporabljali bomo naravno konvencijo, da splošen simbol S(n, k;i1}i2,..., ir) za r = 0 pomeni sam graf S(n, k). Podgraf S(n, k; i) vsebuje eno ekstremno točko iz S(n, k), namreč ii...i, in fc-1 točk oblike ijj ...j, j = i, ki so vsaka zase sosednje točkam jii... % iz podgrafov S(n,k;j). Torej, v grafu S(n,k) je natanko ena povezava med vsakim parom k podgrafov S(n, k; z), % = 0,1,..., k - 1. Za vsak podgraf S(n, k; iu i2,... , %r) grafa S(n, k), r = 1,... , n- 1, bomo točke oblike %x%2 ... irjj ...j, kjer j nastopa n - r krat, imenovali ekstremne točke grafa S{n, k;n,i2,...,ir), saj se preslikajo na ekstremne točke grafa S{n-r, k) z vsakim izomorfizmom med S(n, k;i1}i2,..., ir) in S(n -r,k). Vpeljimo uporabno okrajšano notacijo, ki bo poenostavila takó formulacijo, kot tudi vizualizacijo nadaljnjih izpeljevanj. Popoln pomen in pomembnost take notacije bo postal jasen v izreku 5.4.3, kjer bomo dokazali, da so štirje primeri, ki jih bomo sedaj opisali, pravzaprav edini možni. Naj bo C 1-popolna koda v grafu S(n, k)in(i1}..., ir) G {0,... , k- l}r, potem 5.3. NEKATERI PODGRAFI 67 S(n,M1,«2,---,v)* pomeni: “Za 0 < L < k - 1 vse ekstremne točke %1%2 ...irL...Liz S(n, k; i1} i2,... , ir) pripadajo C.” V izreku 5.4.3 bomo dokazali, da je to možno le za sode m = n r. S(n,k;z1,Z2,...,iry pomeni: “iH2...irj...j je sosednja kodni točki zunaj S(n, k; n, i2,... , ir), in vse druge ekstremne točke %1%2 ... %rL.. .L, 0 < L < k - 1, L ^ j, so sosednje kodnim točkam znotraj S(n, k;i1}i2,..., ir).” V izreku 5.4.3 bomo dokazali, da je tudi to možno le za sode m = n r. S(n)k-i1)i2)...)ir)* pomeni: “Za 0 < L < fc-1 so vse ekstremne točke i1i2 ...zrL...Liz S(n, k; i1 i2,... , ir) sosednje kodnim točkam zunaj S(n, k; n, i2,... , ir).” V izreku 5.4.3 bomo dokazali, da je to možno le za lihe m = n r. S(n,k;i1,i2,...,ir)j pomeni: “i1i2 ...irj...j pripada C, in v S(n, k;i1}i2,..., ir) so vse druge ekstremne točke %1%2 ...irL...L,Q 1 in k > 1 graf S(n, k) vsebuje v bistvu enolično 1-popolno kodo. Bolj natančno, vsaka 1-popolna koda C vsebuje vsaj eno ekstremno točko in, ob predpostavki, da ekstremna točka 00 ... 0 pripada C, dokažemo, da je C enolična. Ker je S(n, 1) = K1 za vsak n, ni za ta primer kaj dokazovati. S(n, 2) je izomorfen poti na 2n točkah in trditev lahko preprosto dokažemo tudi za ta primer. Dokaz enoličnosti za k = 3 je bil objavljen že v [5] in [6] za grafe H3}, ki pa so izomorfni grafom S(n, 3). Za določeno 1-popolno kodo C v S(n, k), k > 2, in za vsako ekstremno točko iz S(n, k;z1,z2,...,ir), imamo natanko tri naslednje možnosti: 1. v je sosednja kodni točki znotraj S(n, k; i1 i2,... , ir); 2. v je sosednja kodni točki zunaj S(n, k; i1} z2,... , ir); 3. v je kodna točka. Število ekstremnih točk S(n, k; i1} i2,... , ir) tipa 1, 2 in 3 bomo v tem vrstnem redu označili z a, b in c. Seveda je a + b + c = n. Da poenostavimo notacijo, označimo m = n - r, l < m < n. Spomnimo se še, da S(n, k; n, i2,..., ir) za r = 0 pomeni sam graf S(n, k). V naslednji lemi 5.4.1 in izreku 5.4.2 bomo podali nekaj spoznanj o 1-popolnih kodah v S(n, k) le s pomočjo preprostih prijemov s področja teorije števil. Lema 5.4.1. Naj bo C poljubna 1-popolna koda v S(n, k), k>2. Naj bo i1i2 ...ir katerikoli element v {0,1,... , k - l}r, kjer r G {0,1,..., n - 1}. Če imajo b, c in m enak pomen, kot smo opisali zgoraj, potem (k + 1) | (km -ck-b). Dokaz. Označimo H = S(n, k; i1 i2,... , ir) in takoj povejmo, da je število točk v grafu H enako km. Ekstremna točka iz H ima k - 1 sosednjih točk v H. V zaprti soseščini ekstremnih točk tipa 3 je ck točk iz H. Če je ekstremna točka u iz H sosednja kodni točki v iz C, v i H, potem jasno u ni sosednja nobeni kodni točki iz H. Vsaka izmed preostalih km-ck-b točk iz H je stopnje k, torej morajo biti pokrite z zaprto soseščino velikosti k + 1. Sledi, da mora biti število km -ck-b deljivo z k + 1. D Trditev 5.4.2. Pri predpostavkah leme 5.4.1 velja naslednje. Če je m sod, potem je ali c = k in b = 0 ali b = c + 1, če pa je m lih, potem je ali c = 0 in b = k ali c = b+l. Dokaz. Ker -1 = k (mod (fc + 1)), sledi (-l)m = km (mod (fc + 1)), in potem (-l)m - ck - b = km-ck-b (mod (k + 1)). Z uporabo leme 5.4.1 sklepamo 5.4. ENOLIČNA 1-POPOLNA KODA 69 (-l)m - ck - b = 0 (mod (k + 1)), torej (-l)m + c - b = c(k + 1) (mod (k + 1)). Zaključimo, da (-l)m + c - b = 0 (mod (k + 1)). Primer 1: m je sod. Ker 1 + c - b = 0 (mod (fc + 1)), obstaja tako število L, da velja b-c=l + (k + l)L. Iz0 1 dobimo na desni strani neenakosti protislovje: 2c + 1 < k{\ - L) - L < 0. V primeru L < -2, dobimo na levi strani neenakosti protislovje: 2c + 1 > (k + l)L > 2(2k + 1), torej O k. Zato imamo le dve možnosti: L = 0 ali -C —— — X. Pri L = 0 dobimo 6 = c+ 1 in pri L = -1 dobimo 6 = c + k. Ker 6 < k in c > 0, je drugi primer možen le, ko velja c = 0 in b = k. Primer 2: m je lih. V tem primeru dobimo -1 + c - b = 0 (mod (fc + 1)) in obstaja tako število L, da velja c-b=l + (k + l)L. Nadaljujemo enako kot v primeru 1, le b in c zamenjamo. D Pravzaprav lahko dokažemo celo močnejši rezultat od tistega v izreku 5.4.2. Izrek 5.4.3. Pri predpostavkah leme 5.4.1 velja naslednje. Če je m sod, potem je ali c = k in b = 0 ali c = 0 in b = l, če pa je m lih, potem je alic = 0 in b = k ali c= 1 inb = 0. Dokaz. Z indukcijo po m = n - r G {1,..., n} bomo dokazali, da za vsak podgraf S(n, k;H,i2,...,ir)v S(n, k) velja natanko eden izmed naslednjih štirih primerov (za vizualizacijo teh primerov v dokazu je priporočljivo uporabiti sliko 5.7): 1. m = n - r je sod, c = k, b = 0, to je S(n, k;n,i2,..., ir), ; 2. m = n - r je sod, c = 0, b = 1, to je S(n, k; il} i2,..., ir)i ; 3. m = n - r je lih, c = 0, b = k, to je S(n, k;i1}i2,..., ir)* ; 4. m = n - r je lih, c = 1, b = 0, to je S(n, k;i1}i2,..., ir), . Za m = 1, ker je S(n, k; i1} i2,..., in-i) izomorfen popolnemu grafu Kk, imamo le dve možnosti: podgraf S(n, k; iu i2,... , zra_i) ne vsebuje nobene kodne točke ali vsebuje natanko eno kodno točko. V prvem primeru so vse točke sosednje kodnim točkam zunaj podgrafa, torej S(n, k;n,i2,..., ira_i)*. V drugem primeru naj bo %x%2 ... in_!J E C. Ker so vse druge točke podgrafa sosednje %x%2 ... %n_l3, je podgraf tipa S(n, k;i1}i2,..., i„_1)J- . 70 POGLAVJE 5. 1-POPOLNE KODE S(4,3;l,2,2) S(4,3;2,2) Slika 5.7: Primeri podgrafov v 5(4,3) V preostalem delu dokaza bomo uporabljali naslednje okrajšave. Naj bo H = S(n, k;i1}i2,..., ir) in H{L) = S(n, k;i1}i2,..., ir,L). Naj bo m sodo število in predpostavimo, da trditev velja za m- 1. Premislimo o podgrafu Hzn-r = m. Za vsakega od njegovih podgrafov H(L), 0 1 liho število in predpostavimo, da trditev velja za m - 1. Premislimo o podgrafu Hzn-r = m. Vsak od njegovih podgrafov H(L), 0 ~<&~ ~<&~ A^y,A _-(X fr*^p tf p^f pč 3P v tJ* pr^p tJ" tJ" pr^sp "o- // ,-*. A. Slika 5.8: Struktura S(n, k; i1, i2, . . . , ir) ko je m = n - r sod Na sliki 5.9 spodnja vrstica prikazuje edini dve možnosti, ko je m = n - r lih. Leva stran slike prikazuje, ko S(n, k; i1, . . . , ir)i, potem S(n, k; i1, . . . , ir, i)? in S(n, k; i1, . . . , ir, j)i za vse j = i, medtem ko desna stran prikazuje, da iz S(n, k; i1, . . . , ir)? sledi S(n, k; i1, . . . , ir, i)i, 0 ? i ? k - 1 . 1 5.4. ENOLIČNA 1-POPOLNA KODA 73 fč 3f 2, in naj bo r G {0,1,...,ra-1}. Potem: 1. izS(n,k;i1...,ir)* sledi S(n,k;i1... ,ir,j)j, 0 < j < k - 1; 2. iz S(n,k;i1}...,ir) sledi S(n,k;z1}... ,ir,i)* in S(n,k;z1}... ,zr,j)t za 0 < j < k - 1, j = i; 3. iz S(n, k;n,..., ir)* sledi S(n, k;i1..., ir, i), 0 2. Če je n lih, C vsebuje natanko eno ekstremno točko j j ... j in če je n sod, C vsebuje vse ekstremne točke iz S (n, k). Dokaz. Pri celem grafu S(n, k) imamo 6 = 0. Od tod iz izreka 5.4.3 sledi c = k, če je m sod in c = 1, če je m lih. D Izrek 5.4.6. Za vsak n > 1 in vsak k > 1 ima graf S(n, k) enolično 1-popolno kodo, če je n sod in natanko k 1-popolnih kod, če je n lih. Natančneje, naj bo n lih in naj bo j j ...j ekstremna točka S(n, k), ki pripada 1-popolni kodi C, potem je C enolična. Dokaz. Najprej bomo pokazali trditve enoličnost z večkratno uporabo izreka 5.4.4. Naj bo n sod in C 1-popolna koda v S(n,k). Po posledici 5.4.5 morajo vse ekstremne točke iz S(n,k) pripadati C, zato velja S{n,k)#. Spomnimo se, da je S(n,k) induciran z (disjunktnimi) podgrafi S(n,k;i). Iz primera 1 izreka 5.4.4 sledi, da velja S(n, k; i)t za vse z. S(n, k) je induciran tudi s podgrafi S(n, k; i, j), tako dobimo z uporabo primera 4 istega izreka S(n,k;z,z), in S{n,k;i,jY za j = z. Poleg tega je za vsak podgraf enolično določljivo kateri lastnosti zadošča. Z uporabo primerov 1 in 2 ter upoštevanjem da je S(n, k) induciran s podgrafi S(n,k;i,j,L) ugotovimo, da je za vsakega od njih enolično določljivo ali zadošča S(n, k; i,j,L)p ali S(n, k; i,j,L)*. Z izmenično uporabo primerov 3, 4 in primerov 1, 2 in upoštevanjem da je S(n, k) induciran s podgrafi S(n, k;n... ira_i) zaključimo, da je za vsakega od njih enolično določljivo ali zadošča S(n, k; z1} z2,..., i^)* ali S(n, k;i1}i2,..., in_x)q (kateri lastnosti zadošča je enoločno določljivo za vsako izbiro indeksov iu i2, ..., ira_i v prvem primeru in za vsako izbiro indeksov iu i2, ...,in-i ter indeksa q v drugem primeru). Če imamo S(n, k; iui2,..., in-i)*, potem S(n, k; n, i2,..., ira_i) ne vsebuje kodne točke in ixi2 ... in_iq je edina kodna točka v S{n, k; z1} z2,..., in_x), če S(n, fc; n, r2,... , rra_i), (spomnimo se, da so ti grafi izomorfni polnim grafom). Zaključimo, da so točke, ki pripadajo C enolično določene. Dokaz za lih n je analogen, le da začnemo s S(n, k)j in na prvem koraku uporabimo primer 4 iz izreka 5.4.4. V nadaljevanju bomo pokazali, da edini zgoraj opisani možni kandidati za 1-popolne kode tudi zares obstajajo. Nadaljujemo z indukcijo po n, s katero bomo dokazali, da za vsak sod n obstaja taka podmnožica Dn C V{S{n,k)), da vsaka točka v = 00... 0 iz S(n, k) ali pripada Dn, ali je sosednja natanko eni točki iz Dn, in da 00... 0 ni niti v Dn, niti ni sosednja katerikoli točki iz Dn. Z isto indukcijo bomo istočasno dokazali tudi, da za vsak lih n obstaja taka podmnožica 5.4. ENOLIČNA 1-POPOLNA KODA 75 Dn C V(S(n, fc)), da vsaka točka v ^ ii... z, 0 < z < k - 1 ali pripada Dn, ali je sosednja natanko eni točki iz Dn, in da vsaka točka U... z, 0 < i < k - 1 ne pripada niti Dn, niti ni sosednja katerikoli točki iz L>„. Vsaka podmnožica V(S(l,k)) z enim samim elementom je 1-popolna koda v S(l,k). Tudi množica vseh ekstremnih točk iz V (S (2, k)) je 1-popolna koda v S (2, k), za primer si oglejmo graf S(2, 4) na sliki 5.4. Tudi podmnožici Dx = 0 za S(l, k) in L>2 = {10, 20,... (k- 1)0} za S(2, k) zadoščata vsem zahtevam dodatnih trditev. Naj bon>2 sodo število. Potem je n - 1 > 1 liho število in po induktivni predpostavki obstaja natanko ena 1-popolna koda C C V(S(n - 1, k)), ki vsebuje točko 00... 0. Za vsak i, 0 < i < k - 1, naj bo fc : V^ra - 1, fc)) —> V(S(n, k)) tak izomorfizem iz S(n-l,k)v podgraf S(n, fc; i) grafa S(n, k), da je L(00 ... 0) = u...i. Potem je /o(C) U • • • U fk-i(C) 1-popolna koda v S(n, k). Namreč, vsaka točka iz S(n,k;z) ali pripada f^C) ali je sosednja natanko eni točki iz fi(C) in ni sosednja nobeni točki iz fj(C) za j ^ i. To sledi iz opažanja, da je edina povezava med podgrafom f^C) in podgrafom fj(C) povezava med točkama ijj ...j in jii...% ter, da je ekstremna točka iz S(n-l, k) različna od 00 ... 0 preslikana s /_,- v jii... i in ne pripada C. Naj bo Dn_x C V(S(n-l, k)) taka množica, da vsaka točka iz S(n-l,k) razen u... z, 0 < i < k - 1 ali pripada Dn_x ali je sosednja natanko eni točki iz Dn_x. Za i = 0,..., k - 1 naj bo 9i : V^ra - 1, fc)) —> V(S(n, k)) tak izomorfizem iz S{n - 1, fc) na podgraf 5(n, fc; i) grafa 5(n, fc) da je ^(00 ... 0) = iQ ... 0. Potem vsaka točka iz S(n, k), razen 00 ... 0, ali pripada ^0pn-i)U^(C)U- • -U^.^C), ali je sosednja natanko eni njenih točk. To sledi iz lastnosti izomorfizma za vse, razen ekstremne točke iz S(n, k; 0). Trditev za vsako točko oblike Oi.. .i, 1 < i < k - 1 sledi iz dejstva, da je Oz... i sosednja zO ... 0 in zO ... 0 G ^(C). Ker 00 ... 0 ni sosednja nobeni točki, ki ni iz 0O(A»-i), prav tako zadošča zahtevani lastnosti. Naj bo n > 2 liho število. Potem je n - 1 > 1 sodo število in po induktivni predpostavki obstaja natanko ena 1-popolna koda C C V(S(n - 1, k)). Prav tako obstaja taka podmnožica L>ra-i C V(S(n - l, k)), da vsaka točka iz S(n - l, k), razen 00... 0, ali pripada Dn_l, ali je sosednja natanko eni točki iz Dn_x. Za i = 0,..., k - 1 naj bo preslikava 9i : V(S(n - 1, fc)) —> V(S(n, k)) definirana kot zgoraj. Potem vsaka točka iz ^(n,*;) ali pripada ^o(C)U^i(Dra_i)U---U^fc_i(Dra_i), ali je sosednja natanko eni njenih točk. Tudi to sledi iz dejstva, da je 0«... i sosednja «0... 0. In nazadnje, za i = 1,... , k - 1 naj bo f\ : V(S(n - 1, fc)) —> V(S(n, fc)) definirana kot zgoraj. Potem /0(A»-i) U ••• U /fc_i(D„_i) zadošča zahtevi, da vsaka točka iz S(n, fc) razen ekstremnih točk ali pripada tej množici, ali je sosednja natanko eni točki iz nje. To sledi iz lastnosti izomorfne vložitve in iz zapažanja, da nobena ekstremna točka ne pripada Dnl, kar je enostavno dokazati z isto 76 POGLAVJE 5. 1-POPOLNE KODE indukcijo, če še to dodatno trditev dodamo k trditvam, ki smo jih dokazali z indukcijo. D Dobljeni rezultati nam omogočajo izračun j(S(n,k)) na sledeč način. Naj bo r = 0,l,...,n-l,m = n-r. Če je m lih, naj bo c{m) = \CnV{S{n,k;i1,i2,...,ir))\, če S(n, k; i1i2,... ,ir)j, in b{m) = \C n V(S(n, k; i1 i2,..., ir))\ , če S(n, k; i1 i2,..., ir)*. Če je m sod, naj bo c(m) = \CriV(S(n,k;n,i2,...,ir))\, če S(n, k; i1} i2,..., ir)», in b(m) = \C n V^ra, fc; i1, i2,..., ir))| , če S(n, k;n,i2,..., ir)' . S tako notacijo bomo poenostavili formulacijo naslednje posledice, istočasno pa je z njo tudi upravičena, saj induktivni dokaz posledice pokaže, da kardinalnosti zgornjih presekov niso odvisne od izbire i1 i2,... , ir in j. Posledica 5.4.7. Za vsak L > 1, L2^-1 i i k2L~2 — 1 c(2L-l) =, b(2L-l) = k---------, k + 1 k + 1 ' c(2L) = k------, b(2L) =---------- . k + 1 k + 1 Dokaz. Očitno velja c(l) = 1, 6(1) = 0. Iz izreka 5.4.4 dobimo naslednje rekurzivne formule c(2L) = kc(2L-l), b{2L) = b(2L-l) + (k-l)c(2L-l), c(2L+l) = c(2L) + (k-l)b(2L), b(2L+l) = kb{2L) za L > 1. Iz teh izpeljemo naslednji induktivni dokaz c(2L) = kc(2L-l) = k k2 1 + 1 ; l,2L-2 _ i P^-1 -1-1 P^ — 1 b(2L) = b(2L - 1) + (k - l)c(2L - 1) = k,---------+ (k-l) =--------; fc + 1 J k + 1 k+1' p^-1 i i L2^ _ i L2^+1 i i c(2L+l) = c(2L) + (k - l)b(2L) = k + (k - 1)--------=; k+1 k+1 k+1 ' 6(2^+1) = kb(2L) = k k2l-l k + 1 ' Z uporabo trditve 5.1.3 in posledice 5.4.7 dobimo naslednji izrek. 5.5. DEKODIRNI ALGORITEM 77 Izrek 5.4.8. Za vsak n ? 1 in vsak k ? 1, k -y(S(n,k)) kn-1 +1 ; n sod, k +1 kn +1 ; k+1 n lih. 5.5 Dekodirni algoritem Naj bo C poljubna 1-popolna koda v S(n, k) in naj bo v = vxv2 ...vn točka iz S(n, k). Spodaj predstavljeni algoritem odloči, ali je v kodna točka in če ni, potem določi točki v sosednjo kodno točko. Algoritem zaradi razumljivosti zgoščeno predstavimo v psevdokodi. Delujočo implementacijo v programskem jeziku Java, podamo v dodatku A. 1. subroutine S(n, k; vl} v2,... ,vr)3 begin 2. if(r = ra-l) 3. then if(vn = j) 4. then v eC 5. else v' = (vl,v2,...,vn-l,j) 6. else if(t;r+1= j) 7. then call S(n, k; v1} v2,... , vr+1), 8. else call S(n, k; v1} v2,... ,vr+iy 9. end 10. subroutine S(n, k; vu v2,... ,vr)* begin 11. if(r = ra-l) 12. then v = vl... vsij ... j, j ^ i, v' = vl... vsji ...i 13. else call S(n, k; v1} v2,... , vr+1)v+1 14. end 15. subroutine S(n, k; vu v2,... ,vr)* begin 16. call S(n,k;vl}v2,...,vr+l)Vr+1 17. end 18. subroutine S(n, k; v1} v2,... ,vr)* begin 19. if(t;r+i=j) 20. then call S(n, k; vu v2,... ,vr+1)* 21. else call S(n, k; vl} v2,... ,vr+l)3 22. end 23. main_program begin 24. if(n odd) _ 78 POGLAVJE 5. 1-POPOLNE KODE 25. then call S(n, k)j 26. else call S(n, k)? 27. end Algoritem najprej določi, ali je n liho ali sodo število. V prvem primeru moramo vedeti, katera ekstremna točka jj . . . j pripada C in v vrstici 25 algoritem pokliče podprogram S(n, k; v1, v2, . . . , vr)j z r = 0. Če je n lih, algoritem pokliče podprogram S(n, k; v1, v2, . . . , vr)? z r = 0 v vrstici 26. Tok algoritma je grafično predstavljen na sliki 5.10. END START 4/5 12 13 21" A Slika 5.10: Diagram prehajanja stanj Izvajanje algoritma se ustavi, ko je r = n- 1. Končni točki algoritma sta dve, v podprogramu S(n, k;vhv2,... , vr)j in v S(n, k;v1,v2,..., vr)*. V prvem primeru, če je vn = j, je za točko v ugotovljeno, da je kodna točka (v vrstici 4), sicer pa je kodna točka njena sosednja točka vxv2 ... vn.xj (v vrstici 5). V drugem primeru ni kodna točka niti v, niti katerakoli od njenih sosednjih točk v polnem grafu S{n, k;v1}v2,..., vn_x). Ker smo končali v podprogramu S(n, k;v1}v2,..., vn_x)\ je točka v sosednja enolični kodni točki v' zunaj polnega grafa (v vrstici 12). Točko v' določimo na naslednji način. Če v = vx... vsij ...j,j^i, potem v' = vi... vsji ...i. Za izračun vrednosti s imamo dve možnosti. Ali si med izvajanjem algoritma zapomnimo vrednost zadnjega indeksa r za katerega se dve zaporedni komponenti vrx in vr razlikujeta, ali to vrednost ločeno izračunamo ob samem 5.5. DEKODIRNI ALGORITEM 79 zaključku algoritma, v vrstici 12. Opis algoritma je s tem končan. Dejstvo da deluje pravilno, sledi neposredno iz (dokazov) izrekov 5.4.6 in 5.4.4. Dekodirni algoritem je optimalen, to je linearen glede na n, dolžino vhodne besede. Dekodirni algoritem je pravzaprav obrnjeni algoritem konstrukcije 1-popolne kode, ki je shematično prikazan na slikah 5.9 in 5.8. Konkretno si lahko konstrukcijo 1-popolne kode ogledamo na sliki 5.11 za grafe S(n, 3), in na sliki 5.12 za grafe S(n, 4). Na sliki 5.13 so s sivimi liki prikazane zaprte soseščine kodnih točk 1-popolne kode v grafih S(n, 4) za k = 1, 2, 3, 4, 5, na slikah 5.14 in 5.15 pa so prikazane zaprte soseščine kodnih točk 1-popolne kode v grafih S(n,5) za k = 1, 2, 3, 4, 5. n=0 n=l n=2 n=3 Slika 5.11: Konstrukcija 1-popolne kode v grafih S(n, 3) 80 POGLAVJE 5. 1-POPOLNE KODE n=0 n=l n=2 n=3 Slika 5.12: Konstrukcija 1-popolne kode v grafih S(n, 4) 5.5. DEKODIRNI ALGORITEM 81 S(l,4) S(2,4) S(3,4) S(4,4) Slika 5.13: Zaprte soseščine kodnih točk v grafih S(n, 4) 82 POGLAVJE 5. 1-POPOLNE KODE vxi r^y s(2>5) S(l,5) Slika 5.14: Zaprte soseščine kodnih točk v grafih S(n, 5) (prvi del) 5.5. DEKODIRNI ALGORITEM 83 Slika 5.15: Zaprte soseščine kodnih točk v grafih S(n, 5) (drugi del) 84 POGLAVJE 5. 1-POPOLNE KODE Poglavje 6 Zaključek V zaključnem poglavju bomo predstavili nekaj aktualnega dogajanja na področju raziskovanja Hanojskih stolpov. Podali bomo tudi ideje in možne smernice nadaljnjih raziskovanj. Med najbolj privlačne odprte probleme lahko gotovo uvrstimo dokaz optimal-nosti Frame-Stewartove strategije prestavljanja ploščic. S tem v zvezi bi bilo koristno poiskati karakterizacijo vseh najkrajših poti med dvema popolnima stanjema ali celo njihovo preštetje. Do sedaj tudi še ni bilo dokazano, ali je razdalja med dvema popolnima stanjema največja razdalja v grafu, kar pomeni, da je enaka premeru grafa. Kazalo bi premisliti tudi pristop Majumdarja [47] pri “dokazovanju” optimalnosti Frame-Stewartove strategije za stolpe s štirimi položaji. Njegovo razmišljanje sloni na naslednji predpostavki. Vsaka pot med dvema popolnima stanjema, pri kateri so ob prestavitvi največje ploščice, ostale ploščice razporejene na pomožnih položajih v nezaporedni velikosti, je največ tako dobra, kot pot dobljena s Frame-Stewartovo strategijo. Med novejše rezultate v tej smeri lahko uvrstimo članek [30], v katerem Klavžar in Milutinović predstavita enostaven eksplicitni izraz za dolžino poti po Frame-Stewartovi strategiji, poleg tega pa podata karakterizacijo množice vseh takih parov števil (n1, n2) iz definicije Stewartovega algoritma 4.1.4, pri katerih je minimalna dolžina poti dosežena. Szegedy v [80] dokaže, da je za k položajev potrebnih vsaj 2Ckn1/(k-2) prestavitev. Bode in Hinz sta v [2] potrdila optimalnost Frame-Stewartovega pristopa za posplošene Hanojske stolpe s štirimi položaji in do 17 ploščic, kar sta preverila s pomočjo računalnika. V lemi 2.3.2 smo videli, da se v splošnem več n-teric preslika v isto p-terico, v posledici 2.2.4 pa smo pokazali, da je število vseh možnih p-teric celo v polinomski odvisnosti od števila ploščic, medtem ko je število n-teric v grafih Hpn v eksponentni odvisnosti. Opis stanja Hanojskih stolpov s p-terico je zadosten, da poznamo vse možnosti za naslednjo prestavitev ploščice. Torej imamo dobre razloge za podrobnejšo analizo naslednjih grafov. 85 86 POGLAVJE 6. ZAKLJUČEK Definicija 6.0.1. Točke grafa Tpn = (V, E) naj bodo vse možne razporeditve vrhnjih ploščic posplošenih Hanojskih stolpov s p položaji in n ploščicami. Dve točki sta sosednji, če lahko preidemo iz ene v drugo z dovoljeno prestavitvijo ploščice. Graf Tpn = (V, E) imenujemo graf stanj vrhnjih ploščic. Točke grafa Tpn opisujemo s p-tericami s = (s0,s1,. . .,sp-1) ? (Zn+1)p, za katere morata veljati pogoja iz leme 2.2.2 oziroma enakovredno, ne sme veljati niti en pogoj iz leme 2.2.5. Na sliki 6.1 sta za primer prikazana grafa T33 in T34. Slika 6.1: Grafa T33 in T34 Na povezavo med grafom klasičnih Hanojskih stolpov in trikotno krivuljo Sier-pińskega je opozoril že Ian Stewart v [73]. Na podlagi te povezave so Hinz in Schief v [25], ter neodvisno Chan v [3] izpeljali zanimiv rezultat, da je povprečna razdalja med dvema točkama na trikotni krivulji Sierpińskega enaka 486865. Rezultat bi bilo zanimivo posplošiti na grafe Sierpińskega, vendar pa je dobljen s postopkom, za katerega posplošitev ni očitna. Kasneje Hinz predstavi tudi algoritem za izračun poti med dvema točkama [20] grafa klasičnih Hanojskih stolpov. Leta 2003 je Romik v [65] predstavil še učinkovitejši algoritem. Ključni del članka je končni avtomat, kateremu za izračun dolžine poti med dvema točkama ni potrebno izračunati dolžine poti, na kateri premaknemo največjo ploščico enkrat in dolžine poti na kateri premaknemo največjo ploščico dvakrat, v povprečju je dovolj, da avtomat analizira položaje 63 38 ? 1, 66 (v limiti, ko gre n proti neskončnosti) največjih 87 ploščic, in ve, katera od teh dveh poti je krajša. S pomočjo končnega avtomata Romik ponovi izračun povprečne razdalje v grafu HL. Z njegovim pristopom bi bilo morda lažje izračunati povprečno razdaljo v grafih Sierpińskega. Po članku [29], v katerem so bili definirani grafi Sierpińskega, je bilo o njih objavljenih več zanimivih rezultatov. V [32] je dokazan obstoj 1-popolnih kod, v [14] je poleg drugih rezultatov izboljšan dokaz obstoja 1-popolnih kod. V tem članku avtorji vse točke grafa S(n,k), ki niso ekstremne, definirajo kot notranje točke. Kodo C v grafu S(n, k) imenujejo skoraj popolno, če točke iz C dominirajo vsem notranjim točkam. Popolna koda je po tej definiciji tudi skoraj popolna koda. Pokažejo, da vse različne skoraj popolne kode v grafu S(n,k), tvorijo particijo množice točk grafa S(n,k). S pomočjo te particije točk določijo ?-število grafa S(n, k), ki je taka minimalna vrednost ?, pri kateri lahko točkam grafa dodelimo oznake iz množice {0,1,..., ?} tako, da imata vsaki dve točki na razdalji dva različni oznaki, in vsaki dve sosednji točki oznaki z razliko najmanj dva. Takemu označevanju pravimo tudi L(2,1) označevanje. V [29] je bilo pokazano, da med poljubnima dvema točkama grafa Sierpińskega obstajata največ dve najkrajši poti. V [23] je podana formula, ki v grafu S(n, 3), ki je izomorfen grafu HL, za dano točko u pove število takih točk v, za katere obstajata natanko dve najkrajši u, v-poti. Formula je izražena z znanim Sternovim zaporedjem [81]. Izkaže se, da je le za točke stopnje dva (ekstremne točke), to število enako nič. Ta rezultat bi bilo zanimivo posplošiti na vse grafe S(n, k). Med mnogimi variacijami Hanojskih stolpov je zanimiva inačica z omejitvijo premikanja ploščic le na sosednje položaje, pri čemer je sosednjost položajev določena z vrstnim redom položajev. Določenemu položaju sta sosednja njemu naslednji in njemu predhodnji položaj. Če zadnjemu sledi prvi, pravimo, da smo jih razvrstili v cikel. Inačica z omejitvijo premikanja ploščic le na sosednje položaje, je bila prvič omenjena za Hanojske stolpe na treh položajih v [69]. Izkaže se za dokaj trivialen problem, vendar pa že na štirih položajih to ne velja več [76]. Guan je v [16] pokazal na povezavo med Grayevimi kodami in najkrajšimi potmi v tej inačici. Problem je seveda zanimivo posplošiti na poljubno število položajev. 88 POGLAVJE 6. ZAKLJUČEK Dodatek A Dekodiranje 1-popolnih kod v grafih Sierpińskega Spodnji izpis izvorne kode (programski jezik Java) je implementacija algoritma za dekodiranje, predstavljenega s psevdokodo in diagramom stanj na sliki 5.10. V komunikacijskem kanalu, shematično predstavljenem na sliki 5.1, tak program teče v sprejemni napravi, kot dekoder prihajajočih sporočil. Za vsako prejeto besedo, ki ni kodna točka, poišče njej najbližjo kodno točko. Uporaba je razvidna iz glavnega programa in ločimo dva primera. Pri sodem n je 1-popolna koda enolična, pri lihem n pa je potrebno opredeliti katera izmed ekstremnih točk je kodna točka. Niti podatka za n, niti za k programu izrecno ne podajamo, temveč n ugotovi iz dolžine oznake podane točke, podatka za k pa za izvedbo algoritma ne potrebujemo. Ob sodi dolžini oznake točke uporabimo klic new Vertex("1010").decode(); ob lihi dolžini pa je potrebno kot argument navesti še oznako ekstremne točke, ki jo določimo za kodno točko, new Vertex("21222").decode(’3’); Izpis izvorne kode: import java.io.*; import java.util.Arrays; public class Vertex { private String v; public Vertex(String vertex) { 89 90 DODATEK A. DEKODIRANJE v = vertex; System.out.print("Vertex "+v); } public void decode(char j) { // odd n System.out.print(" with perfect code vertex "+j); one_code(-1, j); } public void decode() { // even n all_codes(-1); } private void one_code(int r, char j) { if(v.length()-1 == r+1) { if(v.charAt(r+1) == j) System.out.println(" is a code vertex."); else System.out.println(" is not a code vertex, " + "its neighbour code vertex equals "+v.substring(0, v.length()-1)+j+"."); } else { if(v.charAt(r+1) == j) all_codes(r+1); else one_neighbour(r+1, j); } } private void all_neighbours(int r) { if(v.length()-1 == r+1) System.out.println(" is not a code vertex, " + "its neighbour code vertex equals "+outside()+"."); else one_neighbour(r+1, v.charAt(r+1)); } private void all_codes(int r) { one_code(r+1, v.charAt(r+1)); } private void one_neighbour(int r, char j) { if(v.charAt(r+1) == j) all_neighbours(r+1); else one_code(r+1, j); } private String outside() { int h = v.length()-1; char first = v.charAt(h); h--; 91 while(v.charAt(h) == first) h--; char[] equalChars = new char[v.length()-h-1]; Arrays.fill(equalChars, v.charAt(h)); return v.substring(0,h)+first+(new String(equalChars)); } public static void main(String[] args) { new Vertex("3333").decode(); new Vertex("1010").decode(); new Vertex("21222").decode(’3’); new Vertex("55555").decode(’5’); } } Rezultat izvedbe zgornjega programa: Vertex 3333 is a code vertex. Vertex 1010 is not a code vertex, its neighbour code vertex equals 1001. Vertex 20102 with perfect code vertex 0 is not a code vertex, its neighbour code vertex equals 20101. Vertex 21222 with perfect code vertex 3 is not a code vertex, its neighbour code vertex equals 21223. Vertex 55555 with perfect code vertex 5 is a code vertex. 92 DODATEK A. DEKODIRANJE Literatura [1] N. L. Biggs, Discrete Mathematics, Revised Edition, Oxford University Press, New York, 1989. [2] J. P. Bode, A. M. Hinz, Results and open problems on the Tower of Hanoi, in Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), Congr. Numer. 139 (1999) 113–122. [3] T. Chan, A statistical analysis of the Towers of Hanoi problem, Internat. J. Comput. Math. 28 (1988) 57–65. [4] F. B. Chedid, T. Mogi, A simple iterative algorithm for the Towers of Hanoi problem, IEEE Transactions on Education 39 (1996) 274–275. [5] P. Cull, I. Nelson, Error-correcting codes on the Towers of Hanoi graphs, Discrete Math. 208/209 (1999) 157–175. [6] P. Cull, I. Nelson, Perfect codes, NP-completeness, and Towers of Hanoi graphs, Bull. Inst. Combin. Appl. 26 (1999) 13–38. [7] R. Diestel, Graph Theory, Springer Verlag, New York, 1997. [8] H. E. Dudeney, The Canterbury Puzzles (and Other Curious Problems), E. P. Dutton, New York, 1908. [9] O. Dunkel, Editorial note concerning advanced problem 3918, Amer. Math. Monthly 48 (1941) 219. [10] A. S. Fraenkel, Combinatorial games: Selected bibliography with a succinct gourmet introduction, Electron. J. Combin. DS2 (2003) http://www.combinatorics.org/Surveys/. [11] J. S. Frame, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941) 216–217. 93 94 LITERATURA [12] M. Gardner, Martin Gardner’s Sixth Book of Mathematical Diversions from Scientific American, University of Chicago Press, 1984. [13] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Second Edition, Addison-Wesley, 1994. [14] S. Gravier, S. Klavžar, M. Mollard, Codes and L(2, 1)-labelings in Sierpiński graphs, Les cahiers du laboratoire Leibniz 70 (2002), sprejeto v objavo v Taiwanese J. Math. [15] F. Gray, Pulse code communication, U.S. Patent 2632058, March 17, 1953. [16] D. J. Guan, Generalized Gray codes with applications, Proc. Natl. Sci. Counc. ROC(A) 22 (1998) 841–848. [17] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998. [18] A. M. Hinz, An iterative algorithm for the Tower of Hanoi with four pegs, Computing 42 (1989) 133–140. [19] A. M. Hinz, The Tower of Hanoi, Enseign. Math. 35 (1989) 289–321. [20] A. M. Hinz, Shortest paths between regular states of the Tower of Hanoi, Inform. Sci. 63 (1992) 173–181. [21] A. M. Hinz, The Tower of Hanoi, Algebras and Combinatorics, Hong Kong, 1997, Springer, Singapore, 1999. [22] A. M. Hinz, Some open problems and new tasks in applied mathematics, in: J. C. Misra (Ed.), Applicable Mathematics, Its Perspectives and Challenges, Narosa, New Delhi, 2001, 545–554. [23] A. M. Hinz, S. Klavžar, U. Milutinović, D. Parisse, C. Petr, Metric properties of the Tower of Hanoi graphs and Stern’s diatomic sequence, sprejeto v objavo v European J. Combin. [24] A. M. Hinz, D. Parisse, On the planarity of Hanoi graphs, Exposition. Math. 21 (2002) 263–268. [25] A. M. Hinz, A. Schief, The average distance on the Sierpiński gasket, Probab. Theory Related Fields /bf 87 (1990) 129–138. [26] R. Holmes, Game graphs for Towers of Hanoi on 3 or more pegs, http://web.syr.edu/~rsholmes/games/hanoi/. LITERATURA 95 [27] M. Kaykobad, S. T. U. Rahman, R. A. Bakhtiar, A. A. K. Majumdar, A recursive algorithm for the multi-peg Tower of Hanoi problem, Internat. J. Comput. Math. 57 (1995) 67–73. [28] S. Klavžar, O teoriji kodiranja, linearnih kodah in slikah z Marsa, Obzornik Mat. Fiz. 45 (1998) 97–106. [29] S. Klavžar, U. Milutinović, Graphs S(n, k) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47 (122) (1997) 95–104. [30] S. Klavžar, U. Milutinović, Simple explicit formulas for the Frame-Stewart’s numbers, Ann. Combin. 6 (2002) 157–167. [31] S. Klavžar, U. Milutinović, C. Petr, Combinatorics of topmost discs of multi-peg Tower of Hanoi problem, Ars Combin. 59 (2001) 55–64. [32] S. Klavžar, U. Milutinović, C. Petr, 1-perfect codes in Sierpiński graphs, Bull. Austral. Math. Soc. 66 (2002) 369–384. [33] S. Klavžar, U. Milutinović, C. Petr, On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Appl. Math. 120 (2002) 141–157. [34] D. E. Knuth, All questions answered, Notices Amer. Math. Soc. 49 (3) (2001). [35] D. Kozen, The Design and Analysis of Algorithms, Springer Verlag, New York, 1991. [36] J. Kratochvíl, Perfect codes in general graphs, Rozpravy Československé Akad. Věd Řada Mat. Přírod. Věd, no. 7, 126 pp. Akademia Praha, 1991. [37] C. K. Li, I. Nelson, Perfect codes on the Towers of Hanoi graphs, Bull. Austral. Math. Soc. 57 (1998) 367–376. [38] J. H. van Lint, R. M. Wilson, A Course in Combinatorics, Cambridge University Press, Cambridge, 1992. [39] S. L. Lipscomb, A universal one-dimensional metric space, TOPO 72 - General topology and its applications, Second Pittsburgh Internat. Conf. Volume 378 of Lecture Notes in Math. Springer-Verlag, New York (1974) 248–257. [40] S. L. Lipscomb, On imbedding finite-dimensional metric spaces, Trans. Amer. Math. Soc. 211 (1975) 143–160. [41] X. M. Lu, Towers of Hanoi graphs, Internat. J. Comput. Math. 19 (1986) 23–38. 96 LITERATURA [42] X. M. Lu, T. S. Dillon, A Note on parallelism for the Towers of Hanoi, Math. Comput. Modelling 3 (1994) 1–6. [43] X. M. Lu, T. S. Dillon, Parallelism for multipeg Towers of Hanoi, Math. Comput. Modelling 3 (1995) 3–17. [44] X. M. Lu, T. S. Dillon, Nonrecursive solution to parallel multipeg Towers of Hanoi: A Decomposition Approach, Math. Comput. Modelling 3 (1996) 29–35. [45] W. F. Lunnon, The Reve’s puzzle, Comput. J. 29 (1986) 478. [46] A. A. K. Majumdar, Frame’s conjecture and the Tower of Hanoi problem with four pegs, Indian J. Math. 36 (3) (1994) 215–227. [47] A. A. K. Majumdar, The generalized four-peg Tower of Hanoi problem, Optimization 29 (1994) 349–360. [48] A. A. K. Majumdar, A note on the iterative algorithm for the Reve’s puzzle, Comput. J. 37 (1994) 463–464. [49] A. A. K. Majumdar, The divide-and-conquer approach to the generalized p-peg Tower of Hanoi problem, Optimization 34 (1995) 373–378. [50] A. A. K. Majumdar, The generalized p-peg Tower of Hanoi problem, Optimization 32 (1995) 175–183. [51] A. A. K. Majumdar, The bottleneck Tower of Hanoi problem with four pegs, Proc. Pakistan Acad. Sci. 33 (1996) 127–128. [52] A. A. K. Majumdar, Generalized multi-peg Tower of Hanoi problem, J. Austral. Math. Soc. Ser. B 38 (1996) 201–208. [53] M. Martelli, G. Gannon, Weighting coins: Divide and conquer to detect a counterfeit, College Math. J. 28 (1997) 365–367. [54] G. Matthes, Der Einsatz des ’Turm von Hanoi’-Computerprogramms zur Diagnostik von Störungen des problemlösenden Denkens bei Patienten mit er-worbenen Hirnschäden, Biomed. J. 19 (1988) 10–13. [55] U. Milutinović, Completeness of the Lipscomb space, Glas. Mat. Ser. III 47 (27) (1992) 343–364. [56] S. Minsker, The Towers of Hanoi rainbow problem: Coloring the rings, J. Algorithms 10 (1989) 1–19. LITERATURA 97 [57] S. Minsker, The Towers of Antwerpen problem, Inform. Process. Lett. 38 (1991) 107–111. [58] C. Petr, Posplošeni Hanojski stolp, Presek 22 (1994/1995) 10–16. [59] C. Petr, Posplošitve klasičnega problema Hanojskih stolpov, magistrsko delo, Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko, Maribor, 1998. [60] C. Petr, Édouard Lucas (1842-1891), Presek 34 (2003/2004) 46–50. [61] H. de Parville, La Tour d’Hanoi et la question du Tonkin, La Nature 12 (1884) 285-286. [62] D. G. Poole, The Bottleneck Towers of Hanoi problem, J. Recreat. Math. 24 (1992) 203–207. [63] D. G. Poole, The towers and triangles of professor Claus (or Pascal knows Hanoi), Math. Mag. 67 (1994) 323–344. [64] J. S. Rohl, T. D. Gedeon, Four-Tower Hanoi and beyond, Austral. Comput. Sci. Comm. 5 (1983) 156–162. [65] D. Romik, Shortest paths in the Tower of Hanoi graph and finite automata, arXiv:math.CO/0310109 v1 8.10.2003, http://arxiv.org/abs/math.CO/0310109/. [66] A. Sapir, The Tower of Hanoi with forbidden moves, Comput. J. 47 (1) (2004) 20–24. [67] U. K. Sarkar, On the design of a constructive algorithm to solve the multi-peg Towers of Hanoi problem, Theoret. Comput. Sci. 237 (1/2) (2000) 407–421. [68] U. K. Sarkar, On the uniqueness of solution to the multi-peg Towers of Hanoi, Internat. J. Comput. Math. 78 (1) (2001) 57–72. [69] R. S. Scorer, P. M. Grundy, C. A. B. Smith, Some binary games, Math. Gaz. 280 (1944) 96–103. [70] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/~njas/sequences/, 1996-2004. [71] B. M. Stewart, Advanced problem 3918, Amer. Math. Monthly 46 (1939) 363. [72] B. M. Stewart, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941) 217–219. 98 LITERATURA [73] I. Stewart, Le lion, le lama et la laiture, Pour la Science 142 (1989) 102–107. [74] I. Stewart, Four encounters with Sierpiński’s gasket, Math. Intelligencer 17 (1995) 52–64. [75] P. K. Stockmeyer, internetna stran, http://www.cs.wm.edu/~pkstoc/. [76] P. K. Stockmeyer, Variations on the four-post Tower of Hanoi puzzle, Congr. Numer. 102 (1994) 3–12. [77] P. K. Stockmeyer, The Tower of Hanoi: a historical survey and bibliography, rokopis, september 1997. [78] P. K. Stockmeyer, The average distance between nodes in the Tower of Hanoi digraph, Graph Theory, Combinatorics, Algorithms and Applications Vol. II 1999, 799–808. [79] P. K. Stockmeyer, C. D. Bateman, J. W. Clark, C. R. Eyster, M. T. Harrison, N. L. Loehr, P. J. Rodriguez, J. R. Simmons III, Exchanging disks in the Tower of Hanoi, Internat. J. Comput. Math. 59 (1995) 37–47. [80] M. Szegedy, In how many steps the k peg version of the Towers of Hanoi game can be solved?, in STACS 99 (Trier), Lecture Notes in Comput. Sci. 1563, Springer, Berlin (1999) 356–361. [81] I. Urbiha, Some properties of a function studied by De Rham, Carlitz and Dijkstra and its relation to the (Eisenstein–)Stern’s diatomic sequence, Math. Commun. 6 (2002) 181–198. [82] D. Wood, The Towers of Brahma and Hanoi revisited, J. Recreat. Math. 14 (1981-82) 17–24. [83] J. S. Wu, R. J. Chen, The Towers of Hanoi problem with parallel moves, Inform. Process. Lett. 44 (1992) 241–243. [84] J. S. Wu, R. J. Chen, The Towers of Hanoi problem with cyclic parallel moves, Inform. Process. Lett. 46 (1993) 1–6. Slike 1.1 Klasični Hanojski stolpi ........................ 1 1.2 Pokrov škatle z igrico Hanojski stolpi................. 2 1.3 Shematično predstavljeni klasični Hanojski stolpi .......... 3 1.4 Shematično predstavljeni posplošeni Hanojski stolpi......... 4 2.2 Popolno stanje ............................. 11 2.3 Razgrnjeno stanje............................ 11 2.4 Delno razgrnjeno stanje......................... 11 2.5 Dve različni stanji z enakim opisom vrhnjih ploščic......... 12 2.6 Grafi funkcije ?p(k)........................... 23 3.1 Grafi H2, H2 in H2........................... 29 3.2 Konstrukcija grafa H% s p podgrafi H™~1............... 30 3.3 Konstrukcija grafa H% s p2 podgrafi H™~2 .............. 30 3.4 Podgraf H2 izomorfen H2 , ki ni podgraf prvega tipa ........ 32 3.5 Podgrafi H2 izomorfni H2....................... 33 3.6 Podgrafi H2 izomorfni H2....................... 34 3.7 Podgrafi H2 izomorfni H2 (prvi del).................. 35 3.8 Podgrafi H2 izomorfni H2 (drugi del)................. 36 3.9 Štirje disjunktni podgrafi H2 izomorfni grafu H1 .......... 37 3.10 Prestavitev ploščice n - i........................ 43 4.1 Prestavljanje ploščic po Framovem algoritmu ............ 48 4.2 Prestavljanje ploščic po Stewartovem algoritmu........... 49 5.1 Prenašanje sporočil s kodiranjem in dekodiranjem.......... 61 5.2 Vizualizacija relacije ~......................... 63 5.3 Dovoljena poteza Hanojskih stolpov z zamenjavami......... 64 5.4 Graf Sierpiflskega S(2,4)........................ 64 5.5 Grafa Hf in S(3, 3)........................... 65 5.6 Možne relacije S(n,k;i1, i2,..., ir) za določen C........... 67 99 100 SLIKE 5.7 Primeri podgrafov v S(4,3) ...................... 70 5.8 Struktura S(n, k; i1, i2, . . . , ir) ko je m = n - r sod .......... 72 5.9 Struktura S(n, k; i1, i2, . . . , ir) ko je m = n - r lih .......... 73 5.10 Diagram prehajanja stanj ....................... 78 5.11 Konstrukcija 1-popolne kode v grafih S(n,3) ............. 79 5.12 Konstrukcija 1-popolne kode v grafih S(n,4) ............. 80 5.13 Zaprte soseščine kodnih točk v grafih S(n,4) ............. 81 5.14 Zaprte soseščine kodnih točk v grafih S(n,5) (prvi del) ....... 82 5.15 Zaprte soseščine kodnih točk v grafih S(n,5) (drugi del) ...... 83 6.1 Grafa T33 in T34 ............................. 86 Stvarno in imensko kazalo 1-popolna koda, 62 algoritem Framov, 46 Stewartov, 47 Bode J. P., 85 Chan T., 86 Cull P., 65 dominantna množica, 62 dominantno število grafa, 62, 76, 77 Dudeney H. E., 5 Dunkel O., 5 Fraenkel A. S., 2 Frame J. S., 5, 48 graf, 25 polni, 26 Sierpińskega, 63 graf stanj Hanojskih stolpov z zamenjavami, 64 posplošenih Hanojskih stolpov, 27 vrhnjih ploščic, 86 Grayevo kodiranje, 5 Guan D. J., 87 Hamiltonov obhod, 5 Hammingova razdalja, Hanojski stolpi, 2 klasični, 3 posplošeni, 4 62 z zamenjavami, 64 Hinz A. M., 1, 3, 6, 59, 85, 86 Klavžar S., 61, 63, 85 Knuth D. E., 6 Kratochvíl J., 61 Li C. K., 65 Lucas E., 2 Majumdar A. A. K., 6 Milutinović U., 63, 85 Nelson I., 65 padajoča fakulteta, 13 Pascalov trikotnik, 5 podgraf, 26 inducirani, 26 vpeti, 26 Poole D. G., 6 preslikava avtomorfizem, 26 izomorfizem, 26 princip bližnjega soseda, 62 problem ponarejenega kovanca, 41 prva lema teorije grafov, 26 Romik D., 86 Schief A., 86 soseščina, 25, 66 zaprta, 25, 62, 68, 79 stanje, 10 delno razgrnjeno, 10 101 102 STVARNO IN IMENSKO KAZALO neregularno, 10 popolno, 10 razgrnjeno, 10 regularno, 10 Stewart B. M., 5, 49 Stewart I., 86 Stirlingovo število druge vrste, 16, 38 Stockmeyer P. K., 2 stopnja točke, 25 maksimalna, 26 minimalna, 26 povprečna, 26 Szegedy M., 85 trikotna krivulja Sierpińskega, 5, 63, 86 trikotniška števila, 5, 42 Wood D., 4