Back awhile, in a blog about Fibonacci, I mentioned that Edouard Lucas had created the "Tower of Hanoi" game and received comments and mail from people who thought I must be mistaken because the game was "really old". Turns out, it really isn't, but just the creation of a master mathematical story teller. Here are some notes about the man, and the history of the Towers of Hanoi from my Math Words Etymology page.
Also, you can find a java applet to play the game at this site... and if you've never done it (where HAVE you been?) don't start with all 12 discs, that takes 4095 moves to solve (see below).
The Lucas sequence is similar to the Fibonacci sequence. The Lucas sequence is given by {1, 3, 4, 7, 11, 18, ...} . Each term is the sum of the two previous numbers, as in the Fibonacci sequence. Just as in the Fibonacci sequence, the limit of the ratio of consecutive terms is the Golden Ratio. The Lucas numbers can also be constructed from the Fibonacci numbers by the function Ln = Fn-1 + Fn+1, thus the fifth Lucas number, 11, is the sum of the fourth and sixth fibonacci numbers (3+8).
The sequence is named for Edouard Lucas, a French mathematician of the later half of the nineteenth century. He used his sequence and the Fibonacci sequence to develop techniques for testing for prime numbers. Lucas is also remembered for his unusual death, caused by a waiter dropping a plate which shattered sending a piece of plate into his neck. Lucas died several days later from a deadly inflamation of the skin and subcutaneous tissue caused by streptococcus. The disease, officially listed as erysipelas (from the Greek for "red skin") was more commonly known as "Saint Anthony's Fire".
Lucas was also the creator of a popular puzzle called The Tower of Hanoi in 1883. You can see the original box cover above. Note that the author on the box cover is Professor N. Claus de Siam, an anagram of Lucas d' Amiens (his home). The professors college, Li-Sou-Stian, is also an anagram for "Lycee Saint-Louis" where Lucas worked.
France was building an Empire in Indochina (the peninsula stretching from Burma to Viet Nam and Malaysia) and the "mysterious East" was a very fashionable topic. Lucas created a legend (some say he embellished an existing one, but I can find no earlier record of one) of monks working to move 64 gold disks from one of three diamond points to another after which the world would end. The solution for a tower of n disks taks 2n -1 moves, so the game often had less than the 64 disks of the legend. Solving the 64 disks at one move a second would require 18,446,744,073,709,551,615 seconds, which at 31,536,000 seconds a year would take 584 Billion years. (and you thought Monopoly took a long time to finish). The reference in his instructions to Buddhist monks in a temple in Bernares(Varanasi), India seems, even now, to make people believe there was such an activity taking place. Varanasi is considered the holiest of the seven sacred cities (Sapta Puri) in Hinduism, and Jainism, and is important to Buddhism because it was in nearby Sarnath that Buddha gave his first teaching after attaining enlightenment, in which he taught the four noble truths and the teachings associated with it. There is a Buddhist temple there with many relics of the Buddha, but so far as I can find, no monks moving golden disks on needles.
Students/teachers interested in further explorations of the history and math of the famous game should visit the work of Paul K Stockmeyer who maintains the page with the cover illustration mentioned above, and his Papers and bibliography on the Tower of Hanoi problem.
Lucas developed several other mathematical games of his on, including the well known children's pastime of dots and boxes (which he called La Pipopipette), which on large boards is still essentially unsolved, I believe. He also (probably) invented a Mancala type game called Tchuka Ruma.
Lucas is also remembered for suffering an unusual death. At a banquet in 1891 a waiter dropped a dining plate and one of the pieces cut Lucas on the neck and cheek. Within a week he was dead from what was called the "Holy Fire" or St Anthony's Fire, a form of septicemia.
A while after I wrote the above, I learned a little more, and so:
Just browsing through Wikipedia, and they show a solution to the Towers of Hanoi puzzle that I had never seen using a ruler as a solution key.
If you have been off planet for the last 130 years and don't know the Towers problem, you can play online here. You might try that first, and set the number of discs to 6 so that it matches the solution shown below.
And for those who know the game but just want to see how a ruler is used, here is the graphic.
For any move, just move the disc whose size compares to the marks on the ruler. For instance the first five marks on a ruler marked in 32nds would be 1/32, 1/16/ 3/32, 1/8, 5/32.... The denominators tell you which disk to move. The largest denominator (smallest scale) goes with the smallest disc, etc. If you then apply two fundamentals of any solution, always move the smallest disc From rod A, to B to C and back to A in a cycle, and never put a bigger disc on a smaller one, then you have a solution... That's easier than Gray codes isn't it.
Why have I never encountered this before? The connection was made in 1956 by Donald W. Crow, in relation to traversing the vertices of a cube in n-dimensions[ D. W. Crowe, The n-dimensional cube and the tower of Hanoi, Amer. Math. Monthly, 63 (1956), 29-30.]
POSTSCRIPT:::: For another really insightful solution (maybe the best of them all) See the comment by Jeffo....Thanks guy, why don't I see ideas like that?
If the rods are placed in a circular arrangement instead of linear, then a correct solution will involve always moving the smallest disk one rod clockwise every other move. The alternate moves are forced.
No comments:
Post a Comment