Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Towers of Hanoi

  1. Dec 31, 2005 #1
    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. jcsd
  3. Dec 31, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  4. Dec 31, 2005 #3
    No I assure you it's not a homework problem. heck, there's no school now!
    Yes I do know the classic proof...
     
  5. Dec 31, 2005 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor


    ?? 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?
     
  6. Dec 31, 2005 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I assert that the proof for your special case is almost identical to the proof for the classical problem.
     
  7. Dec 31, 2005 #6

    benorin

    User Avatar
    Homework Helper

  8. Jan 1, 2006 #7
    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....
     
  9. Jan 1, 2006 #8

    benorin

    User Avatar
    Homework Helper

    I think that HoI is suggesting you formulate a recurrence relation.
     
  10. Jan 1, 2006 #9

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    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! :)
     
  11. Jan 1, 2006 #10
    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.
     
  12. Jan 2, 2006 #11

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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".
     
  13. Jan 2, 2006 #12

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

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

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Dang! One of these days, I'm going to have to learn to distinguish between "more" and "less"!
     
  15. Jan 11, 2006 #14
    Hi ,Did you solve your problem ? Are you a vietnamese :biggrin:
     
  16. Jan 16, 2006 #15
    yes, i solved the problem, and no, i'm not viatnamese. why do you ask?
     
  17. Jan 17, 2006 #16

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    HINT: Where is Hanoi? :uhh:
     
  18. Jan 18, 2006 #17
    heh i'm sorry, i forgot all about the problem
    are you a vet?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Towers of Hanoi
Loading...