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.