knight on the chess board

[doug]

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!

[Archie Meade]

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.

[doug]

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.

[Archie Meade]

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.

[awkward]

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.

[doug]

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.