![]() The inequality suggests that it might be possible to move N disks with fewer than 2T N-1 + 1 moves. The recursive solution above involves moving twice (N - 1) disks from one peg to another and making Now let us try to derive a general formula. A trained mathematician would also note that T 0 = 0. One can easily convince oneself that T 2 = 3 and T 1 = 1. From the previous section T 3 = 7 and T 4 = 15. Let T N be the minimum number of moves needed to solve the puzzle with N disks. Of course "Move" means moving the topmost disk. To me the sheer simplicity of the solution is breathtaking. The function is recursive in that it calls itself repeatedly with decreasing values of N until a terminating condition (in our case N = 0) has been met. This actually serves as the definition of the function Solve. Then the body of the function might look like Move N - 1 disks from Aux to Dst (using Src as an intermediary peg)Īssume there is a function Solve with four arguments - number of disks and three pegs (source, intermediary and destination - in this order).Move the top N - 1 disks from Src to Aux (using Dst as an intermediary peg).Know how to accomplish the following tasks: Therefore, for a given number N of disks, the problem appears to be solved if we After moving the bottom disk from Src to Dst these disks will have to be At this point in time all the remaining disks will have to be stacked However one solves the problem, sooner or later the bottom disk will To better understandĪnd appreciate the following solution you should try solving the puzzle for small number of disks, Let call the three pegs Src (Source), Aux (Auxiliary) and Dst (Destination). Try IE11 or Safari and declare the site as trusted in the Java setup. If you are reading this, your browser is not set to run Java applets. The applet expects you to move disks from the leftmost peg to the rightmost peg. You can drop a disk on to a peg when its center is sufficiently close to the center of the peg. To solve the puzzle drag disks from one peg to another following the rules. The applet has several controls that allow one to select the number of disks and observe the solution in a Fast or Slow manner. Its solution touches on two important topics discussed later on: The puzzle is well known to students of Computer Science since it appears in virtually any introductory text on data structures or algorithms. The objective is to transfer the entire tower to one of the other pegs (the rightmost one in the applet below), moving only one disk at a time and never a larger one onto a smaller. We are given a tower of eight disks (initially four in the applet below), initially stacked in increasing size on one of three pegs. So we expect a total of 90690 dots to be covered, for an average of 9.069 per throw.The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. In other words, in 10000 throws of the honeycomb, the expected number each dot will be covered is 9069 times. There will be 10 or fewer coins remaining.Ī small digression: Is it possible that for some clever arrangement of dots the long range average of covered dots is something other than 9.069? The answer is no, because each of the dots can be considered separately. You duplicate that throw, and remove all the coins that aren't covering a dot. So now you know that there was at least one throw that covered 10 dots. Because if you never covered 10 dots, the average would be 9 or less. The key insight is that if the average is 9.069, there must have been a throw where 10 dots were covered. If you get enough samples you will eventually find that the expected average number of dots covered is 9.069 per throw. You now do a Monte Carlo simulation, repeatedly throwing the honeycomb on the table at a random location (but always with the same orientation), and counting the number of covered dots. ![]() You also have a big template made of coins glued together in a honeycomb pattern. You're given an arrangement of dots on a table. I think that I can re-arrange Winkler's argument to make it a little more convincing. Can't we still come up with a configuration involving 10 (or less) dots where one of the dots can't be covered? Doesn't the probabilistic nature of this proof simply mean that in the majority of configurations, all 10 dots can be covered. In the following issue, he presented his proof:ĩ0.69% of the infinite plane? The easiest way to answer is to say, In the Communications of the ACM, August 2008 "Puzzled" column, Peter Winkler asked the following question:
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |