Waste less time on Facebook — follow Brilliant.
×

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

\(\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

hanoi2

If \(n=3\),Then \(T_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 \(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

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.

Note by Eddie The Head
3 years, 7 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

For challenge 2 I got 584942417355.072 years Tan Li Xuan · 3 years, 7 months ago

Log in to reply

@Tan Li Xuan So we don't have to worry about the earth being destroyed :D Eddie The Head · 3 years, 7 months ago

Log in to reply

Amazing post! Love the diagrams...;) Rohan Rao · 3 years, 7 months ago

Log in to reply

@Rohan Rao 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 · 3 years, 7 months ago

Log in to reply

3507252276543.7 year Siddharth Bhalawat · 2 years, 10 months ago

Log in to reply

Excellent post! Sagnik Saha · 3 years, 7 months ago

Log in to reply

@Sagnik Saha Thanks! :) Eddie The Head · 3 years, 7 months ago

Log in to reply

Awesome work.!Thank You.But can you please tell me why is \(T_{n - 1}\)= \(2T_{n - 2}\)+1 ?? Akhilesh Chobey · 3 years, 3 months ago

Log in to reply

@Akhilesh Chobey 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.... Eddie The Head · 3 years, 3 months ago

Log in to reply

@Akhilesh Chobey Hah. This is like listening to all the ramayana and asking who is ram. Varun Singla · 3 years, 3 months ago

Log in to reply

@Varun Singla yeah thanks Akhilesh Chobey · 3 years, 3 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 · 3 years, 7 months ago

Log in to reply

@Sharky Kesa 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)\) .. Eddie The Head · 3 years, 7 months ago

Log in to reply

@Sharky Kesa When 4 circles intersect the number of regions formed are 13 which is not of the for 2^n-1 GS Vamsi Krishna · 3 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...