MathematicalAssoc.ofAmerica AmericanMathematicalMonthly121:1 January19,2016 1:57a.m. monthly-Hanoi.tex page1 Self Similarities of the Tower of Hanoi Graphs and a proof of the Frame-Stewart Conjecture Janez Zˇerovnik University of Ljubljana,FME, Asˇkercˇeva 6 6 1 and 0 IMFM, Jadranska 19, SI-1000 Ljubljana,Slovenia 2 [email protected];[email protected] n a J 7 Abstract.Consideringthesymmetriesandselfsimilaritypropertiesofthecorrespondingla- 1 beledgraphs,itisshownthattheminimalnumberofmovesintheTowerofHanoigamewith p=4pegsandn≥pdiskssatisfiestherecursiveformulaF(p,n)=min1≤i≤n−1{2F(p,i)+ ] F(p−1,n−i)}whichprovesthestrongFrame-Stewartconjectureforthecasep=4.The O methodcanbegeneralizedtop>4. C h. 1. INTRODUCTION. TheTowerofHanoigamewithp ≥ 3pegsandn ≥ 0disks t isapopulargameinwhichdiskshavetobemovedfromonetoanotherpeg,obeying a m the rule thata largerdisk can neverbe putonto a smallerone [3]. The case p = 4 is sometimescalledReve’spuzzle.Itis usualto studythe gameby regardingthe graph [ ofpossiblepositionsandlegalmovesamongthem.Themostprominentopenproblem 1 is the Frame-Stewart conjecture about the minimality of a certain algorithm for the v distancebetweensocalledperfectstates.TheknownsolutiontotheProblem3918[5] 8 thathasbeenreinventedseveraltimes(see[3]forhistoricalfacts)appearstobeavery 9 naturalone,butthe proofofoptimality in generalcaseis notknownuntiltoday.The 2 4 two solutions proposed by Frame and Stewart [2, 6] are known to be equivalent [4] 0 andthenumberofstepsneededforp pegsandn ≥ p disks is givenby therecursive 1. formula 0 6 F(p,n) = min {2F(p,i)+F(p−1,n−i)}. (1) 1 1≤i≤n−1 : v AsitistrivialthatF(p,n) = 2n−1forn < p,anditiswell-knownthatF(3,n) = i X 2n−1,formula(1)determinesF(p,n)forallp ≥ 3andn ≥ 0.Theliteratureonthe r topicisenormous,forexamplethereare352referencesin[3].Very recently,a proof a ofoptimalityforthecasep = 4appearedin[1]. Herewefirst observesomeselfsimilarity propertiesofthelabeledgraphsthatare isomorphic to Hanoi graphs. The symmetries can rather naturally be observed from drawings that, to our surprise, are used very rarely. In fact, in an attempt to Google searchfordrawingsofHanoigraphs,thepresentauthorfoundasimilardrawinginonly onepaper[7],whichseemstobeunpublishedstudents’homework(!).Thestructureof theHanoigraphsallowstoprovealemmaaboutexistenceofshortestpathsofcertain structure that in turn provides a proof that the Frame-Stewart algorithm is optimal. ThissolvesthefamousFrame-Stewartconjecture. Therulesofthegamearesimple.Thereareppegsandndisks,thatalldifferinsize (diameter).In the beginning,all the disks are atone peg,(legally)orderedbysize. It isnotallowedtoputalargerdiskontoasmalleroneatanytime.Inonemove,adisk January2014] TOWEROFHANOIANDFRAME-STEWARTCONJECTURE 1 MathematicalAssoc.ofAmerica AmericanMathematicalMonthly121:1 January19,2016 1:57a.m. monthly-Hanoi.tex page2 thatisonthetopatonepegisputtothetopatanotherpeg.Thetaskistoreachastate inwhichallthedisksfromoriginalpegareatanotherpegsothatthenumberofmoves isminimal. Only basic notions of graph theory will be used. A graph is a pair of sets G = (V(G),E(G)), whereV(G)isanarbitrarysetofvertices,andE(G)isasetofpairs of vertices. Usual notation is e = uv meaning that edge e connects vertices u and v. We work with labeled graphs, i.e. graphs with a labeling function that assigns a labeltoeachvertex.Two(unlabeled)graphsGandH areisomorphicwhenthereisa bijection (called isomorphism)α : V(G) → V(H) such that u and v are connected inGifandonlyifα(u)andα(v)areconnectedinH.Awalkisasequenceofvertices andedgesv e v e v ...e v suchthate = v v .Awalkisalsodeterminedeither 0 1 1 2 2 k k i i−1 i by the sequence of vertices v v v ...v or by the sequence of edges e e ...e . The 0 1 2 k 1 2 k lengthofawalkisthenumberofedgesonit.Apathisawalkinwhichallverticesare distinct.Thedistancebetweentwoverticesisthelengthofashortestpath.Asubgraph H ofagraphGisisometricsubgraph,ifthedistancebetweenanytwoverticesinH isequaltothedistanceinG.Fornotionsnotrecalledheresee,forexample[8]. The rest of the paper is organized as follows. In the next section, we construct labeled graphs G(p) corresponding to the Tower of Hanoi game with p pegs and n n disks. In Section 3, a lemma about the self similarity of these graphs is proved and some related facts are given. Sections 4 and 5 provide proof of existence of shortest pathsofcertainformwhichinturngivesalowerboundonlengthoftheshortestpaths between certain vertices. This implies the main result, a proof of the Frame-Stewart conjectureforfourpegsthatappearsinSection6. 2. THE CONSTRUCTION OF LABELED GRAPHS G(P). Before giving the N general definition, we start with the p = 4 pegs example. Labels of the graphs G(4) n willbewordsoflengthnoverthefourletteralphabetA = {A,B,C,D}. 4 Let G(4) be the tetrahedrongraph(completegraphon4 vertices),andthe vertices 1 labeledwithA,B,C,andD. Given G(4), we construct G(4) as follows. Take four copies of G(4): in the first n n+1 n copy,denotedbyAG(4) replaceeachlabel∗withlabelA∗(i.e.addanAatthebegin- n ningofeachlabel).Similarly,inBG(4) replaceeachlabel∗withlabelB∗,inCG(4) n n replaceeachlabel∗withlabelC∗,andinDG(4) replaceeachlabel∗withlabelD∗. n Finally connect some pairs of vertices from different copies of G(4) with edges n by the following rule. Let X,Y ∈ A , X 6= Y. Two vertices u ∈ V(XG(4)) and 4 n v ∈ V(YG(4))areconnectedifandonlyifthelabelsofuandvwithoutthefirstletter n are equaland are words overA −{X,Y}. (i.e. the labels do notcontain anyX or 4 Y).ThegraphsG(4) andG(4) aredrawnonFig.1andthegraphG(4) isonFig.2. 1 2 3 Inotherwords,fromthedefinitionitfollowsthattwoverticesfromdifferentcopies ofG(4)areconnectedinG(4) exactlywhentheirlabelsareequal(inthelastnletters) n n+1 andthelabelsarewordsoveranalphabetoftwoletters. Remark. The graphG(4) is isomorphicto the Hanoigraphofthe gamewith 4 pegs n andndisks.Justinterpretthelabelsnaturallyas:i-thletterinthelabelistheposition ofthei-thdisk.Forexample,thefirstlettergivesthepositionofthelargestdisk. We nowturnto generaldefinition,forarbitraryp ≥ 3. A generalizationto G(p) is n straightforward: Definition. LetG(p) beacompletegraphwithpdistinctlabelsonvertices,sayusing 1 lettersfromalphabetA .ConstructG(p) usingpcopiesofG(p) asabove,i.e.ineach p n+1 n copyofG(p)useadifferentletterasaprefixforlabels.Asbefore,connecttwovertices n 2 (cid:13)c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly121 MathematicalAssoc.ofAmerica AmericanMathematicalMonthly121:1 January19,2016 1:57a.m. monthly-Hanoi.tex page3 DD DC DA DB CD D CC AD CA CB C AC AA BD AB BC A B (a) (b) BA BB Figure1. ThegraphsG(4)andG(4). 1 2 u ∈ V(XG(p)) and v ∈ V(YG(p)) if and only if the labels of u and v without the n n firstletterareequalandarewordsoverA −{X,Y}(i.e.thelabelsdonotcontain p anyX orY). Remark. By construction, the graph G(p) is the graph of the Tower of Hanoi game n withk pegsandndisks.(Asunlabeledgraph,itisthereforeisomorphictotheHanoi graph, Hp in notation of [3].) The Frame-Stewart conjecture says that the minimal n numberofmovesbetweentwo perfectstates is determinedby recursion(1) whichis equivalentto statement that this is the length of a shortest path in G(p) between two n perfectvertices,forexampleverticeswithlabelsAn = AA...AandBn = BB...B. 3. SELFSIMILARITY. ItiswellknownthattheHanoigraphsarehighlysymmet- ric. Here we first emphasizeoneof the propertiesthat motivatedthe idea usedin the argumentgivenbelow.Somemorepropertiesarelisted belowforlaterreference.We donotgivedetailedproofsaswebelievethattheseresultsarenotnew,andarerecalled hereforcompletenessofpresentation. GivenG(p) and1 ≤ i ≤ ndefinetheequivalencerelationR onthesetofvertices n i V(G(p))asfollows:twoverticesareequivalentwhentheirlabelscoincideinthefirst n n−i letters. Define the graph G(p)/R on equivalence classes (as vertices) by con- n i nectingtwoequivalenceclassesifthereisanedgeG(p)thatconnectsapairofvertices n fromthetwoclasses.Thedefinitiondirectlyimplies: Lemma1. G(p)/R isisomorphictoG(p) . n i n−i Having in mind this structure, we will (for fixed i) make a distinction between the edges within equivalenceclasses and the edges connectingdifferent classes. The later will be called bridges and the edges within equivalenceclasses will be referred to as local edges. Thus bridges correspond to moves of the largest n−i disks and localedgestomovesofthesmallestidisks.(SeeFig.2andFig.3,wherethebridges betweenclassesA**andC**inG(4) areshown.) 3 By definition ofR , eachequivalenceclass of R induces a subgraphofG(p) that i i n isisomorphictoG(p).Furthermore,recallthatanybridgeconnectstwovertices(from i January2014] TOWEROFHANOIANDFRAME-STEWARTCONJECTURE 3 MathematicalAssoc.ofAmerica AmericanMathematicalMonthly121:1 January19,2016 1:57a.m. monthly-Hanoi.tex page4 DD D** DC DA DB CD CC AD CB BD AA AC BC AB DD BA BB DC DA DB CD CC AD DD BDCA CB DC AA AC BC C** DA DB CD AB BA BB CC AD CA CB DD BD AA ABAC BC DA DBDC CD A** BA BB CC AD CA CB BD AA ABAC BC B** BA BB Figure2. ThegraphG(4);withthefourequivalenceclasses(i=1). 3 DD D** DC DA DB CD CC AD CB BD AC AA BC AB DD BA BB DC DA DB CD CC AD DD BDCA CB AC DC AA BC C** DA DB CD AB BA BB CC AD CA CB DD BD AC DC AA AB BC DA DB CD A** BA BB CC AD CA CB BD AC AA BC AB B** BA BB Figure3. Thefourequivalenceclasses(i=1)ofthegraphG(4)andalledges(bridges)betweentwoclasses. 3 different equivalenceclasses) with the same labels (i.e. with labels that match in the lastiletters). Westatetwomorepropertiesforalaterreference.Theproofsfollowdirectlyfrom thedefinitions.Maybeevenmorenaturalargumentistoconsiderthemeaninginterms ofthegame,namely(1)fixingpositionsofthelargestn−idisksclearlyresultsina game with i disks and (2) putting the smallest i disks to one of the pegs forbids the 4 (cid:13)c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly121 MathematicalAssoc.ofAmerica AmericanMathematicalMonthly121:1 January19,2016 1:57a.m. monthly-Hanoi.tex page5 movesto that peg,henceexactlyp−1 pegsare free to movethe largest n−i disks at. Lemma2. LetW beaarbitrarywordofn−ilettersoveralphabetA .ThenWG(p) p i areisometricsubgraphsofG(p). n Lemma 3. The vertices WG(p) of G(p)/R where W is an arbitrary word of n−i i n i lettersoveralphabetA −X induceasubgraphthatisisomorphictoG(p−1). p n−i We concludethe section with a coupleoffacts thatwill be usefullater. As above, theproofsarenotdifficult,forexamplebyconsideringthemeaningofthedistancesin termsofthegame.Inshort,thefirstclaimfollowsbyobvioussymmetry(justreplace theroleofAandB).Thesecondclaimisobviousbecauseifwecansolvethebigger task,thenwealsocansolvetheeasiertask(andneednotmovethelargestdisk).Details arelefttothereader. Fact 1. Let A and B be arbitrary letters from alphabet A . Let W be a word of i p lettersoveralphabetA −{A,B}.ThenthedistancebetweenverticeswithlabelsAi p andW isequaltothedistancebetweenverticeswithlabelsBi andW.Hence,there isnoshortestpathconnectingverticeswithlabelsAi andW thatmeetsBi inGp. i Fact2. LetW beawordofilettersoveralphabetA −{A}.ThenthereexistsC 6= p A such that the distance between vertices with labels Ci and W is strictly smaller thanthedistancebetweenverticeswithlabelsAi andW. Remark. Idea of proof of Fact 2 : On any path P from W (i.e. vertex with label W) to Ai, the largest disk will be moved to peg A, so the path P can be written as W → W∗ → AW∗∗ → Ai,whereW∗ andAW∗∗ aretwo labelsthatdifferonlyin thefirstletter.LetthefirstletterofW∗ beC.ThenthereisapathP∗ fromW toCi, i.e.W → W∗ = CW∗∗ → Ci,andP∗ isshorterthanP. 4. SHORTESTPATHS. Letn≥ 2,asthecasen = 1istrivial.LetA beanalpha- p betofpletters,andA,B ∈A . p Let P be a shortest path from vertex a with label An to vertex b with label Bn. Below, in Proposition 1 we will assume that on the path P there is a vertex that has a labelof the form An−iXi, where X ∈ A −{A,B} (i.e. X is not A nor B). We p callsuchavertexspecial.Itmayseemobviousthatthereisaspecialvertexonevery shortestpath from a and b. However,this is notthe case as pointed outby Ciril Petr andSandiKlavzˇar.Aslightlyweaker,butstillsufficient,statementcanbeproved Lemma4. Letp = 4.Thereisashortestpathwithatleastonespecialvertexonevery pathbetweenverticesaandbwithlabelsAn andBn. The proofof Lemma is postponedto the next section. It is based on induction, in whichthe small cases are,due to large numberofthem, rathertedioustask. Alterna- tively,itcanbecheckedbycomputerusingastraightforwardapplicationofashortest pathalgorithm.Webelievethatthesametechniquecanbeusedforp > 5andconjec- ture Conjecture1. Thereisashortestpathwithatleastonespecialvertexoneverypath betweenverticesaandbwithlabelsAn andBn. Nowwewillshowthatthereisashortestpathwithcertainstructure.Moreprecisely, January2014] TOWEROFHANOIANDFRAME-STEWARTCONJECTURE 5 MathematicalAssoc.ofAmerica AmericanMathematicalMonthly121:1 January19,2016 1:57a.m. monthly-Hanoi.tex page6 Proposition 1. Let P be a shortestpath connectingvertices a and b with labels An and Bn and let 1 ≤ i ≤ n. If there is a special vertex on P with label of the form An−iXi, where X ∈ A −{A,B} then there is a shortest path Q from a to b in p G(p), which is a concatenation of three subpaths Q , Q , Q such that Q and Q n 1 2 3 1 3 onlyuselocaledgesandQ onlyusesbridges. 2 Proof. Considera shortestpathP froma to b (verticeswith labels An andBn). Let i = i(P) be maximalwith propertythatthereis a specialvertexs = s(i) with label An−iXi onthepathP. DenotebyP thefirst partofP, froma tos,andobservethatbecauseofLemma 1 2wecan,withoutlossofgenerality,assumethatthereareonlylocaledgesonP .As 1 P isashortestpath,Q = P mustbeashortestpathfromatoswithinthesubgraph 1 1 An−iG(p). i On path P there must be at least one bridge after P meets s because labels An andBn differin the firstn−i ≥ 1letters thatcanonlybechangedwhentraversing bridges.Firstweshowthatthereisashortestpathsuchthattheedgeusedaftervisiting sisabridge: Claim 1. Let P be a shortest path from a to b (with labels An and Bn) that meets vertex s = s(i) with label An−iXi, i = i(P). Then there is a path P′ of the same lengthsuchthatthefirstedgeaftervisitingsisabridge. Proof (of the Claim). If P has the property claimed then P′ = P and we are done. Now assume that P = P P fP where P is a shortest path from a to s, P is a 1 2 3 1 2 subpathoflocaledgesfromstow,f isabridge,andP istherestofP. 3 Wedistinguishtwocases.First,letwbeavertexwithlabelAn−iW whereW isa wordusingletterX.Thisimpliesthatf isabridgethatmovesadiskfrompegAtoa pegthatisnotpegX,sayf movesn−i-thdiskfromAtoY 6= X.Thisimpliesthat wecanreplacesubpathP f withf′P′,wheref′istheedgeconnectingvertexs(with 2 2 labelAn−iXi)andvertexs′ thathaslabelAn−i−1YXi andP′ isacopyofP inthe 2 2 subgraphAn−i−1YG(p). (Formally, the path P′ is constructedfrom P by replacing i 2 2 everyvertexonP (withlabelAn−i∗)withthevertexwithlabelAn−i−1Y∗.) 2 NowassumethatwisavertexwithlabelAn−iW whereW isawordwithoutletter X.InthiscasethesubpathP P (withinAn−iG(p))startsata(withlabelAn),visits 1 2 i firstvertexwithlabelAn−iXi andthenreachesw.However,thereisastrictlyshorter path from a to w which contradicts the assumption that P is a shortest path (recall Fact1). (Claim) Now we will prove that there is no need to use local edges between bridges, i.e. thatthereisashortestpathwhich,aftervisitings,firsttraversesallbridges,andthen traverses only local edges. The next claim shows that we can always conveniently changepositionofthenextdisplacedbridge.Moreprecisely, Claim2. LetP beashortestpathoftheformP = P P LfP ,whereP isashortest 1 2 3 1 pathfrom ato s,P is apathofbridgesfroms tot, Lis alocalpath,f isa bridge, 2 andP is therestofP.ThenthereisshortestpathP′ = P P f′L′P , wheref′ is a 3 1 2 3 bridgeandL′ isalocalpathofthesamelengthasL. Proof(oftheClaim).ThelocalpathLisapathfromvertexttoavertex,sayw.Let thelabeloftbeZXi whereZ isawordoflengthn−ithatdoesnotcontainanyX. ThenthelabelofwmustbeoftheformZW. Wedistinguishtwocases.First,assumethewordW containsatleastoneletterX. Thereforebridgef thatmovesoneofthe largedisksmaynotmovea diskto pegX. (Moreprecisely,edgef connectswandu,andthelabelofumustbeZ′W,wherethe 6 (cid:13)c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly121 MathematicalAssoc.ofAmerica AmericanMathematicalMonthly121:1 January19,2016 1:57a.m. monthly-Hanoi.tex page7 wordsZ′ andZ differinoneletteratoneposition,andneitherZ′ norZ containany letterX.) Hence we can define f′ to be the bridgethat connectst (with labelZXi)and the vertexwithlabelZ′Xi,denoteitr.Furthermore,letL′ beacopyofLinZ′G(p) that i connectsvertices r and u. By construction,paths f′L′ and Lf both connectt and u andareofthesamelength,asneeded. Now assume that w is a vertex with label ZW where W is a word without letter X. In this case, we can construct a shorter path from a to w, which contradicts the assumptionthatP isashortestpath.Theargumentisasfollows. First,observethat,becausethereisnoX inW,thefirstletterofW isY 6= X.(In otherwords,thei-thsmallestdiskisonpegY thatisnotpegX.) Second, by symmetry, existence of the path P (connecting vertices with labels 2 An−iXi andZXi)impliestheexistenceofapathP′ ofthesamelengththatconnects 2 verticeswithlabelsAn−iYi andZYi.(JustreplaceanyoccurenceofY inP withX 2 (andviceversa)togetP′.) 2 Furthermore,bysymmetry,thereisapathP′(ofthesamelengthasP thatconnects 1 1 vertexaandthevertexwithlabelAn−iYi. Finally, recalling Fact 2, in ZGp there is a path L′ from the vertex with label i ZYYi−1 tovertexwthatisstrictlyshorterthanL. Summarizing, the path P′P′L′ from a to w is shorter than P P L, contradicting 1 2 1 2 theminimalityofP. (Claim) ByinductiveapplicationofthelastClaimweprovethatanyshortestpathP canbe replacedbyashortestpathQ = Q Q Q whereQ isapathofbridgeswhileQ and 1 2 3 2 1 Q arepathoflocaledges. 3 5. SPECIAL VERTICES - PARTIAL PROOF OF CONJECTURE ??. In this section we will prove Lemma 4. The proof is by induction. We emphasize that the inductivestepisprovedforgeneralpwhileweareonlyabletoprovethebasestep(s) foreachpseparately. Webeginbyintroducingsomemorenotation.InthegraphG(p) ,weconsidershort- n+1 est paths from a to the set of vertices on the border of AG(p), i.e. to vertices from n which there are edges going out to other subgraphs XG(p), X 6= A. The border S n n is,bydefinitionofG(p) ,aunionofSAX,whereSAX isasetofverticeswithlabels n+1 n n thatdonotuselettersAandX :Sn = [ SnAX.AsAG(np) isjustacopyofG(np) X∈A−A we can recursively define S in G(p), and because AG(p) is a subgraph of G(p) , n−1 n n n+1 this also givesa definition ofS in G(p) . Thus we define the sets S in G(p) for n−1 n+1 i n+1 i= 1,2,...,n(seeFigure4).Obviously, Fact3. Anyshortestpathfromatov ∈ S meetsS . n n−1 Asalreadymentioned,thereareexamples,inwhichthereisauniqueshortestpath fromatosomeverticesontheborder.Weconjecturethatthisisonlypossibleforsmall n. Conjecture 2. For any p ≥ 3 there is n ≥ 2 such that for any v ∈ S there is a 0 n0 shortestpathfromatov thatmeetsaspecialvertex. For p = 4, the validity of conjecture can be proved by regarding S in the graph 6 G(4). In fact the presentauthor performed a tedious case analysis ”by hand” using a 7 tool for drawing shortest paths in Hanoi graphs by Igor Pesek. As a curiosity, let us January2014] TOWEROFHANOIANDFRAME-STEWARTCONJECTURE 7 MathematicalAssoc.ofAmerica AmericanMathematicalMonthly121:1 January19,2016 1:57a.m. monthly-Hanoi.tex page8 a Figure4. SubgraphAn−3G(34)withemphasizedvertexsetsS2inS3.Edgescorrespondingtothemovesof the3rddiskarenotdrawn. mentionthattheonlyverticesontheboundaryS thathaveauniqueshortestpathtoa 5 arethesixverticeswithlabelsA...ACCDCD,A...ADDCDC,(and,bysymmetry, A...ACCBCB, A...ABBCBC, A...ABBDBD, A...ADDBDB), two of them passingthevertexwithlabelA...AAAAAB.OnS ,thereisnovertexwithaunique 6 shortestpathtovertexa,andinparticular,ineachcaseatleastoneofthepathsavoids vertexwithlabelA...AAAAAB. Wethusknowthat Fact 4. For any v ∈ S in the graph G(4), there is a shortest path from a to v that 6 7 meetsaspecialvertex. Hence, by induction step (Fact 3), for any v ∈ S in the graph G(4) there is a n n+1 shortestpathfromatov thatmeetsaspecialvertex,foranyn ≥ 7. Recall that any shortest path between a and b (with labels An and Bn) in G(p) n meets S , more precisely SAB. Provided validity of Conjecture 2 (that is proved n−1 n−1 aboveforcasep = 4),wehavetheexistenceofashortestpathbetweenaandb(with labelsAn andBn)thatmeetsaspecialvertex.Furthermore,forp = 4andn < 7itis straightforwardto constructshortestpaths that meeta specialvertex. This concludes theproofofLemma4. Remark. Clearly, the cases p > 4 can be handled along the same lines. The size of graphshoweverisprobablytoolargetocheckwithoutcomputerassistance. 6. THEMAINRESULT. Proposition1impliesthatthereisashortestpathbetween verticesaandb(withlabelsAnandBn)inwhichbridgesareallsandwichedtogether betweentwolocalpaths.Hence,itsufficestoconsiderthepathsofthisform. Lemma5. AssumevalidityofConjecture1.LetP beapathconnectingverticeswith labels An and Bn, and with a special vertex on P with label of the form An−iXi, whereX ∈ A−{A,B}.AssumeP isaconcatenationofthreesubpathsP ,P ,and 1 2 8 (cid:13)c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly121 MathematicalAssoc.ofAmerica AmericanMathematicalMonthly121:1 January19,2016 1:57a.m. monthly-Hanoi.tex page9 P suchthatP andP onlyuselocaledgesandP onlyusesbridges.Thenthelength 3 1 3 2 ofP isF(p,i)+F(p−1,n−i)+F(p,i). Proof. LetthespecialvertexsonP beoftheformAn−iXi.Thenthelastilettersof labels ofall the verticeson P are Xi, which implies that P nevermeets the copies 2 2 WG(p) where X appears in the word W. Recall that by Lemma 3, the subgraph in- i ducedonverticesWG(p) whereW isawordoflengthn−ioveralphabetA −X n−i p isisomorphictoG(p−1). n−i ThelengthsofsubpathsP ,P ,P arethusboundedbyF(p,i),F(p−1,n−i), 1 2 3 andF(p,i),respectively.HencethestatementoftheLemmafollows. Theorem1. AssumevalidityofConjecture1. Thedistancebetweenverticeswith la- belsAn andBninG(p) ismin {2F(p,i)+F(p−1,n−i)}. n 1≤i≤n Proof. Consider a shortest path P between vertices with labels An and Bn. There must be a special vertex on P, and, by Lemma 1, a shortest path Q for which the length is given by Lemma 5. Recall [4, 3] that there are algorithms for which the numberof movesis given by Eq. (1). Thereforethe length of a shortestpath P is of thefrom2F(p,i(P))+F(p−1,n−i(P)),asclaimed. Theorem1andLemma4impliy Theorem2. ThestrongFrame-Stewartconjectureistrueforp = 4. Recall that for any p, validity of Conjecture 1 implies the strong Frame-Stewart conjectureforthatp. ACKNOWLEDGMENT. TheauthorwishestothankIgorPesekforprovidingatoolfordrawingshortest pathsinHanoigraphs,andtoSandiKlavzˇarandCirilPetrforusefulcommentsonanearlierversionofthis paper.TheworkwasinpartsupportedbyARRS. REFERENCES 1. T.Bousch,LaquatriemetourdeHanoi, Bull.Belg.Math.Soc.SimonStevin21(2014)895-912. 2. J.S.Frame,ProblemsandSolutions:AdvancedProblems:Solutions:3918,TheAmericanMathematical Monthly48(1941)216-217. 3. A.M.Hinz,S.Klavzˇar,U.Milutinovic´,C.Petr, TheTowerofHanoi-MythsandMaths,Springer,Basel, 2013. 4. S.Klavzˇar,U.Milutinovic´,C.Petr,OntheFrame-Stewartalgorithmforthemulti-pegTowerofHanoi problem,DiscreteAppliedMathematics120(2002)1141-157. 5. B.M.Stewart,ProblemsandSolutions:AdvancedProblem3918,TheAmericanMathematicalMonthly 46(1939)363. 6. B.M.Stewart,ProblemsandSolutions:AdvancedProblems:Solutions:3918,TheAmericanMathemat- icalMonthly48(1941)217-219. 7. A. Zhang, Properties of the Hanoi Graph for 4 Pegs, manuscript, https://www2.bc.edu/ grigs- byj/ZhangFinal.pdf 8. R.Wilson, J.J. Watkins, Graphs: AnIntroductory Approach–A First Course in Discrete Mathematics, Wiley,1990. January2014] TOWEROFHANOIANDFRAME-STEWARTCONJECTURE 9