7
$\begingroup$

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:

Toroidal knight movement

$\endgroup$
4
  • $\begingroup$ Good lord ..... $\endgroup$ Jan 12, 2018 at 1:00
  • $\begingroup$ not sure I understand which moves are allowed.... in the example only two of a possible 8 moves seem to be allowed. If this is the case does it matter which two of the 8 we choose? Or am I missing something? --- aahhh ok _ I see we can choose 2 of the 8 possible and then have to run with making 1e6 moves..... interesting - sorry I didn't get that straight away $\endgroup$
    – tom
    Jan 12, 2018 at 1:10
  • $\begingroup$ @tom It should matter. The combinatorics turn out different depending on which one you analyze, so a complete answer ought to include all possible 2-square patterns (up to symmetry). $\endgroup$
    – Feryll
    Jan 12, 2018 at 1:14
  • $\begingroup$ @Feryll - yes sorry - my misunderstanding I get you now... I very much like this problem... ok I think I have the answer for some combinations... $\endgroup$
    – tom
    Jan 12, 2018 at 1:16

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Yup, nice explanation! $\endgroup$
    – Feryll
    Jan 12, 2018 at 1:38
  • $\begingroup$ aaaarrrgghhhh - very nicely done... I was fighting with the formatting and was making a real mess of my answer when you posted... Good job and very well explained, better than me! $\endgroup$
    – tom
    Jan 12, 2018 at 1:41
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Actually, it should depend on which two squares of movement are allowed. $\endgroup$
    – Feryll
    Jan 12, 2018 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.