# Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi.

Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - 1$ moves apart, under Lucas's original rules?

My initial guess is no, there are no starting and ending configurations of $n$ disks on three pegs that are more than $2^n - 1$ moves apart.

I will post an answer to this question with my attempt at a solution. I would like to confirm if my solution is correct and complete, or if there is a better approach.

-

I will show it by induction on $n$ (the number of disks). Let $T(n)$ be the number of moves needed to go from an arbitrary configuration to another arbitrary configuration. Let $P(n)$ be the proposition "$T(n)\leq 2^n-1$". That is, $P(n)$ is the proposition "All starting and ending configurations of $n$ disks are at most $2^n-1$ moves apart.". I want to show that $P(n)$ is true for every natural number $n$.

For the base case, $P(0)$ is true, because it is clear that $T(0)=0\leq 2^0-1=0$.

For the inductive hypothesis, let's assume that $P(n-1)$ is true; that is, let's assume that it is true that $T(n-1)\leq 2^{n-1}-1$. Now, I will show that $P(n-1)$ implies $P(n)$.

First method

Suppose I have a configuration of $n-1$ disks. By the inductive hypothesis, we know that $T(n-1)\leq 2^{n-1}-1$. Now, let's consider what will change if we add one more disk (an $n^{th}$ disk), smaller than every other disk in the configuration, so that we have a situation where there are $n$ disks. Since this $n^{th}$ disk is the smallest one, it will always be on top in one of the three pegs, due to the rules of the problem.

The bottom $n-1$ disks will make $T(n-1)$ moves. For each move of the $n-1$ disks, in the worst case, the new smallest disk will be either on top of the disk that wants to move, or on top of the peg to which the disk wants to move. So, the new disk will have to make at most one move for each move of the other $n-1$ disks, that is, the new disk will make at most $T(n-1)$ moves. At last, when the $n-1$ disks are already at their correct positions in the end configuration, the new disk may have to make one more move to reach its correct position in the end configuration.

So, there will be at most $T(n) = T(n-1) + T(n-1) + 1 \leq 2^{n-1}-1+2^{n-1}-1+1 = 2^n - 2 + 1 = 2^n - 1$ moves. Therefore, $T(n) \leq 2^n - 1$, which shows that $P(n)$ is true.

Second method

I can also build the inductive step by considering that the new disk is the largest disk (instead of being the smallest one), as explained in the comments below.

Suppose we have a configuration of $n-1$ disks. By the inductive hypothesis, these $n-1$ disks need $T(n-1) \leq 2^{n-1}-1$ moves to reach any other configuration. Now, let's add an $n^{th}$ disk, which is the largest disk. We have two cases:

(1) If the largest disk doesn't move from the starting configuration to the end configuration, then we can just move the top $n-1$ disks as if there were only $n-1$ disks; so, in this case, it takes at most $2^{n-1} - 1$ moves. Therefore, it is true that $T(n) \leq 2^{n} - 1$. So, $P(n)$ is true in this case.

(2) If the largest disk moves, so we first have to move it to its end configuration. For this, we may have to move the top $n-1$ disks to a peg so that they are out of the way; by the inductive hypothesis, this takes at most $2^{n-1} - 1$ moves. Then, we move the largest disk to its correct position in the end configuration (1 more move). Then, we move the top $n-1$ disks to their correct positions in the end configuration (at most $2^{n - 1} - 1$ moves). The whole procedure takes at most $2^{n-1} - 1 + 1 + 2^{n-1} - 1 = 2^n - 1$ moves. So, $T(n) \leq 2^n - 1$. This shows that $P(n)$ is true in this case.

-
It’s easier if you make the new disk the largest one. Then it takes at most $T(n-1)$ moves to move the smallest $n-1$ disks to the peg on which the largest one is not supposed to end up, possibly one move to get the largest disk in place, and at most $T(n-1)$ moves to get the smallest $n-1$ disks to where they belong. However, what you’ve done works. – Brian M. Scott May 13 '12 at 23:39
It generally looks good, but it would be simpler to think about the largest disk instead of the smallest. To get from the initial position to any valid configuration, consider the largest disk that needs to be moved. If the largest disk is already in correct position, then the result follow from the $n-1$ case. Otherwise, you must first move all larger disks out of the way, more the largest disk into position, and then move the rest of the disks into position. The first part takes $2^{n-1}-1$ moves, the second takes $1$, and the final takes at most $2^{n-1}-1$ moves by the inductive hypothesis – Arturo Magidin May 13 '12 at 23:39
(cont) The key being that in any optimal sequence of moves, the largest disk needs to be moved at most once. – Arturo Magidin May 13 '12 at 23:41
@BrianM.Scott: Thank you for the suggestion, I've actually thought about doing it this way too. – anonymous May 13 '12 at 23:44
@ArturoMagidin: Thank you for the comment, moving the largest disk really seems to give a better idea about why this is an optimal sequence. I've thought about doing it this way too. – anonymous May 13 '12 at 23:46