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:
“There are two great rules in life, the one general and the other particular. The first is that every one can in the end get what he wants if he only tries. This is the general rule. The particular rule is that every individual is more or less of an exception to the general rule.”
—Samuel Butler (1835–1902)
“I have simplified my politics into an utter detestation of all existing governments; and, as it is the shortest and most agreeable and summary feeling imaginable, the first moment of an universal republic would convert me into an advocate for single and uncontradicted despotism. The fact is, riches are power, and poverty is slavery all over the earth, and one sort of establishment is no better, nor worse, for a people than another.”
—George Gordon Noel Byron (1788–1824)
“O Master, let me walk with Thee
In lowly paths of service free;
Tell me Thy secret, help me bear
The strain of toil, the fret of care.”
—Washington Gladden (1836–1918)
“In proportion as our inward life fails, we go more constantly and desperately to the post office. You may depend on it, that the poor fellow who walks away with the greatest number of letters, proud of his extensive correspondence, has not heard from himself this long while.”
—Henry David Thoreau (1817–1862)