Bicolor Towers of Hanoi (Solution)
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·4n + 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 Tn. From the solution to the standard hanoi problem, we have Tn = 2n+1 - 2. That is:
| |
| T2n | = (6, -6, 0) |
| T2n-1 | = (3, -6, 0) |
|
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 Bn. 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 An. By induction on n, you may obtain:
| |
| A2n | = (8, -8, -3) |
| A2n-1 | = (4, -4, -3) |
| B2n | = (10, -10, -3) |
| B2n-1 | = (5, -5, -3) |
|
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 Ak is in general less than Bk. 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 Ln, satisfying Ln = An-2 + Bn-2 + 8·Tn-2 + 11. That is:
| |
| L2n+2 | = (66, -33, -6) = 11·(22n+1 - 1) - 3·2n |
| L2n+1 | = (33, -24, -6) = 11·(22n - 1) - 3·(2n-1) |
|
These two are the same: Lk = 11·(2k-1 - 1) - 3(k-2) for k sufficiently large. Of course, for n <= 2 the values are different: L0 = 0, L1 = 3, L2 = 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.
- Tower of Hanoi
- Tower of Hanoi, the Hard Way
- Bicolor Towers of Hanoi
- Bicolor Towers of Hanoi, Solution
- 3-Colors Tower of Hanoi
- 3-Colors Tower of Hanoi (Algorithm)
- Hanoing
- Sierpinski Gasket and Tower of Hanoi
Copyright © 1996-2008 Alexander Bogomolny
|
