Results 1 to 6 of 6

Math Help - knight on the chess board

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    43

    knight on the chess board

    How many steps does a knight need to reach the bottom right square from the opposite top left square on a 101x101 board?

    I am sure that he needs 67 steps or more because the sum of the coordinates of the starting square is 1+1=2 and the sum of the coordinates of the target square is 101+101=202. (So the difference is 200.) In each step the sum of the coordinates increases by (maximum) 3. So he needs at least 67 steps. I think 67 steps is not enough, but I can't prove how many he n.eeds

    Any help would be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by doug View Post
    How many steps does a knight need to reach the bottom right square from the opposite top left square on a 101x101 board?

    I am sure that he needs 67 steps or more because the sum of the coordinates of the starting square is 1+1=2 and the sum of the coordinates of the target square is 101+101=202. (So the difference is 200.) In each step the sum of the coordinates increases by (maximum) 3. So he needs at least 67 steps. I think 67 steps is not enough, but I can't prove how many he needs

    Any help would be appreciated!
    On an 8X8 board, a knight can move from G1 to D4 in 2 moves,
    while missing the squares F2 and E3,
    so it advances 3 left and 3 up in 2 moves, from (1,1) to (4,4).

    Therefore it will get to (10,10) in 6 moves.

    It takes 56 more moves to get to (94,94).
    On a normal board, it would be on H1 let's say,
    trying to get to A8 in the least number of moves.
    It cannot do so directly as described, so it takes a detour via

    H1 to G3 to H5 to F4 to D5 to B6 to A8.
    As this takes only one move more than if it could have continued it's previous
    hopping mechanism, (which could not be continued with),
    that is the shortest number of jumps.

    6+56+6=68

    EDIT: Sorry, I just noted from your post that my horse is going the wrong way!

    No matter, just reel the tape backwards.
    Last edited by Archie Meade; February 13th 2011 at 10:51 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2010
    Posts
    43
    Quote Originally Posted by Archie Meade View Post
    On an 8X8 board, a knight can move from G1 to D4 in 2 moves,
    while missing the squares F2 and E3,
    so it advances 3 left and 3 up in 2 moves, from (1,1) to (4,4).

    Therefore it will get to (10,10) in 6 moves.

    It takes 56 more moves to get to (94,94).
    On a normal board, it would be on H1 let's say,
    trying to get to A8 in the least number of moves.
    It cannot do so directly as described, so it takes a detour via

    H1 to G3 to H5 to F4 to D5 to B6 to A8.
    As this takes only one move more than if it could have continued it's previous
    hopping mechanism, (which could not be continued with),
    that is the shortest number of jumps.

    6+56+6=68

    EDIT: Sorry, I just noted from your post that my horse is going the wrong way!

    No matter, just reel the tape backwards.
    Thank you so much.
    I know that your solution is right and I see that we need at least 68 steps. On the other hand I can't see that it is formally proved. Why is it impossible that a better strategy exists? I mean, I see that 67 is a lower bound (beause of the sum of coordinates), but I can't see it for 68.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    The knight advances 3 left and 3 up in two hops.
    Hence it gets from (1,1) to (100,100) in 99/3 multiplied by 2 hops,
    which is in 66 hops.
    The knight cannot now hop onto the (101,101) position in 1 move.
    Hence, it is the exact scenario if it had started from (1,1) and wants to reach (8,8)
    on a normal chessboard.
    A route from corner to corner takes a minimum of 6 hops
    regardless of route taken.
    However, the knight can get from (1,1) to (94,94) by getting onto the long diagonal
    every 2nd move,

    from (1,1) to (4,4) to (7,7)..... to (94,94).

    The knight could take longer, but the absolute shortest route is 93/3 times 2, with the remaining smallest possible 6 added.
    That's 68 minimum.

    H1 to G3 to E4 to C5 to A6 to C7 to A8 is another version of the shortest route
    across a standard 8X8 board.

    If the knight started from F1 or H3, it could get to the corner on 4 moves, instead of 6.
    Unfortunately, it would not take less than 2 extra moves to get there instead of H1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    One way to see that 67 moves won't work is that the color of the square the knight is on changes at each move. The squares at (1,1) and (101,101) have the same color, so an even number of moves is required.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Sep 2010
    Posts
    43
    Quote Originally Posted by awkward View Post
    One way to see that 67 moves won't work is that the color of the square the knight is on changes at each move. The squares at (1,1) and (101,101) have the same color, so an even number of moves is required.
    Thank you, that was what I needed.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chess board and 2x1 domino stones.
    Posted in the Math Puzzles Forum
    Replies: 0
    Last Post: July 27th 2011, 05:09 PM
  2. Chess Board Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 4th 2011, 03:13 PM
  3. Grains of rice on a chess board
    Posted in the Math Puzzles Forum
    Replies: 8
    Last Post: March 10th 2010, 03:33 PM
  4. knight's restricted walk
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 12th 2009, 06:34 AM
  5. Need help on POW 12: The Big Knight Switch
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: June 5th 2005, 05:35 PM

Search Tags


/mathhelpforum @mathhelpforum