Can the Towers of Hanoi Problem Exceed 2^n-1 Moves?

[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)?

 

[Hurkyl]

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?

 

[asdf60]

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

 

[HallsofIvy]

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)?

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

 

[Hurkyl]

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

 

[benorin]

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

 

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

 

[benorin]

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

 

[Tide]

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

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! :)

 

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

 

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

 

[shmoe]

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

 

[HallsofIvy]

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

 

[linhtm]

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)?

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

 

[asdf60]

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

 

[Tide]

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

HINT: Where is Hanoi?

 

[asdf60]

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