Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Best sites for teachers
Sites for teachers
Sites for parents
Terms of use
Awards

Interactive Activities
CTK Exchange
CTK Insights - a blog

Games & Puzzles
What Is What
Arithmetic/Algebra
Geometry
Probability
Outline Mathematics
Make an Identity
Book Reviews
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
Visual Illusions
My Logo
Math Poll
Cut The Knot!
MSET99 Talk
Other Math sites
Front Page
Movie shortcuts
Personal info
Reciprocal links
Privacy Policy

Guest book
News sites

Recommend this site

Best sites for teachers
Sites for teachers
Sites for parents

Education & Parenting

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

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 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.

  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

Copyright © 1996-2008 Alexander Bogomolny

28762640Page copy protected against web site content infringement by Copyscape


Search:
Keywords:


Latest on CTK Exchange
Math
Posted by Laura
2 messages
06:56 AM, Apr-15-08

Divisibility rules - Jargon buste ...
Posted by Carolyn
2 messages
08:35 AM, Apr-04-08

drawing puzzle
Posted by martin gran
31 messages
06:53 PM, May-09-08

conway's game of life
Posted by frequency
0 messages
11:52 PM, May-12-08

Mistake on the page (an aside, Be ...
Posted by Max
4 messages
10:28 AM, Feb-28-08

A Riddle
Posted by idavis1
33 messages
06:59 AM, May-15-08

Josephus Flavius (correction)
Posted by David Turner
1 messages
09:42 AM, May-14-08