Bicolor Towers of Hanoi (Solution)
Nathan Bowler
13 February, 2004
As I was browsing ctk, I happened upon the page Bicolor Tower of Hanoi. I don't know how general the 'more general formulations' you were thinking of were, but I tried the obvious one: putting lots of disks into the towers. So here is my solution to ndisk bicolor tower of hanoi:
Notation first: Since many formulas will be of this form, let (a, b, c) denote the expression
To move a disk of a particular size, it is necessary for all disks of lower size to be stacked up in a pile. Let the number of moves necessary to move such a pile with 2n disks in it from one pin to another be T_{n}. From the solution to the standard hanoi problem, we have T_{n} = 2^{n+1}  2. That is:

It is also worthwhile to see how long it takes to form such a tower. Such a tower may (when first formed) be on pin 2: let the minimal number of moves to reach this situation be B_{n}. Let the minimal number of moves to reach the other such situation (the tower on top of a stack on pin 1 or 2) be A_{n}. By induction on n, you may obtain:

Finally, cosider the final two layers together with the tower above them. It is necessary to swap the bases, get the next two the right way around, and do this moving the tower as little as possible. The best solution (8 tower moves, 11 other moves) also saves a little time by finishing with the tower in position A, since A_{k} is in general less than B_{k}. The sequence, starting with the tower on place 0 and considering the tower as a single object, is:
12.02.01.20.21.01.02.10.12.12.02.10.21.20.20.10.21.02.01
Handily, now that the bottom two layers are right there is no more need to worry: The other layers may be arranged as we wish. So the least number of moves for towers with n disks is L_{n}, satisfying L_{n} = A_{n2} + B_{n2} + 8·T_{n2} + 11. That is:

These two are the same: L_{k} = 11·(2^{k1}  1)  3(k2) for k sufficiently large. Of course, for n <= 2 the values are different: L_{0} = 0, L_{1} = 3, L_{2} = 10. However, it suggests there is a nicer way to get the formula, but I don't know it. It gives an answer of 11·3  3 = 30 for k = 3 and the string is
Is that right? Anyway, if you generalised the problem any more it would be hard to get exact values, just upper and lower bounds.
 Tower of Hanoi
 Tower of Hanoi, the Hard Way
 Bicolor Towers of Hanoi
 Bicolor Towers of Hanoi, Solution
 3Colors Tower of Hanoi
 3Colors Tower of Hanoi (Algorithm)
 Hanoing
 Sierpinski Gasket and Tower of Hanoi
Contact Front page Contents Up
Copyright © 19962018 Alexander Bogomolny66983018