Results 1 to 5 of 5

Math Help - Tower of Hanoi Problem and skipping a move

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Tower of Hanoi Problem and skipping a move

    The Tower of Hanoi problem:


    According to legend, a certain Hindu temple contains three thin diamond poles( A, B, C and A is closer to B and B is closer to C but C is not closer to A) on one of which, at the time of creation, God placed 64 golden disks that decrease in size as they rise from the base.

    The priests of the temple work unceasingly to transfer all the disks one by one from the first pole to one of the others, but they must never place a large disk on top of a smaller one and they are allowed to move disks from one tower to only adjacent pole. Let

     a_n = \left[ \begin{array}{c} \text{the minimum number of moves} \\ \text{needed to transfer a tower of n} \\ \text{ disks from pole A to pole C} \end{array} \right ]

     b_n = \left[ \begin{array}{c} \text{the minimum number of moves} \\ \text{needed to transfer a tower of n} \\ \text{ disks from pole A to pole B} \end{array} \right ]

    Find a recurrence relation a_n and b_n.

    Solve for the problem to find a_n (The book did this):

    \begin{align*}\nonumber a_n  =& a_{n-1} \text{ (moves to move the top n - 1 disks from pole A to pole C) }  +\\  &\nonumber 1 \text{ (move to move the bottom disk from pole A to pole B) } + \\ &  \nonumber a_{n-1} \text{ (moves to move the top disks from pole C to pole A) } + \\ &  \nonumber 1 \text{ (move to move the bottom disk from pole B to pole C) } + \\ & \nonumber a_{n-1} \text{ (moves to move the top disks from pole A to pole C) } \\ \nonumber =& 3a_{n-1} + 2 \end{align*}



    Solve for the problem to find b_n(I did this):

     \begin{align*}\nonumber  b_n =& b_{n-1} \text{ (moves to move the top n - 1 disks from pole A to pole C) }  +\\ & \nonumber 1 \text{ (move to move the bottom disk from pole A to pole B } + \\ & \nonumber b_{n-1} \text{ (moves to move the top disks from pole C to pole B) } \\ \nonumber =& 2b_{n-1} + 1 \end{align}


    Why my solution of b_n is wrong? For finding b_n I did the same thing as done in finding a_n which is skipping the move from A to B when moving from A to C. I calculated this move as 1 like the book did it.

    So why am I wrong?


    Also my question is why in finding a_n to move the disks from A to C they skipped to calculate the move to move the disks first from A to B?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Tower of Hanoi Problem and skipping a move

    Unless the rules contains some restriction that takes into account how close the poles are, a_n should be equal to b_n. The recurrence equation is a_n=2a_{n-1}+1, and similarly for b_n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Tower of Hanoi Problem and skipping a move

    Quote Originally Posted by emakarov View Post
    Unless the rules contains some restriction that takes into account how close the poles are, a_n should be equal to b_n. The recurrence equation is a_n=2a_{n-1}+1, and similarly for b_n.
    I am bit confused. The poles are erected like Figure 1.

    Tower of Hanoi Problem and skipping a move-poles3.png

    The rules for moving the disks are:
    You can move disks from pole A to pole  C via Pole  B you can't move disks directly to Pole C from Pole A.
    Same rule goes for pole C. You can't move disk directly from pole C to Pole A. You've to go via Pole B.
    You can move disks directly from Pole A to pole B. Also you can move disks directly from Pole C to pole B
    You can move disks from Pole B to Pole A or to Pole C directly . And you can't move larger disks on smaller disks.

    You said that:

    a_n=2a_{n-1}+1


    Now a_1 = 2 because if you have 1 disk in pole A it will take 2 moves to move 1 disk from pole A to pole C via pole B. you can't move a disk from pole A to pole C directly according to the rule stated above.

    a_2 = 8 if you look at the Figure 1 you need minimum 8 moves to move 2 disks from pole A to pole C but you said a_n=2a_{n-1}+1

    If we plug in the value of n = 2 we get:
    a_2 = 2a_{2-1} + 1 = 2a_{1} + 1 = 2*2 + 1 = 5 \neq 8 \text{(we got previously)}

    So shouldn't a_n  = \left[ \begin{array}{c} \text{the minimum number of moves} \\ \text{needed to transfer a tower of n} \\ \text{ disks from pole A to pole C} \end{array} \right ]  = 3a_{k-1} + 2?




    The same goes for b_n


    You said that b_n  = \left[ \begin{array}{c} \text{the minimum number of moves} \\ \text{needed to transfer a tower of n} \\ \text{ disks from pole A to pole B} \end{array} \right ]  = 2b_{n-1} + 1

    Base condition is b_1 = 1 because to move a disk from pole A to pole B you need minimum 1 move according to the rules above.

    Then if you look at Figure 1 it takes 4 minimum moves to move 2 disks from pole A to pole B. So b_2 = 4

    If we replace n with 2 according to your equation:

    b_2 = 2b_{2-1} +1 = 2b_1 + 1 = 2* 1 + 1 = 3 \neq 4


    You can't take 3 move to move 2 disks from pole A to pole B. It's impossible according to the rules stated above.


    Can you kindly shed light what you said? Sorry I didn't get it. Also is it possible to get an answer to my question I posted first in this thread?
    Last edited by x3bnm; September 19th 2011 at 08:13 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Tower of Hanoi Problem and skipping a move

    Sorry, I missed the adjacency requirement. It's not in the standard Towers of Hanoi rules.

    The equation for b_n should be b_n=a_{n-1}+b_{n-1}+1 since the first part is moving disks from A to C, which takes a_{n-1} moves.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Tower of Hanoi Problem and skipping a move

    Quote Originally Posted by emakarov View Post
    Sorry, I missed the adjacency requirement. It's not in the standard Towers of Hanoi rules.

    The equation for b_n should be b_n=a_{n-1}+b_{n-1}+1 since the first part is moving disks from A to C, which takes a_{n-1} moves.
    I know the subject should be "Modified Tower of Hanoi Problem....." Sorry for misunderstanding.

    And thanks for the answer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hanoi specific problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 7th 2012, 12:30 PM
  2. Towers of Hanoi Problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 30th 2010, 08:42 AM
  3. Tower of Hanoi Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 23rd 2010, 04:11 PM
  4. Tower Law problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 12th 2009, 04:30 PM
  5. Reve's Puzzle (Hanoi Problem with 4 towers)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2008, 07:35 PM

/mathhelpforum @mathhelpforum