The Solution to the Towers of Hanoi

0 Conversations

The Problem



The towers of Hanoi starts with three pegs, with different sized discs on the left peg (as shown below):




There are two rules for moving the discs:

    Only one disc may be moved at once.
    A disc may only be moved onto an empty peg, or onto a larger sized disc (i.e. a larger disc cannot be placed on top of a smaller one).

The aim is to move the whole tower from the left peg onto the right peg in the smallest possible number of moves. The number of discs can vary, but the greater the number of discs the more moves are required to complete the puzzle, and the more difficult the puzzle becomes.


This is the solution to the problem when there are three discs:

0 Moves

1 Move

2 Moves

3 Moves

4 Moves

5 Moves

6 Moves

7 Moves


The fewest number of moves in which the puzzle with three discs can be completed is seven moves.


The problem therefore is this:

What is the fewest number of moves in which the
puzzle can be completed for a given number of discs?

The Solution



The solution to this problem can be found by beginning with the simplest case, with just one disc:

0 Moves


To complete the puzzle in the fewest number of moves, the disc can simply be moved from the left peg to the right peg.

1 Move


The solution to the puzzle with one disc is one move. This can now be used to solve the puzzle for two discs:

0 Moves


To complete the puzzle in the fewest number of moves, the small disc must be moved onto the middle peg (to allow the bottom disc to be moved onto the right peg). This first move is the same as the solution to the puzzle with one disc, but this time the disc is being moved to a different peg.

1 Move


The next move is to move the large disc to the right peg.

2 Moves


The puzzle can now be completed by moving the small disc onto the right peg. This move is again the same as the solution to the puzzle with one disc, but from a different peg.

3 Moves


The solution to the puzzle with two discs is three moves. For the puzzle with two discs to be completed, the move to complete the puzzle with one disc must be made to move the small disc onto the centre peg, followed by a move of the large disc onto the right peg, followed again by the move to complete the puzzle with one disc to move the small disc onto the right peg. In other words, to complete the puzzle with two discs, the move to complete the puzzle with one disc must be made twice, plus an extra move (to move the large disc).


This principle is the same for larger numbers of discs. For the puzzle with n discs to by completed, the combination of moves that are used to complete the puzzle with n - 1 discs must be made to move all of the discs except the largest one onto the centre peg. Then a single move of the largest disc onto the right peg can be made. To complete the puzzle, the combination of moves to complete the puzzle with n - 1 discs must be made to move all of the discs from the centre peg onto the right peg. Therefore, the number of moves which it takes to complete the puzzle with n discs is twice the number of moves it takes to complete the puzzle with n - 1 discs plus 1. If the number of moves to complete the puzzle with n discs is written as mn then:

mn = 2mn - 1 + 1



Or written the other way around:

mn = 1 + 2mn - 1



Using this equation, the following must also be true:

mn - 1 = 1 + 2mn - 2



This can be substituted into the original equation to give:

mn = 1 + 2( 1 + 2mn - 2 )



Multipltying out the brackets gives:

mn = 1 + 2 + 4mn - 2



Again, using the original equation, the following must be true:

mn - 2 = 1 + 2mn - 3



This can be substituted into the equation above, and after multiplying gives:

mn = 1 + 2 + 4 + 8mn - 3



These substitutions can be continued. It can be seen that this is a sum of successive powers1 of 2. Therefore this equation can be rewritten as:

mn = 20 +  21 + 22 + 23mn - 3



The substitutions can be continued until the term m1 is reached. Since the coefficient2 of the term mn - a can be seen to be 2a, the coefficient of the term m1 (which is the same as mn - (n - 1) ) must be 2n - 1. Therefore, after further expansions the following equation can be written:

mn = 20 +  21 + 22 + 23 + 24 + … + 2n - 1m1


m1 is known to be 1 (since it takes one move to complete the puzzle with one disc). Therefore:
mn = 20 +  21 + 22 + 23 + 24 + … + 2n - 1



This equation says that mn is equal to a sum of consecutive powers of two, from the power 20 to the power 2n - 1. This summation can be proved3 to be equal to 2n - 1. Therefore, the solution is:

mn = 2n - 1



Therefore the fewest number of moves in which the puzzle with n discs can be completed is 2n - 1 moves.
12 to the power of n means 1 times 2 n times. For example, 2 to the power 4 equals 1 x 2 x 2 x 2 x 2 and is written as 2 ^ 4 or 24.2Multiple of. The coefficient of 8mn - 3 is 8.3Proof by induction can be used to prove this.

Bookmark on your Personal Space


Conversations About This Entry

There are no Conversations for this Entry

Entry

A1123200

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry


Written and Edited by

References

h2g2 Entries

Disclaimer

h2g2 is created by h2g2's users, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the Not Panicking Ltd. Unlike Edited Entries, Entries have not been checked by an Editor. If you consider any Entry to be in breach of the site's House Rules, please register a complaint. For any other comments, please visit the Feedback page.

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more