0
$\begingroup$

Here is the question:

There are $m$ different sizes of disks and exactly $n_k$ disks of size $k$. Determine $A(n_l,. . . , n_m)$, the minimum number of moves needed to transfer a tower when equal-size disks are considered to be indistinguishable.

First, I figured out the number of moves needed for each disk when there are $n$ disks. I found out that each disk moves the same amount regardless the total number of disks, so $f(n)=t(n)-t(n-1)$.

$f(n)$ is the minimum number of times the disk moves, starting from the bottom and going up. For example: $f(1)$ is for the most bottom disk and $f(2)$ is the one above it etc.

$t(n)$ is the minimum number of moves needed to move all n disks from peg A to peg B.

After this, I just did sum from $k=1$ to $n$, the number of disks, of $(t(k)-t(k-1)) \cdot n_k$.

Is this the right answer?

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

It isn't the right answer because it isn't an answer. It is a plan to find the answer. Why do you talk of $A(n_l,. . . , n_m)$ when there are only three parameters in the problem-$m,k$ and $n$? I presume $k$ is the position in the list of sizes where you have multiple disks, so there are $m+n-1$ disks in total. Stating the question carefully is often a good step toward the solution.

Assume we are doing Tower of Hanoi with $m$ sizes of disk and there are $n$ disks of the $k^{\text{th}}$ smallest size. These disks can be stacked on on another in any order, but cannot be stacked on any smaller disk. Hint: you should convince yourself that all the matching disks need to stay together. Each time in the standard Tower of Hanoi that you would move a disk of size $k$, you make $n$ moves instead of $1$. How many times does that disk move in the standard Tower of Hanoi? The largest disk only moves once, the next moves ???

$\endgroup$
4
  • $\begingroup$ Inside the sum is the number of times each disk size has to move. That sums up to all the disks. Whats wrong with the answer? $\endgroup$
    – Armon Safai
    Aug 12, 2015 at 4:27
  • $\begingroup$ The approach seems fine, but there is no final answer provided. The answer is clearly a function of $m$, but $m$ does not appear in your approach. Your $t(n)$ should be $t(n,m,k)$ because it will depend on all three variables. I described the dependence on $n$, the rough dependence on $m$ is not hard, but you need to think about the dependence on $k$ $\endgroup$
    – Ross Millikan
    Aug 12, 2015 at 4:45
  • $\begingroup$ but why does m have to be included if i can give the answer to the problem without it? The final answer is the sum of k=1 to k=n of [t(k)-t(k-1)]*n(small k). Idk why this doesn't answer the question. $\endgroup$
    – Armon Safai
    Aug 12, 2015 at 5:20
  • $\begingroup$ Now I see that you are allowing for more than one disk of each size, not just more than one of one size. Then there will be $m=\sum_kn_k$ disks in total. That explains your $A(...)$. If $t(n)$ is the number of moves in a classic Tower of Hanoi, it is known to be $2^n-1$, which you don't state. The expression is correct, but you do not incorporate the known $t(n)$, so the expression could be simplified. $\endgroup$
    – Ross Millikan
    Aug 12, 2015 at 14:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .