2
$\begingroup$

For example a line with '1111' represents a disc with diameter of length 4. Similarly a line with '111' represents a disc with diameter of length 3.

Below is the representation of a tower that has 5 discs. ground disc has a diameter 9, disc '2' d=5, disc '3 and 4' d=3 and disc '4' has d = 1.

$1$

$111$

$111$

$ 11111$

$111111111$

How Many moves will it take to move these kind of towers?

$\endgroup$
  • $\begingroup$ You could represent the starting position more efficiently as 12234. $\endgroup$ – TonyK Nov 24 '15 at 19:06
6
$\begingroup$

If you have two equal disks, then as long as they're on different pegs, you can't ever move any larger disk. So it makes no sense to stay in this situation longer than necessary. The optimal solution must therefore be to keep all disks of the same size together, only splitting them up temporarily when you need to move all of them from one peg to another, which then needs to happen one at a time.

This reduces the problem to the usual Towers of Hanoi problem with one disk per size class. You just need to multiply the number of moves each disk makes in the standard problem (namely $2^n$ where $n$ is the number of larger sizes) by the number of disks of a given size, and then add everything together.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

It is possible to move such a tower faster: First "merge" equal sized disks into one, then solve the problem for the reduced number of disks, then replace each move of a disk obtained by merging $k$ disks with moving the $k$ merged disks. In your example, we first need to move $4$ disks, which takes $2^2-1=15$ moves. Among these, $4$ moves concern the "III" disk, and get replaced with $8$ single moves, resulting in a total of $15-4+8=19$ moves (instead of $31$ moves).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

After considering all the suggested methods and some calculations I came up with this recursive call:

We all know that when there are no blocks of similar width we use the call : $T_{n+1} = 2T_{n}+1$ So some insight will clearly tell you that in case the block is of same width as the previous it's call would be $T_{n+1} = T_{n}+1$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You need to specify that you are counting down from the top and that you use the coefficient $2$ when the disk differs in size from the previous and $1$ when they agree. $\endgroup$ – Ross Millikan Jan 22 '16 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.