Editing Tower of Hanoi (section)

=== 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 Tat-Hung independently discovered<ref>{{cite journal |first=A. |last=Hinz |title=The Tower of Hanoi |journal=L'Enseignement Mathématique |volume=35 |year=1989 |pages=289–321 |doi=10.5169/seals-57378 }}</ref><ref>{{cite journal |first=T. |last=Chan |title=A statistical analysis of the towers of Hanoi problem |journal=Internat. J. Comput. Math. |volume=28 |issue=1–4 |year=1988 |pages=57–65 |doi=10.1080/00207168908803728}}</ref> (see also
<ref>{{cite book |last=Stewart |first=Ian |title=Another Fine Math You've Got Me Into... |publisher=Courier Dover |year=2004 |isbn=978-0-7167-2342-4 }}</ref>{{rp|Chapter 1, p.&nbsp;14}}) that the average number of moves in an n-disk Tower is given by the following exact formula:

:<math> \frac{466}{885}\cdot 2^n - \frac{1}{3} - \frac{3}{5}\cdot \left(\frac{1}{3}\right)^n +
\left(\frac{12}{59} + \frac{18}{1003}\sqrt{17}\right)\left(\frac{5+\sqrt{17}}{18}\right)^n +
\left(\frac{12}{59} - \frac{18}{1003}\sqrt{17}\right)\left(\frac{5-\sqrt{17}}{18}\right)^n.</math>

For large enough ''n'', only the first and second terms do not converge to zero, so we get an [[asymptotic analysis|asymptotic expression]]: <math>466/885\cdot 2^n - 1/3 + o(1)</math>, as <math>n \to \infty</math>. Thus intuitively, we could interpret the fraction of <math>466/885\approx 52.6\%</math> 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 <math>2^n - 1</math> 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.<ref>{{cite journal |first=D. |last=Romik |title=Shortest paths in the Tower of Hanoi graph and finite automata |journal=[[SIAM Journal on Discrete Mathematics]] |volume=20 |issue=3 |year=2006 |pages=610–622 |doi=10.1137/050628660|arxiv=math/0310109 |s2cid=8342396 }}</ref>