The Tower Of Hanoi
Here is the famous problem called the Tower of Hanoi:
In the diagram above, there are three towers: (left to right) A, B, and C. Suppose there are a certain number of discs in tower A, arranged in ascending order of their sizes from top to bottom. You are required to transfer them to tower C, with or without the help of tower B. But you have to follow the following rules while transferring them:
1) You can pick only one disc from a tower at a time.
2) A larger disc can't be placed upon a smaller disc.
(For example, if there were two discs in tower A, then, You may follow the following procedure:
1. First disc(A to B) 2. Second disc(A to C) 3. First disc(B to C).
Hence, the total number of steps required=
.)
Then determine the number of steps required to transfer
discs.
The answer is 1023.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Let S(n) be the number of steps required if there are 'n' discs. We also know that the number of steps required for 2 discs;S(2) is 3. Similarly for 3 discs, S(3) = 7.
From this we can deduce that S(n) = (2^n) - 1. Example: S(2) = (2^2) - 1 = 3 or 2² - 1 = 3.
Hence for 10 discs; S(10) = (2^10) - 1 S(10) = 1023.