General Shortest Paths and The Number 466/885
A curious generalization of the original goal of the puzzle is to start from a given configuration of the disks where all disks are not necessarily on the same peg, and to arrive in a minimal number of moves at another given configuration. In general it can be quite difficult to compute a shortest sequence of moves to solve this problem. A solution was proposed by Andreas Hinz, and is based on the observation that in a shortest sequence of moves, the largest disk that needs to be moved (obviously one may ignore all of the largest disks that will occupy the same peg in both the initial and final configurations) will move either exactly once or exactly twice.
The mathematics related to this generalized problem becomes even more interesting when one considers the average number of moves in a shortest sequence of moves between two initial and final disk configurations that are chosen at random. Hinz and Chan Hat-Tung independently discovered (see also, Chapter 1, p. 14) that the average number of moves in an n-disk Tower is given by the following exact formula:
Note that for large enough n, only the first and second terms are not converging to zero, so we get an asymptotic expression:, as . Thus, intuitively we could interpret the fraction of as representing the ratio of the labor one has to perform when going from a randomly chosen configuration to another randomly chosen configuration, relative to the difficulty of having to cross the "most difficult" path of length which involves moving all the disks from one peg to another. An alternative explanation for the appearance of the constant 466/885, as well as a new and somewhat improved algorithm for computing the shortest path, was given by Romik.
Read more about this topic: Tower Of Hanoi
Famous quotes containing the words general, shortest, paths and/or number:
“The first general store opened on the ‘Cold Saturday’ of the winter of 1833 ... Mrs. Mary Miller, daughter of the store’s promoter, recorded in a letter: ‘Chickens and birds fell dead from their roosts, cows ran bellowing through the streets’; but she failed to state what effect the freeze had on the gala occasion of the store opening.”
—Administration in the State of Sout, U.S. public relief program (1935-1943)
“Cultivated labor drives out brute labor. An infinite number of shrewd men, in infinite years, have arrived at certain best and shortest ways of doing, and this accumulated skill in arts, cultures, harvestings, curings, manufactures, navigations, exchanges, constitutes the worth of our world to-day.”
—Ralph Waldo Emerson (1803–1882)
“The paths of glory lead but to the grave.”
—Thomas Gray (1716–1771)
“Not too many years ago, a child’s experience was limited by how far he or she could ride a bicycle or by the physical boundaries that parents set. Today ... the real boundaries of a child’s life are set more by the number of available cable channels and videotapes, by the simulated reality of videogames, by the number of megabytes of memory in the home computer. Now kids can go anywhere, as long as they stay inside the electronic bubble.”
—Richard Louv (20th century)