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$?


1 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


with solution

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


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


  • $\begingroup$ oeis.org/A340849 $\endgroup$
    – Florian F
    Commented Jan 24 at 12:54
  • 1
    $\begingroup$ There's a slightly more symmetrical way to write the closed forms. It's surprising that they aren't given on OEIS. sagecell.sagemath.org/… $\endgroup$
    – PM 2Ring
    Commented Jan 24 at 22:17
  • 1
    $\begingroup$ A340849 has been updated with the Hanoi variant reference and the simplified formulas. $\endgroup$
    – Bubbler
    Commented Feb 21 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.