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 n-disk bicolor tower of hanoi:

Notation first: Since many formulas will be of this form, let (a, b, c) denote the expression (a·4ⁿ + b)/3 + c·n. I shall refer to moves by the pin the disk is taken from followed by the pin it goes to. So the solution to normal tower of hanoi with 3 disks in this notation is 02.01.21.02.10.12.02.

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ⁿ⁺¹ - 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_n-2 + B_n-2 + 8·T_n-2 + 11. That is:

These two are the same: L_k = 11·(2^k-1 - 1) - 3(k-2) for k sufficiently large. Of course, for n <= 2 the values are different: L₀ = 0, L₁ = 3, L₂ = 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

10.12.02.02.01.20.20.21.01.01.02.10.10.12.12.02.02.10.21.21.20.20.10.10.21.02.02.01.20.21.

Is that right? Anyway, if you generalised the problem any more it would be hard to get exact values, just upper and lower bounds.

1. Tower of Hanoi
2. Tower of Hanoi, the Hard Way
3. Bicolor Towers of Hanoi
   • Bicolor Towers of Hanoi, Solution
4. 3-Colors Tower of Hanoi
5. 3-Colors Tower of Hanoi (Algorithm)
6. Hanoing
7. Sierpinski Gasket and Tower of Hanoi