The Tower Of Hanoi Problem – Here’s Everything You Need To Know

Jul 28, 2020

The Tower of Hanoi is a mathematical puzzle or a game that consists of 3 rods as well as a number of flat disks of various sizes that can be slipped over any rod among the 3. The Tower of Hanoi game set-up looks like the way it’s shown in this image depicted below.
 
Tower of Hanoi set-up with 8 disks     

According to legend, the temple priests are ordered to shift a tower containing 64 fragile golden disks from a section of the temple to another one. There was a catch.
The priests have to transfer disks one at a time. The disks have to be arranged in order.

No two disks are similar in size. The largest disk should be at the bottommost position with the smallest on the topmost position of the order. This was mainly done because of a reason. The disks were fragile and hence a larger disk should not be placed on a smaller one to prevent damage or breakage of disks. There’s one intermediate rod where the disks can be placed temporarily.  The legend also goes that as soon as the last disk will complete its journey from the initial spot to the final spot, the world will be destroyed. But don’t worry about that. It would take them an estimated (2^64-1) seconds or 585 billion years for completion. Plus it’s just a legend.

But how did we calculate the time that said 585 billion years for completion? We’ll see to it later in this article. We’ll determine the number of moves required for completion of the moves by deriving a formula. You’ll also see that if each move is done even in 1 second (shortest possible time), we’ll see that the time taken will be roughly 585 billion years.  

Before we start delving deeper into this topic, let’s make something clear first. We’ll sue the same principle explained in the legend above minus the destruction of earth of course and the number of disks. The number of disks that we’ll use for explanation will be from 1 to 3. But after deriving the formula, you can use the same for calculating the number of moves required for transferring any number of disks from one position to another with the intermediate position in between.

Note: It’s not compulsory for the player to use the intermediate rod. Although s/he will have to take the help of the intermediate rod if the number of disks are more than 1. You’ll see that below.

The problems

First problem

Number of disk used is 1. The problem is represented in the figure below. The disk has to be transferred from position A to C. B’s the intermediate rod.

Image courtesy - http://mathforum.org/dr.math/faq/faq.disk1.gif

Here only 1 move is required and the intermediate rod is not used at all. Red disk is moved directly from A to C.
Number of move =1.

Second problem

Number of disks used are 2. Refer to the image given below. Disks are placed at rod A and have to be transferred to C as usual with the largest at the bottom and the smallest at the top.

Image courtesy- http://mathforum.org/dr.math/faq/faq.disk2.gif

(1)    Blue disk is moved from A to B.
(2)    Red disk is moved from A to C.
(3)    Blue disk is moved from B to C.

Number of moves= 3.

Third problem

Number of disks used are 3. The image is provided below. Disks have to be transferred from A to C with the largest at the bottom and the smallest at the top.

Image courtesy -  http://mathforum.org/dr.math/faq/faq.disk3.gif

(1)    Green disk is moved from A to C.
(2)    Blue disk is moved from A to B.
(3)    Green disk is moved from C to B.
(4)    Red disk is moved from A to C.
(5)    Green disk is moved from B to C.
(6)    Blue disk is moved from B to C.
(7)    Green disk is moved from A to C.

Number of moves= 7.

Now we’ll stop here because the information above is enough to get a formula.

Recursive Pattern Formula

A recursive pattern formula is a formula that tells the starting number of any pattern and the ways through which the pattern continues.
The other numbers in the same pattern can be found out through the application of the recursive pattern formula. We’ll try to derive the recursion formula from the information that we found above.

For 1 disk, number of moves required (M1) =1.

For 2 disks, number of moves required (M2) =3.

M2= (2*M1) +1= (2*1) + 1= 3.

For 3 disks, the number of moves required (M3) = 7.

M3= (2*M2)+1= (2*3)+1= 7.

So the formula derived should be: Required move= (2*Previous move) +1.

Thus, you’ll be able to calculate the successive required moves if you know the previous moves required. Example:

For 4 disks,

Required moves= 2*7+1 = 15.

For 5 disks,

Required moves= 2*15 +1 = 31.

But this can be a problem. Say for example, you are asked to calculate the number of moves required to transfer 60 disks from A to C.
You have to start your calculation from start or from the place from which the value is known to you. You have to start from disk 1 that takes requires only 1 movement to complete its journey from A to C. After that you have to go for successive calculation until you reach the required value. Hence, we have to find out an explicit pattern formula.

Explicit Pattern Formula

An explicit pattern formula is one that enables one to calculate any term in a pattern without the knowledge of the immediate previous term.

Disks(n) Moves
1 1
2 3
3 7
4 15
5 31

 

We can already find a pattern through the information provided to find out an explicit pattern formula.

Number of moves= (2^n) -1

Apply it and you’ll find the exact same information on the right hand side column.

When disks = 4,

Number of moves= (2^4) - 1= 15.

Tower of Hanoi problems are pretty interesting and fun to engage with. These problems will help you a lot in grasping important math concepts based on iterations, sequences, etc. After-school on-line mathematics tutorials can also help you out immensely if you want to delve deeper into the subject matter. That’s all for today but before signing off we will want to keep our promise about how we determined the time of completion of the task, the task that was assigned to the priests of transferring fragile golden disks from one section of the temple to another. We said the time taken should be roughly 585 billion years.

Numbers of golden disks involved were 64.

Therefore number of moves= (2^64)-1= 18,446,744,073,709,551,615.

Do you have anything more to say? That’s a humungous number, isn’t it? Clearly, the person who gave the order had no intention of finishing the task. If each move is done in 1 second (which is still impossible unless they had a teleporting machine), the time taken should be 18,446,744,073,709,551,615 seconds or 585 million years. So, you do not have to worry about the world getting destroyed because you still have a lot of time in your hands. That’s it for today. Adios!

Article Posted in: Information and Examples

Sid

Sid writes educational content periodically for Wizert and backs it up with extensive research and relevant examples. He's an avid reader and a tech enthusiast at the same time with a little bit of “Arsenal Football Club” thrown in as well. He's got more than 5 years of experience in technical content framing, digital marketing, SEO and graphic designing.

Related Posts