# Towers of Hanoi

1. Dec 31, 2005

### asdf60

Here's an interesting question about the famous Towers of Hanoi problem. Is there any initial configuration of the disks on three pegs that requires more than 2^n-1 moves (to construct a tower on the rightmost peg)?

2. Dec 31, 2005

### Hurkyl

Staff Emeritus
This almost sounds like a homework problem! Have you thought about the question at all? Do you know (well) the proof that the classic solution works in 2^n - 1 steps?

3. Dec 31, 2005

### asdf60

No I assure you it's not a homework problem. heck, there's no school now!
Yes I do know the classic proof...

4. Dec 31, 2005

### HallsofIvy

?? That's a peculiar question but the answer should be obvious. The standard Towers of Hanoi problem has all disks on one peg and it is fairly easy to prove that it then takes 2^n-1 moves to move them all to another peg.

Suppose you started with all the disks on one peg and then move the top disk. How many moves are required to get from that configuration to the end?

5. Dec 31, 2005

### Hurkyl

Staff Emeritus
I assert that the proof for your special case is almost identical to the proof for the classical problem.

6. Dec 31, 2005

### benorin

Here's a link to a http://thinks.com/java/hanoi/hanoi.htm [Broken]

Last edited by a moderator: May 2, 2017
7. Jan 1, 2006

### asdf60

It's clear to me now that it is always less than 2^n-1, but I don't think that it's obvious, to me at least.

HallsofIvy, I don't really see where you're going with that....

8. Jan 1, 2006

### benorin

I think that HoI is suggesting you formulate a recurrence relation.

9. Jan 1, 2006

### Tide

I think your original problem requires you to formulate an argument to show that any (valid) initial configuration will require at most the same number of moves required in the standard Tower initial configuration (i.e. all disk on the same post). You stated that it is now clear to you that it is true but I suggest that you write it out so others can verify if your logic is correct.

Regarding the "standard" Tower problem, Halls is simply pointing out how the "classic proof" is done. You say you "know the classic proof" but you haven't shown it. If you need help on that part, say so! :)

10. Jan 1, 2006

### murshid_islam

hi, is there an iterative algorithm to solve the tower of hanoi problem. i know the recursive one:

1. move n-1 discs from peg A to peg B.
2. mobe the nth disc to peg C.
3. move n-1 discs from peg B to peg C.

but what is the iterative algorithm (if there is any)?

thanks in advance to anyone who can help.

11. Jan 2, 2006

### HallsofIvy

Actually, what I was pointing out is that the original question was "Is there any initial configuration of the disks on three pegs that requires more than 2^n-1 moves (to construct a tower on the rightmost peg)?" where the "initial configuration of the disks on the three pegs" for the classical problem, that requires 2^n-1 moves, has all n disk on the "leftmost peg".

My point in my original response was: suppose you have already made the first move in the classical solution: isn't that a configuration which now requires 2^n- 2 moves? For that matter, suppose you have an "initial configuration" in which all except the smallest disk are already on the rightmost peg. Isn't that an "initial configuration" which will now require only one move?

Unless I am misunderstanding, the answer is obviously "yes, there exist initial configurations which require fewer than 2^n-1 moves".

12. Jan 2, 2006

### shmoe

He was asking if there was an initial configuration needing *more* than 2^n-1 moves. Less is pretty obvious like you say!

13. Jan 2, 2006

### HallsofIvy

Dang! One of these days, I'm going to have to learn to distinguish between "more" and "less"!

14. Jan 11, 2006

### linhtm

Hi ,Did you solve your problem ? Are you a vietnamese

15. Jan 16, 2006

### asdf60

yes, i solved the problem, and no, i'm not viatnamese. why do you ask?

16. Jan 17, 2006

### Tide

HINT: Where is Hanoi? :uhh:

17. Jan 18, 2006

### asdf60

heh i'm sorry, i forgot all about the problem
are you a vet?