Gimped Knight on a Torus

Question

Place a knight on a toroidal $100 \times 100$ board (i.e. the edges wrap). Restrict his movement to a particular 2-square pattern (gimped from his usual 8-square pattern; for example, he may only be able to move up-up-right and down-left-left). After move one, he may be in one of two locations. After move two, he may be in one of three locations, and so on. After one million moves, how many different locations may he be in? Does it depend on the 2-square pattern that is chosen?

Here is an example of how one pattern of possible locations will develop, on a $5 \times 5$ board:

Answer 1

Suppose the knight's permitted moves are $u$ and $v$. (These are two-dimensional "vectors" on the torus.) Then

after $N$ moves he is at $nu+(N-n)v$ for some $n$. We can write this as $Nv+n(u-v)$. Note that the first term is the same whatever $n$ may be; and note that choosing $n$ is all we get to do. So the knight's repertoire of available squares is, up to translation, just all the multiples of $u-v$. This will form a single straight line, possibly "dotted", and possibly wrapping around as it reaches the edges of the 100x100 square.

Thus:

Without loss of generality, suppose one of his available moves is (2,1). Then his other might be:
(1,2), so that $u-v$ = (1,-1) and he can reach a diagonal line of 100 squares;
(1,-2), so that $u-v$ = (1,-3) and he can reach a more-slanted "dotted" line of 100 squares, wrapping around twice or three times depending on how you count;
(2,-1), so that $u-v$ = (0,2) and he can reach an orthogonal dotted line of 50 squares;
(-2,1), so that $u-v$ = (4,0) and he can reach an orthogonal more-dotted line of 25 squares;
(-2,-1), so that $u-v$ = (4,2), dotted, slanted, wrapping around once or twice depending on how you count, 50 squares;
(-1,2), so that $u-v$ = (3,1), dotted, slanted, wrapping 2/3 times, 100 squares;
(-1,-2), so that $u-v$ = (3,3), wrapping around on a single 45-degree diagonal, covering all 100 squares.

Answer 2

I think I have the answer

Ok so I image the moves of the knight as being on a clock face .... the knight can move to 1 O'Clock, 2 O'Clock, 4 O'Clock, 5 O'Clock, 7 O'Clock, 8 O'Clock,10 O'Clock and 11 O'Clock,

now

For 1 O'Clock and 2 O'Clock - 100 squares

and for

1 O'Clock and 4 O'Clock - 100 squares

and for

1 O'Clock and 5 O'Clock - 25 squares

and for

1 O'Clock and 7 O'Clock - 50 squares

and for

1 O'Clock and 8 O'Clock - 100 squares

and for

1 O'Clock and 10 O'Clock - 100 squares (same as 1 and 4)

and for

1 O'Clock and 11 O'Clock - 50 squares

The reasoning

The two moves are like vectors - say a and b- and after 1e6 moves the knight will have move 1e6a + k(b-a) where k is a number between 0 and 1e6.... thus it all depends on how many different squares lie on the line defined by the difference between the two vectors (and of course integer units of the line

Answer 3

Correct answer is 50.

There are 2 distinct movements and the catch here is to realize that the order of movements doesn't matter and the number of movements will not matter if you can set a formula.

Say you start at (x0, y0) make n total movements and n of these are (up-up-right)(uur) and m - n are (down-down-left)(ddl) movements.

n (uur) movements means you will move:
-2n along the y axis
+n along the x axis

m - n (ddl) movements means you will move:
2(m-n) along the y axis
-n along the x axis

Compiling this you will end up at (xM, yM) = (x0 + n - (m - n), y0 - 2n + 2(m - n)) = (x0 - m + 2n, y0 + 2m - 4n).
with m = 1,000,000 & n in [0,100]

Every +/- 100 in either direction is nullified since the board is toroidal. So your final location is actually modulus of 100. ((x0 - 1,000,000 + 2n) % 100, (y0 + 2(1,000,000) - 4n) % 100) = ((x0 + 2n) % 100, (y0 - 4n) % 100)
The number of final locations depends on different values of n, and since 2n is modulused(sp?) by 100, the final location can only have 50 different values.