Modular Knights


This problem was a toughnut for a while before we received solutions from several students.
 
Max Whittaker from Culford School, Jose, Carlos , Dan and Sam from Ickford Combined School, Issy and Audrey, also from Ickford combined school, all sent in their methods of solution in certain cases. This involved starting in a certain place and moving around the board systematically.


Alex from Darell Primary School gave an explicit solution:

First you need to have these settings:

knight moves round: 2 in/out:

1 board sectors: 3 tracks: 3

Here is what you should do in the exact order, there may be other ways, but here is what I did.

Bottom/middle right
Inner left
Top right
Inner bottom right
Far left
Bottom right
Then finally, Far/middle left


Ben from Kenny School gave a great description of his mathematical thinking about this analysis of this problem which we like very much: it really highlights the creative side of mathematical problem solving.
 
 
Ben uses the notion of coprime numbers (two whole numbers which share no common factor except 1) to make some inroad into the analysis of the problem .

Ben cleverly represented the board as a rectangle with opposite sides identified, which makes visualising, and therefore analysing, the situation much easier.
 
If the grid is $p$ by $q$ and the knight can move $a$ across and $b$ down then Ben suggests that the journey is possible if at least 2 of the following conditions are true
 
  1. $a (\mbox{ mod } p)$ is coprime to $p$
  2. $b (\mbox{ mod } q)$ is coprime to $q$
  3. $b (\mbox{ mod } p)$ is coprime to $p$
  4. $a (\mbox{ mod } q)$ is coprime to $q$
You can read Ben's analysis here.
 

This is a great start, but not quite the whole story as some grids with coprime values are not coverable, although many are.
 
 
 To make a little more progress, imagine that the grid has $p$ rows and $q$ columns, with $p, q$ coprime and $q> p$. Suppose also that the knight moves $a$ across and $b$ down each time, where $a$ is coprime to $p$ and $b$ coprime to $q$. Then each of the first $q$ squares will land on a different column of the grid ; therefore the knight will not have revisited any squares yet, although it will have revisited $q-p$ rows. If $q-p$ is coprime to $p$ then this procedure will fill the whole grid. If not, then the knight will need to change direction at some point to have a chance of filling the grid without hitting another square more than one. 
 
To proceed note that if the knight always moves in the same direction it positions will be of the form $(na \mbox{ mod p} , nb \mbox{ mod q}) $.
 
For a location to be repeated, for some $n$ and $m$ we would have 
$$
(na \mbox{ mod p} , nb \mbox{ mod q}) =(ma \mbox{ mod p} , mb \mbox{ mod q})
$$
For this to hold we would have
$$
((n-m)a \mbox{ mod p} , (n-m)b \mbox{ mod q}) =(0,  0)
$$
Since $a$ and $b$ are coprime to $p$ and $q$ respectively this implies that
$(n-m) = Np$ and $(n-m)= Mq$ for some non-zero integers $N$ and $M$. Since $p$ and $q$ were chosen to be coprime and different we must have $N = Rq$ and $M=Rp$ for some other non-zero integer $R$. Thus $(n-m)$ is a non-zero multiple of $pq$. Since there are only $pq$ squares in the grid we see that the knight cannot have revisited any squares.