1+3 Towers of Hanoi

Question

There are four pegs in a row; let's call them A, B, C, and D from left to right. Peg A has a stack of $n$ differently sized disks, sorted in size so the smallest disk is at the top. All other pegs are empty. The goal is to move all the disks to peg D, following the rules:

• You can move only one disk at a time.
• Disks can only be moved from the top of a stack to the top of another stack.
• You cannot put a larger disk over a smaller one.
• Once a disk leaves peg A, it cannot be moved back to peg A.
• You can move disks freely between pegs B, C, and D.

Describe an optimal (i.e. minimizing the number of steps) sequence of moves. What are the number of moves for $n=5$ and $n=6$?

Answer 1

Any solution will at one point have the two largest disks on their own pegs and all the others on the third one (the fourth peg (A) is out once the largest disk has been moved). WLOG we move the two largest disk only once the others have been stacked to their single peg (whatever sequence of moves leads there works regardless of where the two largest disks are). The full sequence of moves is therefore an optimal solution for the n-2 problem + 3 moves to move the two largest disks to their final destination + an optimal solution to the n-2 classic (no fourth peg) problem.

From this we get the recursion formula

$X_1=1,X_2=3,X_n=X_{n-2}+2+2^{n-2}$

with solution

$X_{2m}=2m+\frac {4^m-1} 3,X_{2m+1}=2m+2\times\frac {4^m-1} 3+1$.

UPDATE

As @PM2Ring points out in the comments there is a prettier way of writing the closed formula:

$X_n=n+\left \lfloor \frac {2^n} 3 \right \rfloor$

The first few values are

1,3,5,9,15,27,49,93,179,...