8
$\begingroup$

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework.

This is a variant on the classic towers of Hanoi, where all moves must be made clockwise only. The recursive solution is to consider $Q_n$ to be the number of moves to move a tower size $n$ one step across (e.g. from start $\rightarrow$ end post), and $R_n$ to be the number of moves to move it two (e.g start $\rightarrow$ end $\rightarrow$ spare).

The recursive solution is (sorry about the formatting, just getting to grips with tex):

$Q_n = 0 \quad \text{if n = 0}$

$Q_n = 2R_{n-1} + 1\quad \text{if n > 0}$

$R_n = 0 \quad \text{if n = 0}$

$R_n = Q_n + Q_{n-1} + 1 \quad \text{if n > 0}$

How can I prove these? I presume an inductive proof is required but everything I've tried to do just gets garbled into a mess of further decreasing $n$ values.

Explaining why these work is simple enough: $Q_n$ can be explained by the fact that you need to move a stack of size $n-1$ two steps forward followed by the $n$ piece, followed by moving the $n-1$ stack two steps again onto the $n$ piece=> $Q_n = R_{n-1} + 1 + R_{n-1} = 2R_{n-1}+1$.

The wordy proof for $R_n$ is similar: It consists of moving $R_{n-1}$ then 1 followed by $Q_n$, 1 and $R_{n-1}$ which will end us up with

$R_n = 2R_{n-1}+1+Q_{n-1}+1 = Q_n+Q_{n-1}+1$

But these are all just words that don't form any real proof... I've gone over the leading chapter and looked up some resources on proof by induction, but doing it with a recursion with two components has put me for a spin (having forgotten a lot of the math studied in the past certainly isn't helping either). If someone could run me through a rigorous proof for $n > 0$ it would be much appreciated.

As an aside, any recommended learning resources on proof by induction would be appreciated as I'm still barely "getting it".

3 Answers 3

7

The "word" description is in fact the guide to a proof. The only problem is showing that the process you describe is in fact optimal. This is done by induction.

we want to prove the formulas you give are the optimal solution.

The case $n=0$ is immediate.

Now: to prove the $k+1$ case assuming the $k$th case (so our induction hypothesis is that the formula you give is optimal for $R_k$ and for $Q_k$), you take a stack of $k+1$ disks. To move them all forward (to perform $Q_{k+1}$) you must get the top $k$ out of the way; that is done, by the induction assumption, with $R_k$ as optimal. Then you move the $k+1$ disk to the target, taking one move; then you move the disks from where they are to the target. Again, by the induction assumption, the best possible way of doing this is $R_k$. So you get that $Q_{k+1}=R_k+1+R_k=2R_k+1$, on the assumption that $Q_k$ and $R_k$ are the optimal moves.

The same argument works for $R_{k+1}$; the only thing that your "just words" is missing is to be clear about what the induction hypothesis is, and to apply it.

Added: Why is the given strategy actually the best? In order to move all the disks from the original rod to the target rod, we must move the largest disk at least once; note that the position of the largest disk does not affect the validity or lack thereof of any move, so the position of the largest disk is immaterial for any other moves (as opposed to any other disk). So the optimal solution will only require us to move the largest disk exactly once, from the original rod to the target rod. In order to do this, we must first remove all disks from above the largest disk, and have no disks on the target rod so we can perform the move; that is $R_k$, because the only configuration that allows us to move the largest disk from the original rod to the target rod is to have all other disks in the non-target rod. Then we move the largest disk, which is the $+1$. And now, we just want to move the remaining disks to their final position in the quickest possible way, which again is $R_k$. A similar argument focusing on placing the largest disk in its final position, works for the computation of $R_{k+1}$.

  • 0
    Thanks, that seems to make sense to me. However one thing I remain unsure of is that this proof depends on the strategy of moving $R_k$ followed by 1 followed by $R_k$. While by "common sense" this makes sense, it isn't actually proved as the best strategy to move a stack $K_{n+1}$ or is it?2010-12-17
  • 0
    @juhanic: I added a paragraph at the end to explain that.2010-12-17
  • 0
    A minor point is that the solution is conditional on the assertion that moving the largest disk once is optimal. There are a number of ways to actually prove this. The technically simplest (but not most intuitive) is that this argument shows the number of moves to solve the puzzle is no less than $2 R_k + 1$, and since we can solve it in that many moves, it must be an optimal solution.2012-05-25
0

I was trying to do this same exercise. So, I am posting this answer to add some details that I find relevant. I would like someone to confirm if this information is correct and consistent.

The original statement from the book is:

Let $Q_n$ be the minimum number of moves needed to transfer a tower of $n$ disks from A to B if all moves must be clockwise-that is, from A to B, or from B to the other peg, or from the other peg to A. Also let $R_n$ be the minimum number of moves needed to go from B back to A under this restriction. Prove that

$\begin{align}Q_n&=\begin{cases} 0 \text{, if $n = 0$} \\ 2R_{n-1}+1 \text{, if $n>0$}\end{cases}\end{align}$

$\begin{align}R_n&=\begin{cases} 0 \text{, if $n = 0$} \\ Q_n+Q_{n-1}+1 \text{, if $n>0$}\end{cases}\end{align}$

The exercise states that the only allowed moves are either from A to B, or from B to the middle peg, or from the middle peg to A. $Q_n$ is the minimum number of moves to transfer a tower from A to B, and $R_n$ is the minimum number of moves from B to A. Now, let $M_n$ be the minimum number of moves needed to transfer a tower of $n$ disks from A to the middle peg, and let $N_n$ be the minimum number of moves needed to go from the middle peg to B.

To find the recurrence relation for $Q_n$, we find an optimal sequence of moves from peg A to peg B. We want to move the largest disk from peg A to peg B; to allow this, we must move the top $n-1$ disks from peg A to the middle peg (so that they are out of the way), which needs $M_{n-1}$ moves. Then, we can move the largest disk to peg B, which takes 1 move. Then, we move the top $n-1$ disks from the middle peg to peg B, which takes $N_{n-1}$ moves. So, $Q_n = M_{n-1} + N_{n-1} + 1$.

Now, the only detail left is how to find $M_n$ and $N_n$. Notice that the original wording of the exercise doesn't directly state what are $M_n$ and $N_n$, and this is the reason why I am posting this answer. I will show that $M_n$ and $N_n$ are, actually, the same as $R_n$, which makes $Q_n = 2R_{n-1} + 1$. For me, this was really not obvious at first, and I took a long time to realize it.

But, first, let us find the recurrence relation for $R_n$. We want to move the largest disk from peg B to peg A, but, since this is not allowed directly, we must first move it to the middle peg. To allow this, we must first move the top $n-1$ disks to peg A, which takes $R_{n-1}$ moves. Then, we move the largest disk to the middle peg (1 more move). Then, to be able to move the largest disk from the middle peg to A, we must first move the top $n-1$ disks from A to B ($Q_{n-1}$ more moves). Then, we move the largest disk to peg A (1 more move). Finally, we move the top $n-1$ disks from B to A ($R_{n-1}$ more moves). So, $R_{n} = 2R_{n-1} + Q_{n-1} + 2$. Notice that, in the whole procedure of moving the tower from B to A, every individual disk that moves from B to A has to first make a stop at the middle peg (from which they can move directly to B), due to the moving rules (clockwise).

The moves from A to the middle peg ($M_n$) are equivalent to the moves from B to A ($R_n$) because, in an analogous way, every individual disk that moves from A to the middle peg has to first make a stop at peg B (from which they can move directly to the middle peg). So, the moves from A to the middle peg use B as the "middle peg" in exactly the same way as the moves from B to A use the middle peg.

Analogously, all the moves of individual disks from the middle peg to B ($N_n$) also involve making a stop at peg A (because the moving rules don't allow direct moves from the middle peg to B, but do allow direct moves from A to B), so $N_n$ is also equivalent to $R_n$.

0

The best answer is great, but I just wanted to add more explanation to clarify, because it took me a while to completely understand the problem and the solution. Also note that the duplicate for this question also has a similar answer which may help clarify.

First of all, realize that the only direction in which we can make moves are from $A$ to $B$, $B$ to $C$ and from $C$ to $A$ (clockwise). So what $R_n$ essentially does is that it moves a stack of $n$ disks from a given peg to the previous peg by moving it forward twice (so from $B$ to $C$ to $A$). And what $Q_n$ does, intuitively, it moves a given stack of $n$ disks from a given peg to the next by moving it forward once. The other answers provide the case for proving $Q_n$, so I will just explain $R_n$.

For $R_n$ (moving a stack of $n$ disks from $B$ to $A$), what we need to do is to first move $n-1$ disks from $B$ to $A$, which is $R_{n-1}$ (as we need to move the disks forward twice). This lets us move the $n$ th disk from $B$ to $C$, which is cost $1$. Then, we can move the $n-1$ disks sitting at $A$ to $B$, which is $Q_{n-1}$. This again lets us move the largest, $n$ th disk, this time from $C$ to $A$, which is exactly what we wanted to do, for another cost $1$. Then, all that remains is to move the $n-1$ disks sitting at $B$ to $A$, which is $R_{n-1}$. Thus, the total is:

$$Q_n = R_{n-1} + 1 + Q_{n-1} + 1 + R_{n-1}$$

Now, notice that $2R_{n-1} + 1 = Q_n$, so the above total becomes:

$$Q_n = Q_n + Q_{n-1} + 1$$