Mathematical Analysis of Tower of Hanoi Problem

Tower of Hanoi is a mathematical puzzle invented by French Mathematician Édouard Lucas in 1883.  There is a story about it being associated with Indian temple named Kashi Viswanath temple about which you can read here.

Now, let's jump into the problem.

Picture source: Wikipedia

There are three rods as shown in the figure above.  One of the rods has the discs arranged in the order of their size.  The discs are arranged upwards in the decreasing-size manner.  Our job is to shift whole set of discs to any other rod following the following rules.

• Only one disc can be moved at a time.
• Never can a larger disc sit above smaller disc.
• Only uppermost disc can be moved from the set of discs.

Complying to these rules, we should shift the whole set of discs from first rod to any other rod.  There can be any number of discs.  Our task is to come for general solution for any 'n' number of discs.

Solving for a single disc or a couple of discs is a piece of cake.  With a little brainstorming, we could get over three discs too.  The difficulty arises when we increase the number of discs to a greater value.  We are going to find solution for any number of discs by its mathematical analysis. 

We use a technique called recursion here to solve the problem.  If you don't know about recursion, click here and start learning.  Recursion is powerful tool in the field of computer programming.

For a single disc, we can simply shift that one disc from first rod to any other rod.  It takes one step.

For a couple of discs, we shift upper disc into third rod and lower disc into second rod.  Then, finally we shift third-rod-disc into second rod.  In this way, we solve for a couple of discs.

Now, let's solve for three discs.  We shift the upper two discs into third rod using the method we said for two discs.  Then we shift lowest disc into second rod.  Finally, we shift those two discs placed at the third rod to the second rod.  Tada!  We solved it.

In this way, for n discs, we shift (n-1) discs from first rod to third rod and then shift lowest disc to second rod.  We then shift all discs of third rod into the second one and solve it completely.

So for n discs, we need to shift (n-1) discs two times and last disc one time.  Let's represent the steps taken by 'n' discs as f(n).

So, f(n) = 2f(n - 1) + 1

Also, f(n - 1) = 2f(n - 2) + 1

So, f(n) reduces to:

In this way,

Now, let's see how many discs we can solve at most in whole of our life.

Let's assume that we can do one step in one second, and we solve this puzzle every-time without doing other things like sleeping, etc.

Let's assume we may live further 100 more years.  That means 3153600000 seconds.

So,

Therefore, at most we can solve 31-discs Tower of Hanoi.

It may not seem obvious at first glance that Tower of Hanoi is so many steps involving when n starts to increase from 3.  But this is what it is!

If you could solve anywhere near 30-odd-discs Tower of Hanoi, you are into making the history.