# Stacking Problems (a generalized Tower of Hanoi)

In this note we will discuss a few ways to efficiently stack a collection of elements having a few constraints in mind.

towers of hanoi

$\textbf{Tower of Hanoi:}$It consists of three pegs fastened to a stand, and of eight circular discs of wood or cardboard each of which has a hole in the middle so that a peg can be put through it. These discs are of different radii, and initially they are placed all on one peg, so that the biggest is at the bottom, and the radii of the successive discs decrease as we ascend: thus the smallest disc is at the top. This arrangement is called the Tower. The problem is to shift the discs from one peg to another in such a way that a disc shall never rest on one smaller than itself, and finally to transfer the tower (i.e. all the discs in their proper order) from the peg on which they initially rested to one of the other pegs.

$\textbf{Solution:}$Let $T_n$ denote the number of ways to transfer n disks from the source tower to the destination tower. Let us consider few base cases:

If $n = 1$ then $T_1=1$, since one disk can be transferred to the destination tower in 1 step.

If $n=2$,Then $T_2 = 3$,The steps to be performed are shown in the diagram below

hanoi2

If $n=3$,Then $T_3 = 7$,The steps to be performed are shown in the diagram given below

hanoi3

Now let us try to obtain a relation between the number of steps for differrrent values of n.

Suppose there are n disks,The at first we move the $n-1$ disks from the source tower to the auxilliary tower using $T_{n-1}$ steps, then we the remaining largest disk from the source tower to the destination tower using 1 step.Then we move the $n-1$disks from the auxilliary tower to the destination tower using $T_{n-1}$ steps and we are done!! So we obtain the recursive relation $T_n = 2T_{n-1}+1$ and we have a base case $T_{1}=1$.

So now we obtain $T_n = 2T_{n-1}+1$.Substituting $T_{n-1} = 2T_{n-2}+1$,we get $T_n = 2^{2}T_{n-2}+2+1$ Continuing in this way ultimately we will obtain the sequence $T_n = 2^{n-1}T_1+2^{n-2}+.......+2^{2}+2+1$ Substituting the value of the base case that is $T_1 = 1$ we obtain $T_n = 2^{n-1}+2^{n-2}+.......+2^{2}+2+1$ Using the sum of the geometric series we have the relation $\boxed{T_n = 2^{n}-1}$

$\textbf{Challenge 1.}$ can you give the logic behind why this is the minimum number of steps in which this puzzle can be solved??

$\textbf{Generalization:}$Looks like we can solve the problem if there are $3$ pegs but what if there are $r$ number of pegs??Then what would we do?? The best possible solution with four pegs(let alone more pegs) is still an open problem.The case with four pegs is called the Reve's puzzle.

But there is an algorithm for solving $r$ pegs which is presumed to be optimal.

$\textbf{Frame-Stewart algorithm:}$Let $n$ be the number of disks and $r$ be the number of pegs and $T_{n,r}$ be the number of steps needed to move all the disks from one tower to another.

$1.$For some $k$, $1 \le k < n$, transfer the top k disks to a single peg other than the start or destination pegs, taking $T_{k,r}$ moves.

$2.$Without disturbing the peg that now contains the top $k$ disks, transfer the remaining $n-k$ disks to the destination peg, using only the remaining $r-1$ pegs, taking $T_{n-k,r-1}$ moves.

$3.$Finally, transfer the top k disks to the destination peg, taking T_{k,r} moves

The entire process takes $2T_{k,r}+T_{n-k,r-1}$ moves But the of $k$ here is to be made by trying out all possible values so that it is minimum.There is no generalized rule for it .

$\textbf{Applications:}$The Tower of Hanoi is also used as a Backup rotation scheme when performing computer data Backups where multiple tapes/media are involved.

It is also used in psychological research and as a test to evaluate frontal lobe deficits.

So from today onward if you ever find people struggling with arrangement of boxes(like this guy below) and stuff then please help them out :D

box

$\textbf{Problems and challenges:}$

Here are a few problems for you to try. I request you to try them immediately after understanding the material presented here.Look forward to my next post :) and post the answer to the challenge questions in the comments section but not the rated problems.

Level 3

Level 5

$\textbf{Challenge 2.}$In the great temple at Benares, beneath the dome which marks the centre of the world, rests a brass-plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunder-clap the world will vanish.If the priest take one second to move one disk find the number of years in which the world will get destroyed.

5 years, 7 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

For challenge 2 I got 584942417355.072 years

- 5 years, 7 months ago

So we don't have to worry about the earth being destroyed :D

- 5 years, 7 months ago

Amazing post! Love the diagrams...;)

- 5 years, 7 months ago

Thanks a lot :) ..Also check out my note on Fermat's Method of infinite descent..I also tried to put some interesting diagrams in that one..... click here

- 5 years, 7 months ago

Excellent post!

- 5 years, 7 months ago

Thanks! :)

- 5 years, 7 months ago

3507252276543.7 year

- 4 years, 11 months ago

Isn't this also related to the number of regions of intersecting circles. If there is 1 circle, there is 1 region. If two circles intersect, there are 3 regions. If there are three circles intersecting each other, there are 7 regions and so forth.

- 5 years, 7 months ago

Nice observation but not quite...as far as i remember the recursive relation for intersecting circles is : $S_n = S_{n-1} + 2(n-1)$ ..

- 5 years, 7 months ago

When 4 circles intersect the number of regions formed are 13 which is not of the for 2^n-1

- 5 years, 4 months ago

Awesome work.!Thank You.But can you please tell me why is $T_{n - 1}$= $2T_{n - 2}$+1 ??

- 5 years, 4 months ago

Since we have logically shown it holds for n terms it means it also holds for (n-1) by the same logic....it may also be interpreted as only putting n-1 in place of n in a general relation,..., if you still have doubt feel free to ask....

- 5 years, 4 months ago

Hah. This is like listening to all the ramayana and asking who is ram.

- 5 years, 4 months ago

yeah thanks

- 5 years, 3 months ago