This is exercise 11b from Concrete Mathematics book.
I know how to solve problem with Tower of Hanoi. I was able to interpret how many movements is required to transfer Tower of Hanoi with 2n disks from one peg to another. But currently I'm struggling with solving Tower of Hanoi with 2n disks and correct order. I managed to solve this problem in suboptimal (very non-efficient) way.
I preserved order all the time. It means, that no matter where I've been, all disks had the same order as initially.
B(n) = A(n-1) + 1 + A(n-1) + 1 + A(n-1) + 1 + A(n-1)
n=1, B(2) = 3
n=2, B(4) = 15
n=3, B(6) = 63
B(n) = 2^{2n} - 1
Although in book I see that correct answer is:
n=1, B(2) = 3
n=2, B(4) = 11
B(n) = A(n-1) + 2 + A(n-1) + 2 + B(n-1)
B(n) = 2^{n+2} - 5
I can understand, that we don't need to have the same order all the time, just at the end. It means, that I can move from peg A to peg B disks without an order. Then, move two last disks to peg C. Move back all n-1 disks back to peg A. Change order of two last disks moving them C->B…
And now I suspect that B(n-1) means: transfer from peg A to peg B with preserving order.
But how can I resolve this function and find final form?
Best Answer
$B(n)$ is the minimum number of moves required to move $2n$ disks subject to the stated constraints, and $A(n)$ is the minimum number required if we require only that no disk ever rest on a smaller disk.
The crucial point is that the solution to part (a) of the problem almost works for part (b): it leaves all of the disks in their original order except the two largest ones, which are reversed. We can avoid this reversal as follows.
Putting the pieces together, we see that
$$\begin{align*} B(n)&=A(n-1)+2+A(n-1)+2+B(n-1)\\ &=B(n-1)+2A(n-1)+4\\ &=B(n-1)+2\left(2^n-2\right)+4\\ &=B(n-1)+2^{n+1}\;, \end{align*}$$
where the penultimate step uses the closed-form solution $A_n=2^{n+1}-2$ of part (a).
Now we have the first-order recurrence $B(n)=B(n-1)+2^{n+1}$ with $B(1)=3$, which can be solved by ‘unwinding’:
$$\begin{align*} B(n)&=B(n-1)+2^{n+1}\\ &=B(n-2)+2^n+2^{n+1}\\ &=B(n-3)+2^{n-1}+2^n+2^{n+1}\\ &\;\;\vdots\\ &=B(n-k)+\sum_{i=n+2-k}^{n+1}2^i\\ &\;\;\vdots\\ &=B(1)+\sum_{i=n+2-(n-1)}^{n+1}2^i\\ &=3+\sum_{i=3}^{n+1}2^i\\ &=3+\sum_{i=0}^{n+1}2^i-\sum_{i=0}^22^i\\ &=3+\left(2^{n+2}-1\right)-7\\ &=2^{n+2}-5\;. \end{align*}$$
If you’re in any doubt about the calculation, you can prove the result by induction on $n$: certainly $B(1)=3=2^{1+2}-5$, and if $B(n)=2^{n+2}-5$, then
$$B(n+1)=B(n)+2^{n+2}=2\cdot 2^{n+2}-5=2^{n+3}-5\;,$$
as desired.
This does not actually show that this procedure gives the minimum possible number of moves, but it does show that the transfer is always possible in $2^{n+2}-5$ moves, and it can be shown that this is the best possible result.
Added: This is going to be a bit informal rather than entirely rigorous.
To see that this is the best possible result, let the two largest disks be $\top$ (on top) and $\bot$ (on the bottom), and let the tower of $2(n-1)$ smaller disks be $T$. At some point we must move $\bot$ to peg B; assuming that we do so directly, rather than by way of peg C, this requires getting $\top$ and $T$ to B. If $m$ is the minimum number of moves needed to accomplish this, we’ll need at least $2m+1$ moves to transfer everything from A to B — more, if $T$ doesn’t end up in the right order. Getting $\top$ and $T$ from A to C requires getting $T$ to B, where it’s out of the way, so that we can move $\top$ from A to C; by definition this requires a minimum of $A(n-1)$ moves. After moving $\top$ to C, we must still move $T$ to C on top of $\top$, so $m=2A(n-1)+1$. Note that this actually leaves the disks in $T$ in the correct order, since we’ve reversed the order of the two bottom disks of $T$ twice while leaving the other pairs alone.
This means that we need at least
$$2m+1=4A(n-1)+3=4\left(2^n-2\right)+3=2^{n+2}-5$$
moves to transfer the entire stack from A to B. We’ve already seen that the task can be accomplished in this many moves, so this is the best possible result.
Note that we now have a second algorithm that also produces the best possible result: