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 towers of hanoi

Tower 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.

Solution:\textbf{Solution:}Let TnT_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=1n = 1 then T1=1T_1=1, since one disk can be transferred to the destination tower in 1 step.

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

hanoi2 hanoi2

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

hanoi3 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 n1n-1 disks from the source tower to the auxilliary tower using Tn1T_{n-1} steps, then we the remaining largest disk from the source tower to the destination tower using 1 step.Then we move the n1n-1disks from the auxilliary tower to the destination tower using Tn1T_{n-1} steps and we are done!! So we obtain the recursive relation Tn=2Tn1+1T_n = 2T_{n-1}+1 and we have a base case T1=1T_{1}=1.

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

Challenge 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??

Generalization:\textbf{Generalization:}Looks like we can solve the problem if there are 33 pegs but what if there are rr 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 rr pegs which is presumed to be optimal.

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

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

2.2.Without disturbing the peg that now contains the top kk disks, transfer the remaining nkn-k disks to the destination peg, using only the remaining r1r-1 pegs, taking Tnk,r1T_{n-k,r-1} moves.

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

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

Applications:\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 box

Problems and challenges:\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

Challenge 2.\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.

Note by Eddie The Head
7 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 2

paragraph 1

paragraph 2

[example link]( 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

3507252276543.7 year

Siddharth Bhalawat - 6 years, 9 months ago

Log in to reply

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

Akhilesh Chobey - 7 years, 2 months ago

Log in to reply

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

Varun Singla - 7 years, 1 month ago

Log in to reply

yeah thanks

Akhilesh Chobey - 7 years, 1 month ago

Log in to reply

Since we have logically shown it holds for n terms it means it also holds for (n-1) by the same 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....

Eddie The Head - 7 years, 2 months ago

Log in to reply

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.

Sharky Kesa - 7 years, 5 months ago

Log in to reply

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

GS Vamsi Krishna - 7 years, 2 months ago

Log in to reply

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

Eddie The Head - 7 years, 5 months ago

Log in to reply

For challenge 2 I got 584942417355.072 years

Tan Li Xuan - 7 years, 5 months ago

Log in to reply

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

Eddie The Head - 7 years, 5 months ago

Log in to reply

Excellent post!

Sagnik Saha - 7 years, 5 months ago

Log in to reply

Thanks! :)

Eddie The Head - 7 years, 5 months ago

Log in to reply

Amazing post! Love the diagrams...;)

Rohan Rao - 7 years, 5 months ago

Log in to reply

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

Eddie The Head - 7 years, 5 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...