Tower of Hanoi with a restriction of no direct transfers

We need to solve the Tower of Hanoi problem, with this additional restriction : direct moves between the origin and destination towers is disallowed. All other restrictions still apply  as-is.

For example, if a single disk is to be moved from Tower A to Tower B (using Tower C), then moving the disk directly from A to B is not allowed. The disk must be first transferred to Tower C and then to Tower B.

The purpose is to find the shortest sequence / number of moves we can do this in : 
  • T(0) = 0 (basis case, nothing to move)
  • T(1) = 2 (from above)
  • T(n-discs) = ???
Source : Concrete Mathematics (2nd Edition) Ex. 1.2

4 comments:

Unknown said...

If we work out the small cases, we see that :

T(1) = 2
T(2) = 8
T(3) = 26

Also, to transfer the 'n'th disc from Tower A to Tower B, we must first transfer the previous 'n-1' discs from Tower A to Tower B. Now, since direct transfers are forbidden, the approach will be this :
1.> move the 'n-1' discs from Tower A to Tower B
2.> move 'n'th disc to Tower C
3.> move 'n-1' discs from Tower B to Tower A
4.> move 'n'th disc from Tower C to Tower B
5.> Now recursively transfer the 'n-1'th disc from Tower A to Tower B

From above we can see that

T(n) = T(n-1) + 1 + T(n-1) + 1 + T(n-1)

which means
T(n) = 3 * T(n-1) + 2
solving this :
T(n) + 1 = 3 * [T(n-1) + 1)
using U(n) = T(n) + 1, we get
U(n) = 3*U(n-1)
which can be solved to be :
U(n) = 3^n (for n > 0)

Hence,
T(0) = 0 and
T(n) = 3^n - 1 (for n > 0)

Anonymous said...

Hi

Do you have any pseudocode for this?

Unknown said...
This comment has been removed by the author.
DUŠKA ALŽBĚTA said...

I would highly recommend Mr Benjamin services to any person in need of financial help and they will keep you on top of high directories for any further needs. Once again I commend yourself and your staff for extraordinary service and customer service, as this is a great asset to your company and a pleasant experience to customers such as myself. Wishing you all the best for the future.Mr, Benjamin is the best way to get an easy loan,here is their email..  247officedept@gmail.com    Thank You for helping me with loan once again in my sincerely heart I'm forever grateful.

 
Stats