>> (with accent)Thank you, Mr. Dersch. Okay, well…. you could usethis toy just for the seminar talk.(laughing) But you cannot takeit home with you. (all laughing) So…(clearing throat) I’m going to talkabout three main things. Obviouslythe Tower of Hanoi, the puzzle. And then, mathematiciansrelated to the puzzles, and some mathematics. So if you’re into the game,you’re going to be disappointed because I’m going to talkabout mathematics a lot. (chuckling) So, when you purchasethis Tower of Hanoi, it comes witha little paper. In that paper,we read this thing. Oops– going tothe wrong direction. Okay, here it is. I’m going to let youtake a look at it. >> I don’t wantto have to get it. (all laughing) I’ll die before that happens.(all laughing) >> All right, so itis a popular puzzle, and here’s a picture from ahands-on museum in Mexico City. And there are quitea tower behind her. And, if you see this one….(laughing) Yeah, she did itwrong on that one. So, Tower of Hanoi wasfirstly introduced by Monsieur Claus,Mister Claus, in 1883. And the game has manufacturedin several different names, such as theTower of Brahma, Hindu Pyramid Puzzle, Tower of Trouble. And Monsieur Claus made upthe story that we just read to go with theTower of Hanoi. So who isMonsieur Claus? It is actually aFrench mathematician, named FrancoisEdouard Anatole Lucas. Here’s a pictureof him there. He introduced theTower of Hanoi using”Monsieur Claus,” but the actualname is Lucas. And Claus is apermutation of Lucas. Lucas is best knownfor Number Theory. Studied theFibonacci sequence and then made uphis own sequence called the”Lucas Sequence.” And the difference betweenthose two sequences is not much,actually. Fibonacci– Let me see if I canfind one that works. Hmm, I should havepracticed first, I guess. Fibonacci Sequencehas as a formula, F-sub-n is equal toF-sub-n minus 1 plus F-sub-nminus 2, for n greateror equal to 3. And the Lucas’ Sequenceis also similar formula, L-sub-n is equal toL-sub-n minus 1 plus L-sub-nminus 2
plus L-sub-nminus 2 for n greateror equal to 3. So what’s thedifference? Initial. F-sub-1 is equal to 1,F-sub-2 is equal to 1, for theFibonacci sequence. But Lucas Sequence,L-sub-1 is equal to 1, L-sub-two isequal to 3. So, that’s theonly difference, but we get different sequenceof numbers, obviously, using both. He used thisLucas Sequence to testing theprime numbers. And he eventuallyproved that the Mersenne number– 2 tothe 127th power minus 1– is actually a prime, usingthe Mersenne sequence. Why is thatimportant? Because if we have thisnumber to be a prime number, we have a perfectnumber, also. Soon as you haveMersenne prime, we have aperfect number. And that number happened tobe the largest prime number discovered withoutusing a computer. Since then, all ofthe prime numbers discoveredusing computers. He also wrote the four volumeson “Recreations Mathematiques.” We read this– “Dayand night unceasingly “the priests transfer thediscs from one diamond needle “to another, accordingto the fixed and immutable law “of Brahma “which require that hemust place one disc, “or this disc,on a needles, “so that there is nosmaller disc below it.” Okay, so that means that wehave the following objectives for the puzzle. Meaning, you can moveone disc at a time. Never put a larger discon top of the smaller disc. And, finally, transferall of the discs onto the needle. All of the discs from oneneedle to another needle. Okay, that’sthe objective. Then, we see this,at the bottom. “When the 64 discs havebeen thus transferred “from one needleto the other needle, “tower, temple willcrumble into dust, “and with a thunder-clapthe world will vanish.” Sounds absurd. Is it? (chuckling) So, let me askyou this question. I know at least one personknows the answer to this one but I’m goingto ask this. Which of the followingis the largest? “A,” the age of theuniverse in seconds. “B,” number of starsin the universe. “C,” number of ways toarrange a deck of cards. “D,” number of movesrequired to transfer 64 discs from a needle toanother needle. Any guesses?(all laughing)
Any guesses?(all laughing) >> I’ll go for “D.” >> You’re going togo with the “D”? Okay!(all laughing) Which one do you thinkis the smallest, then? >> “C”? >> “C” is the smallest,you think? And the answer is… Oh, later.(all laughing) All right, so we’re going totalk about mathematics first. Suppose, insteadof 64 discs, suppose thereare n discs. And the question is, what isthe minimum number of moves required to transfer thediscs from one needle to another needle? Okay, we’re going todenote that with M-sub-n. Well, in orderto do that, we have to– here, I haveonly seven of them. And you alsohave seven. In order to movethe whole thing, first, I haveto move the… top six discs. In this case, we need to movethe top n minus 1 discs. How many moves?We don’t know. Let’s call thatM-sub-n minus 1 moves. Okay, once Ihave moved that, then I canmove the one, move to movethe largest one. And then, I’m going to putthat disc on top of that one, and how many movesdoes it take? M-sub-nminus 1 again! Okay? So, now let’s say Iadd those numbers. M-sub-n minus-1 to takeout the n minus 1 discs. Put it back,M-sub-n minus 1, and largest onetakes only one. And so, here is the recurrencerelations– adding them. First it– well, if you haveonly one disc, obviously, you need onlyone move. Well, the thing about that,is if you wanted to compute this 64 with thisrecurrence relation, you have to gothrough the… One, two, three,all the way to 63. So question is, isthere some nice formula that we can use to findout the number directly? Okay, so… Look at this one. Recurrence relationand closed formula. Well, M-sub-2, then, is twicethe previous one, plus 1. Well, what’s theprevious number? 1. We get2 plus 1. Instead of addingthose 2 plus 1, I’m going to keepit that way. So M-sub-3 is, by using therecurrence relation, is 2 times theprevious, plus 1. But what isthe M-sub-2? It’s 2 plus 1.
brain teasers math puzzles It’s 2 plus 1.
It’s 2 plus 1. Substitutethat in. Just put number withthe 2, we get this. How aboutM-sub-4? 2 times M-sub-3plus 1, M-sub-3 is this, just put itwith the 2, and then add 1. Do you see thepattern going on now? Okay? And one important thing I wantyou to know at this moment is this is thenumber of discs, and here is the sum wherethe largest exponent is 4. So in general, M-sub-nwould look like this, then. There are n discs, largest exponent willbe one less than that, and keep on adding allthe way down to one. Well, canwe add that? Yes, here’s a nicealgebra formula. x to the n minus 1,x to the n minus 2, all the waydown to 1. It’s a verysimple formula. Or another wayto look at it, this is a sum of thegeometric sequence, and the formula isthis one, I think. Well, in our case,the x is… 2. So substitutethe 2 in this, we get the formula2 to the n minus 1, over 2 minus 1, or simply 2 to the nminus one. That’s ourclosed formula. Which means we can figureout the number of moves for any number ofdiscs very quickly now. So, if wehave 64 discs, plug in 64, 2 to the 64minus 1 is… >> (indistinct). (all laughing) >> Here it is. 1.845 times10 to the 19th moves. Yeah. And thank goodness weonly have seven discs. >> If we stacked all ofours together, though… (all laughing) >> So, let’s go backand answer this. Which one wasthe largest? Well, we already figuredout the last one is 2 to the 64minus 1, okay? Age of the universe. Scientists believe that it isaround 13.82 billion years. Multiply by 365.25,including leap years, multiply by 24, 60,60, we get that. So this number is about42 times larger than that. So, if someonestarted the puzzle in the beginning of time…(laughing) that puzzle isnot finished yet. How about thenumber of stars? Scientists believe that thereare about 100 billion stars
Scientists believe that thereare about 100 billion stars in the Milky Way–that’s one galaxy– and there are also10 trillion galaxies. Multiplying them, about–this is just estimations– 10 to the 24thstars. Okay, someone said that “C” isthe smallest number, right? Okay, and the number of waysto arrange a deck of cards is actually52 factorial… and here isthe number. (murmuring from audience) This is thelargest one, actually. In fact, if we multiplyall of these three numbers, it’s still smallerthan part “C.” >> So if (indistinct), you justsay, “I’m going to deal now.” >> Yes!(all laughing) That’s right. Okay, so… you sawthis picture. There are 32 discs. So in order to movethat 32 discs from one needleto the other one, it would take 2 to the 32minus 1, and that many moves. So if we think ofthat as seconds, it would take136 years. >> Think of all the thingsthat would distract you in the middle of that.>> Right. (all laughing) You cannot go to the bathroom,you cannot go to sleep. (all laughing) All right, so that’sthe introduction to the Towerof Hanoi. I wanted to introduceanother mathematician, a famous mathematician,named William Rowan Hamilton. He is an Irishmathematician, and this is a perfectpicture, with the stamps. There are two thingsyou see in this stamps. One of them isthe equations, and the other oneis the diagram. William Rowan Hamiltonmade contributions to the abstractalgebra– well, he first startedwith optics and dynamics, and then, after that, he wasthinking about abstract algebra. In 1843, Hamilton discoveredwhat we call “quaternions,” a noncommutativegroup. Very fascinatingmathematics. And besides this equation,you see this diagram, right? Pentagon-shapeddiagram. 1857– Hamilton introducedthe Icosian Game. So what is theIcosian Game? Here it is. That diagram is actuallya two-dimensional drawing of a dodecahedron,like this one. And basically,there are 20 pegs, and put those pegssequentially, and must startfrom the one peg and go around to allof the 20 vertices, and come back to whereyou started from. So here’s the,um… He sold this game ideato a game dealer for 25 pounds in 1800s.(laughing) Sounds like it’snot that much, but I would imagine withinflation and everything, somewhere around50,000 pounds now, maybe? I don’t know. And the dealer sold the gamewith several different names, and here’sanother name. Okay, here we go. A Voyage Roundthe World. The puzzle consisted ofa wooden dodecahedron, as you can see, althoughthe bottom is rather flat, wide and flat, with a peg at each vertexof the dodecahedron, and the string. 20 vertices were labeledwith different cities and with the stringgoing through all of the 20 verticesexactly once. Another name they used isTraveler’s Dodecahedron. The object of the puzzle wasto start at a city, one city, travel along the edgesof the dodecahedron, visiting the othercities exactly once and getting back to thehome where you started. Well…(exhaling) Turned out that apparentlythe game didn’t sell well. So it was goodfor Hamilton, he got the money,but the game producer, game manufacturer,lost money, because the gamedidn’t sell well. However, so Hamilton is notfamous for inventing this game. He’s famous for thisidea right here. Visiting each of the other19 cities exactly once and back to wherehe starts from. In graph theory, we callthat a “Hamiltonian Cycle.” And then, there isthe Hamiltonian Path to go with that. So Hamiltonian Cyclein a graph is the cycle that containsevery vertex of the graph, turns out to beexactly once, and goes back towhere he started from. Hamiltonian Path,on the other hand– you start at one vertexand end at the other vertex. You don’t need to go backto where you started from. So here is theHamiltonian Cycle, on this graph. Go this way, and come backto where you started from. There’s a Hamiltonian Pathon the second graph there. So, solution tothat Icosian Game. This might be onepossible solution, finding aHamiltonian Cycle. Visiting everyvertex exactly once and coming back towhere you started. That’s onepossibility. I happened to draw that, butthere’s several other ones. Okay, if a graph hasa Hamiltonian Cycle, then it contains aHamiltonian Path. Well… The converseis not true. We could go through thisvertex and end it there, so it has aHamiltonian Path, but it cannot go back towhere you started from. Well, if youwanted to do it, you have to gothrough this vertex. And that means that thisvertex is visited twice. Second graph does not haveany Hamiltonian Cycle, nor Hamiltonian Pathto go with that. No matter howmuch we try, we just cannotfind one. All right. Now, I’m going to introduceanother class of graph called the “n-Cube Graph,”or “Hypercube Graph.” So, what is then-Cube graph? Well, it is defined,recursively, Q-sub-n is equalto Q-sub-n minus 1 times Q-sub-1. Or Q-sub-1 isthe same as K-2. Now, this is kind of afancy thing in graph theory, but simply put,basically, in order to obtainthe next cube graph, draw the two copiesof the previous one, and then join thecorresponding vertices. Okay, so here it is–this is Q-1. In order toobtain the Q-2, draw the two copiesof the previous one, and join thecorresponding edges. What is this? How about Q-3? Two copiesof Q-2, and join thecorresponding vertices. Okay, Q-4. Two copiesof Q-3, and join thecorresponding vertices. This is ordinarilycalled a “cube,” and that’s calleda “hypercube graph.” Um, more!(chuckling) This is going to getcomplicated very quickly, as you can see. So, why are wetalking about this? Well, it turns outthat every Cube Graph has a HamiltonianPath in it. So here’sone of them. Q-2 has aHamiltonian Path. Sideway–start over here, visit here, there,and come back. Cube 3. Started here… go up… come back. Now, let’s count the numberof different colors of the edgesfor a moment. One red, two yellow, four… that’s one, two,and four. Well, let’s lookat this one. Starting here, go tothe same as before. Cross over withthe green edge, and now go back. This one. One green, two red, four yellow, eight blue. Do you see the connectionbetween here and the number thatwe saw before? Okay, so! 1956… Crowe. He’s a professor at theUniversity of Michigan now, apparently. He wrote a paper on connecting n-Cube Graphand the Tower of Hanoi. He says, “The sequence ofn-tuples in an H-sub-n sequence “describes an H-circuitof the n-cube.” Hmm… what? Translation,please, okay? Here, it basically means that…he called it an “H-circuit,” but this is actuallya Hamiltonian Cycle. So his Hamiltonian Cyclein the n-Cube graph describes thesequence of moves for n discs in theTower of Hanoi. So! Basically,what that means… as we walk along the edgesof a Hamiltonian Path, in the n-Cube graph, move depending on whatcolor of the edge is. Now, I purposefullycolored it this way. Horizontal edge is blue,represents the disc number 1. 45-degree angle edgeis disc number 2. Vertical edge, which is red,disc number 3. And the green, about150-degree angle edge, represents the disc number 4,or green edge. So let’s start! Ready to play thegame now– or puzzle? Let’s start with the easy one!(laughing) (puzzle piecesclattering) One disc! Blue one. Yay! Okay. So, if you have two discs, thesequence of moves should be… disc 1, disc 2,and disc 1. Disc 1, disc 2, and thendisc 1. (puzzle piecesclattering) All right. It’s going to get complicatedvery fast, though. (chuckling) Here we go–three discs! (puzzle piecesclattering) Let’s follow them,all right? 1, 2,1, 3, 1, 2, 1. Okay, so… 1. 2. 1. 3. 1. 2. 1. Did you get lost? Did I go too fast on you?(all chuckling) Okay, try again. We got plenty enough timeto do these things. Okay. (puzzle piecesclattering) Start again. 1. 2. 1. 3. Okay, now, 1. Mmm-hmm. 2. No, the other way–that’s right. And then, 1. Got it? All right, let’s go withthe four discs, then! (puzzle piecesclattering) So here it is. Ready tofollow this? You can do it. Maybe if– I’ll go slowly.(laughing) 1. 2. 1. (puzzle piecesclattering) 3. (puzzle piecesclattering) 3, okay? 1. 2. 1. 4. That’s thelargest disc. 1. 2. 1. 3. 1. 2. And 1. (general chatter) Okay, now, hereit is, folks. I don’t have the diagramfor the Cube 5, because it’s going toget too complicated. But you understandwhat’s going on. All you have to use isthis one to unload, and then, move the largestone, disc number five, and then use the samegraph to move it back. Make sense? Okay, I’m gonnalet you try. (puzzle piecesclattering) Okay! Have you finished allseven of them, maybe? (laughing) >> (indistinct). >> Yeah! (all laughing) I’m going to illustratewith an ice cream cone. When you order ice creamwith an ice cream cone, well, obviously theimportant part is the… ice cream rightin the cone. Cone is just a vehiclefor carrying ice creams. And I look at theTower of Hanoi as a vehicle for… talk aboutmathematics! (scattered chuckling) So, mathematics is adelicious yummy part of thiswhole thing. And some of the mathematicsthat we talked about today might be–just call out– Number Theory,Combinatorics, Abstract Algebra,Recurrence Relations, Hamiltonian Path,Hamiltonian Cycle, Hyper n-CubeGraphs. Those are the yummy partof this whole thing. And applications ofthis Tower of Hanoi and the– some of the mathematics mightbe used in data structure in algorithms,comparative science. There is times when–there is– let’s see. F-I-L-O. How many of youhave heard of FILO? “First In, Last Out.”>> (all) “First In, Last Out.” >> Well, you havedata structures. So if you have the largestdisc at the bottom, that would bethe last one out. And there are several algorithmsthat have to go through before ittakes it out. And also, Hamiltonian Cycle is quite useful in theoptimization problem called the “TravelingSalesman Problem.” In that, actually,it’s not a dodecahedron, but it is acomplete graph, and so we are looking at whatis the most economical way to go traveldifferent cities and come back to whereyou started from, okay? There’s a lot of theories, alot of research is going on. In 1998, Adlemanmade the connection between DNA and alsoHamiltonian Path. So there’s anapplication there. And finally,Hamiltonian Cycle is applied in the Gray Codes,and Coding Theory, also. So with that,have fun, and enjoy thepuzzles, everyone. Thank you. Thank you! (applause)