Copyright © University of Cambridge. All rights reserved.
This is an interesting investigation with many
possible ways of solving and generalising the problem, and several
people wrote in giving an answer of 66 moves.
Isabelle from Lathallan School investigated
what happened with different sized grids, and spotted a pattern,
which she used to get an answer of 66.
The smallest numbers of moves for 99 squares is 66 moves. I
worked out the smallest number of moves for a 3 square grid which
was 4. I then worked out the number of moves for a 4 square (which
was 2) and a 5 square which was 4. The 6 square was also 4 and so
was the 7 square. And then because the moves have to go from a
white square and end up on a white square then the number of moves
cannot ever be an odd number. So then I tried 8, 9 and 10 square
grids which all needed6 moves. So then when I got to 15 squares I
needed 10 moves. So then I worked out that a 30 square needs 20
moves. The number of squares is 1.5 times the number of required
moves. I tested this at 45 squares (30 moves) and therefore at 99
squares it was 66 moves.
Emily from Durham Johnston Comprehensive
School and Tom from Bristol Grammar School both used algebra to
explain Isabelle's pattern. Here is Tom's solution:
Firstly, we establish the (obvious) fact that a knight can
move down 3 and across 3 in only two moves, and that this is the
most efficient way (or certainly no less efficient than any other
way) to generally move in the direction from the top left to the
bottom right.
Proof: one move is either (2,1) or (1,2). The above move is
(3,3), which is the furthest distance you can travel with 2 knight
moves, and in precisely the correct direction. We also establish
that an even number of moves will be required, because the knight
finishes on a square of the same colour to that upon which it
started. Therefore, our problem is reduced to the most efficient
way to get out of, and into, the corners. Take n> 3 (3 is shown,
and less than 3 is impossible). We have three cases.
Case 1: n=3k+1 for some integer k. In this case, we can get
across using only the kind of move established above, and we also
established that it was most efficient. So we are already done. 2k
moves will be required.
Case 2: n=3k-1 for some integer k. In this case, we can reduce
it to a 5x5 board using (3,3) moves. We can solve this problem with
only 4 moves. Since we know an even number of moves is needed, and
that the knight cannot possibly cover the ground in two moves, this
must be the most efficient way, so 2k moves are needed here, 2(k-2)
to get us to the 5x5 case, and 4 more to complete.
Case 3: n=3k for some integer k. This reduces to a 6x6 square
(since n> 3). Again, this can be solved using four moves (see
diagram), and cannot be solved with fewer moves by the same logic
as in case 2, so 2k is the minimum number of moves needed here:
2(k-2) to get to the 6x6 case, and 4 to finish from there.