Puzzle solution for n = 2 and n = 3

In order to illustrate the rules of the MToH, and also show the route to a more general solution, it is useful to work through examples for n = 2 and n = 3. For the case of n = 2, four steps are required, as shown in the accompanying figure, compared to three steps in the n = 2 case of the original ToH. The extra step is required because after the second step the small disk cannot be moved directly from the I post to the D post, as this would mean that its Blue side would be facing downwards. Thus, an extra step is required to flip the color of the small disk, so that it can then be placed on the D post with its Blue side facing upwards.

The solution of the n = 2 puzzle

For the n = 3 case, the solution involves the following steps:

• Numbering the disks 1 to 3 from largest to smallest, one first moves disks 2 and 3 from the S post to the I post (four moves)

This first stage is similar to the n = 2 puzzle described above, which also takes four moves, where the D and I posts are interchanged. However, it is not identical to the n = 2 puzzle due to the presence of the large disk on the S post, which "colors" it red. This means that a disk can only be placed on this post with its red side facing upwards.

• Move disk 1 from S to D (one move)

At this stage one might be tempted to again make use of the n = 2 puzzle, and try to move disks 2 and 3 from I to D in 4 moves. However, here again care is needed. Due to the presence of disk 1 on D, D is now "colored" Blue, i.e. another disk can be placed on it only if it has its Blue side facing up. Furthermore, with the n = 2 puzzle the disks have their red side facing upwards in the starting position, whereas here they have their blue sides facing upwards. Thus, this intermediate configuration is not equivalent to the n = 2 MToH. Instead, we proceed as follows:

• Move disk 3 from I to D via S (2 moves)
• Move disk 2 from I to S (1 move)
• Move disk 3 from D to I (1 move)
• Move disk 2 from S to D (1 move)
• Move disk 3 from I to D (1 move)

Thus, the solution requires 11 steps altogether. As just shown, it is natural to try to use the n = 2 solution to solve parts of the n = 3 puzzle in a recursive manner, as typically used for solving the classical ToH puzzle. However, in contrast to the classical ToH, here the n = 2 solution cannot be blindly applied due to the coloring of the posts and disks. This point illustrates that to achieve a more general solution for the n-disk MToH puzzle, it is necessary to consider variants of the puzzle where the posts are pre-colored (either Blue or Red). By considering these variants it is possible to develop full recursive relations for the MToH puzzle, and thus find a general solution.

Symmetry relations

Not all of the different colored variations are distinct puzzles, since symmetry means that some pre-colored puzzle variations are identical to others. For example, if we solve the RBB puzzle backwards, then this is the same as solving the RRB puzzle in the regular forward direction (note: the Blue and Red colors have been swapped to keep the rule that at the start of the puzzle all disks must be on the source post with their Red side facing up). Thus, the RBB and RRB puzzles form a time reversal symmetry pair. This means that they share the same characteristics with respect to the number of optimal moves required, even though each puzzle requires a distinct algorithm to solve it. In fact, it will be shown below that puzzles forming a time reversal symmetry pair are interdependent one on the other, in the sense that the solving algorithm of one makes use of the solving algorithm of the other.

Recursive solving algorithms and proof of their optimality

It is instructive to first consider the time reversal symmetry pair of puzzles RBB and RRB. As it turns out, these two puzzles are the simplest to solve in that their recursive algorithms depend only one on the other, and not on other variations of the puzzle.

In contrast, solutions for the semi-colored variations (where one or more posts are neutral) and the fully free variation are solved by more complex recursion relations. The RBB(n) and RRB(n) puzzles can be solved using the following pair of optimal algorithms:

For RBB(n):

• Move the n − 1 smallest disks from S to I using the RBB(n − 1) algorithm
• Move disk 1 from S to D
• Move n − 1 disks from I to S using the RRB(n − 1) algorithm
• Move n − 1 disks from S to D using the RBB(n − 1) algorithm

For RRB(n):

• Move the n − 1 smallest disks from S to D using the RRB(n − 1) algorithm
• Move n − 1 disks from D to I using the RBB(n − 1) algorithm
• Move disk 1 from S to D
• Move n − 1 disks from I to D using the RRB(n − 1) algorithm

The optimality of this pair of algorithms is proved via induction, as follows (this proof also forms a detailed explanation of the algorithms):

For n = 1 it is obvious that the algorithms are optimal, since there is only a single move. Next, it is assumed that the algorithms are optimal for n − 1, and using this assumption, it is shown that they are optimal for n.

Beginning with the RBB(n) algorithm, it is clear that before disk 1 can be placed on the D post, it must first be on the S post (which is the only post colored Red), and the rest of the disks must be on the I post. Thus, the solution must pass through this intermediate state, and, by assumption, the optimal way to achieve this intermediate state is to use the RBB(n − 1) algorithm with the D and I posts interchanged.

Next, disk 1 has to be moved from S to D, since it must be moved at least once.

Next, it is shown that from this state the final solution can only be reached via an intermediate state where all n − 1 disks are on the S post. For disk 2 to be placed on the D post, it must first be on the S post (the only Red post), while the other n − 2 disks must be on the I post. However, before disk 3 can be placed on the I post, it must first be on the S post on top of disk 2. This reasoning can proceed through all the disks, each of which must first be on the S post before passing to the I post, thus showing that the solution must pass through an intermediate state where all n − 1 disk are on the S post.

To achieve this intermediate state, it is necessary to use an optimal algorithm which transfers n − 1 disks from the Blue I post to the Red S post via the Blue D post, i.e. the optimal BBR(n − 1) algorithm, which is equivalent to the RRB(n − 1) algorithm (the colors are just swapped).

Finally, it is necessary to transfer the n − 1 smallest disks from the S to the D post via the I post. This of course is just the RBB(n − 1) algorithm.

Similar reasoning can be applied to show that the RRB(n) algorithm above is optimal. Solving algorithms can also be written, and their optimality proved, for other time-reversal pairs of the puzzles, namely:

• The RBN and NRB pair
• The RNB and BNR pair
• The RNN and NNB pair

These algorithms are generally more complex, and make use of the fully colored RBB and RRB algorithms described above. Full details of these algorithms and proofs of their optimality can be found in.^[7]

To conclude this section, the solving algorithm of the fully free NNN puzzle is listed. The proof of optimality can also be found in.^[7]

• Move the smallest n − 1 disk from S to I via D, using the RNN(n − 1) algorithm
• Move disk 1 from S to D.
• Move the smallest n − 2 disks from I to S via D, using the RRB(n − 2) algorithm (which is equivalent to the BBR(n-2) algorithm)
• Move the smallest n − 2 disks from S to D via I, using the RBB(n − 2) algorithm
• Move disk 2 from I to S
• Move the smallest n − 2 disks from D to I via S, using the RBN(n − 2) algorithm (which is equivalent to the BRN(n − 2) algorithm)
• Move disk 2 from S to D
• Move the smallest n − 2 disks from I to D via S, using the NNB algorithm

Recurrence relations and their solutions

Once the solving algorithms are found, they can be used to derive recurrence relations for the total number of moves made during the execution of the algorithm, as well as for the number of moves made by each disk.

Denoting the total number of moves made by the optimal algorithms of the RBB and RRB puzzles as ${\displaystyle S_{RBB}(n)}$ and ${\displaystyle S_{RRB}(n)}$, then referring to the solving algorithm listed above, it is easy to show that the following recurrence relation holds:

${\displaystyle S_{RBB}(n+1)=2S_{RBB}(n)+S_{RRB}(n)+1=3S_{RBB}(n)+1}$

where use has been made of the fact that the RBB and RRB puzzles form a time reversal symmetry pair, and thus ${\displaystyle S_{RBB}(n)=S_{RRB}(n)}$.

It is also possible to list a recursion relation for the total number of moves made by disk k, which we denote by ${\displaystyle P_{RBB}(k)}$ and ${\displaystyle P_{RRB}(k)}$ for the RBB and RRB algorithms respectively (note that ${\displaystyle P(k)}$ is independent of the total number of disks n in the puzzle). Again working through the algorithms, and using the equality ${\displaystyle P_{RBB}(k)=P_{RRB}(k)}$, it is simple to show that

${\displaystyle P_{RBB}(k+1)=2P_{RBB}(k)+P_{RRB}(k)=3P_{RBB}(k)}$

From these recursive relations, it is quite simple to derive closed form expressions for ${\displaystyle S_{RBB}(n)}$ and ${\displaystyle P_{RBB}(k)}$, which are given by

${\displaystyle S_{RBB}(n)=S_{RRB}(n)={\tfrac {1}{2}}3^{n}-{\tfrac {1}{2}}}$

${\displaystyle P_{RBB}(k)=P_{RRB}(k)=3^{k-1}}$

As can be seen, these quantities scale as 3ⁿ, in contrast to the classical ToH puzzle which scales as 2ⁿ. In fact, as shown in,^[7] all variations of the MToH puzzle satisfy the asymptotic relations

${\displaystyle \lim _{n\to \infty }S(n)=s3^{n}}$

${\displaystyle \lim _{k\to \infty }P(k)=p3^{k-1}}$

with the factors s, p given by the following table:

Finally, while the integer sequences generated by the expression for ${\displaystyle S_{RRB}(n)}$ and ${\displaystyle P_{RRB}(k)}$ are well known and listed in the Online Encyclopedia of Integer Sequences (OEIS),^[8] the integer sequences generated by the other puzzle variations are far less trivial, and were not found in OEIS prior to the analysis of the MToH. These new sequences, 15 in number, are now all listed.

Markov type solution

A powerful method of analyzing the MToH puzzle (and other similar puzzles), suggested by Fred Lunnon and presented in his review of Tower puzzles variations,^[4] is a matrix method.

In this method no effort is made to separate the various puzzles into independent groups whose solving algorithms depend only one on the other. Instead the solving algorithms are written in the most direct way so that algorithms of all the puzzle variations are interdependent. Once this has been done, the total number of moves ${\displaystyle S_{SID}(n)}$ (S,I,D being equal to R,B,N) for each puzzle variation can be written as follows:

${\displaystyle S_{NNN(n)}=S_{RNN(n-1)}+1+S_{NNR(n-1)}}$

${\displaystyle S_{RNN(n)}=S_{RNN(n-1)}+1+S_{NBR(n-1)}}$

${\displaystyle S_{NNR(n)}=2\cdot S_{RRB(n-1)}+1+S_{RBN(n-1)}+1+S_{RNN(n-1)}}$

${\displaystyle S_{NBR(n)}=2\cdot S_{RRB(n-1)}+1+S_{RBN(n-1)}+1+S_{RBN(n-1)}}$

${\displaystyle S_{RNB(n)}=S_{RBN(n-1)}+1+S_{NBR(n-1)}}$

${\displaystyle S_{RBN(n)}=S_{RNB(n-1)}+2\cdot S_{RRB(n-1)}+1}$

${\displaystyle S_{RRB(n)}=2\cdot S_{RRB(n-1)}+1+S_{RRB(n-1)}}$

Note that in contrast to the other variations and the general rule, MToH variations NNR and NBR end with the red sides of the disks facing upwards. This is a natural consequence of the destination post being colored red.

If we now define a vector

${\displaystyle {\vec {S}}(n)={\begin{bmatrix}S_{NNN}(n)\\S_{RNN}(n)\\S_{NNR}(n)\\S_{NBR}(n)\\S_{RNB}(n)\\S_{RBN}(n)\\S_{RRB}(n)\\1\end{bmatrix}}}$

Then

${\displaystyle {\vec {S}}(1)={\begin{bmatrix}1\\1\\2\\2\\1\\1\\1\\1\end{bmatrix}},}$

and the recursion relations can be written in the following matrix form

${\displaystyle {\vec {S}}(n)=M{\vec {S}}(n-1),}$

where the Markov matrix ${\displaystyle M}$ is defined by

The number of moves required for optimal solutions of different variations of the MToH puzzle

${\displaystyle M\equiv {\begin{bmatrix}0&1&1&0&0&0&0&1\\0&1&0&1&0&0&0&1\\0&1&0&0&0&1&2&2\\0&0&0&0&0&2&2&2\\0&0&0&1&0&1&0&1\\0&0&0&0&1&0&2&1\\0&0&0&0&0&0&3&1\\0&0&0&0&0&0&0&1\end{bmatrix}}}$

The equation for ${\displaystyle {\vec {S}}(n)}$ can now be written as

${\displaystyle {\vec {S}}(n)=M^{n-1}{\vec {S}}(1).}$

The characteristic polynomial of ${\displaystyle M}$ is given by

${\displaystyle (K-3)(K^{3}-K-2)(K-1)^{2}K^{2},}$

having the following eight roots

${\displaystyle {K_{1},\dots ,K_{8}}={3,1.52183,-0.7607+0.8579i,-0.7607-0.8579i,1,1,0,0},}$

and eight eigenvectors ${\displaystyle {\vec {\xi }}_{j}}$ such that

${\displaystyle M{\vec {\xi }}_{j}=K_{j}{\vec {\xi }}_{j}.}$

We can now express ${\displaystyle {\vec {S}}(1)}$ using the eight eigenvectors

${\displaystyle {\vec {S}}(1)=\sum _{j=1}^{8}b_{j}K_{j}{\vec {\xi }}_{j},}$

so that

${\displaystyle {\vec {S}}(n)=\sum _{j=1}^{8}b_{j}K_{j}^{n}{\vec {\xi }}_{j}.}$

Now, since ${\displaystyle |K_{1}|>|K_{j}|}$ for all ${\displaystyle j>1}$, it is clear that

${\displaystyle \lim _{n\to \infty }{\vec {S}}(n)=b_{1}K_{1}^{n}{\vec {\xi }}_{1}=b_{1}3^{n}{\vec {\xi }}_{1}.}$

Thus, as before we obtain the following asymptotic relation for all puzzle variations

${\displaystyle \lim _{n\to \infty }S_{SID}(n)=s3^{n}}$

with the factor s given by the following table: