Hello to everyone,
I have to find an optimal k for the following recurence:
T(n, 4) = 2^(n-k+1) + 2^k - 3
The above expression answers the question of how many moves, at least, are required for the problem of Hanoi with n disks and 4 towers to be solved. The problem was given to me as follows:
Given 4 towers and n disks, the n disks must go from tower A to tower D. First, I have to take n-k disks from A to B via C (cannot use D). Second, take k diskc from A to D via C (cannot use B). Finally, move n-k disks from B to D.
What I am most concerned about is an expression for the optimal k.
Can anyone help me please?
Tasos