All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Two Towers Hanoi (Posted on 2020-05-27) Difficulty: 3 of 5
A Towers of Hanoi puzzle has all of its discs colored black or white according to parity. Looking at the starting/finished tower the discs alternate back and forth between black and white.

Take a colored set like this and separate the white discs from the black discs. The white discs are placed on one pole in order and the black discs are placed on a second pole in order.

Devise an algorithm that will transfer the discs back into the complete tower on the third pole. As a function of N, how few moves can a tower of N discs be reassembled on the third pole?

An example: the XS, S, M, L, XL discs in the linked puzzle would start with the XS, M, and XL discs colored black and be on the first pole while the S and L discs would be colored white and be on the second pole.

No Solution Yet Submitted by Brian Smith    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Most of solution | Comment 1 of 4
The number of moves can be expressed as the sum of powers of 2 in an interesting pattern {1,0,1,1,0,1,1,0,1,1,0...

For N discs, the first power is N-1, (skip N-2) then N-3, N-4, (skip N-5) and so on down to 0 skipping every 3rd power after the N-1

For example N=8 discs requires 2^7+2^5+2^4+2^2+2^1=182 moves.

In the standard Towers of Hanoi, there are no missing powers of 2 and the sum is 2^N - 1.  In this variant you can see, when actually solving, that some discs are not hindering the smaller ones as much, so you don't need as many mini recursive towers. 

The sequence for N=0,1,2... discs is
0,1,2,5,11,22,45,91,182,
and you can see the same idea in the recursive structure
f(N+1)=2*f(N) if N=1mod3
f(N+1)=2*f(N)+1 if N=0 or 2mod3

Other formulas at



  Posted by Jer on 2020-05-27 13:45:20
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information