Show that a generalized knight can return to its original position only after an even number of moves

Question

Source: German Mathematical Olympiad

Problem:

On an arbitrarily large chessboard, a generalized knight moves by jumping p squares in one direction and q squares in a perpendicular direction, p, q > 0. Show that such a knight can return to its original position only after an even number of moves.

Attempt:

Assume, wlog, the knight moves $q$ steps to the right after its $p$ steps. Let the valid moves for the knight be "LU", "UR", "DL", "RD" i.e. when it moves Left, it has to go Up("LU"), or when it goes Up , it has to go Right("UR") and so on.

Let the knight be stationed at $(0,0)$. We note that after any move its coordinates will be integer multiples of $p,q$. Let its final position be $(pk, qr)$ for $ k,r\in\mathbb{Z}$. We follow sign conventions of coordinate system.

Let knight move by $-pk$ horizontally and $-qk$ vertically by repeated application of one step. So, its new position is $(0,q(r-k))$ I am thinking that somehow I need to cancel that $q(r-k)$ to achieve $(0,0)$, but don't be able to do the same.

Any hints please?

Answer 1

Case I: If $p+q$ is odd, then the knight's square changes colour after each move, so we are done.

Case II: If $p$ and $q$ are both odd, then the $x$-coordinate changes by an odd number after every move, so it is odd after an odd number of moves. So the $x$-coordinate can be zero only after an even number of moves.

Case III: If $p$ and $q$ are both even, we can keep dividing each of them by $2$ until we reach Case I or Case II. (Dividing $p$ and $q$ by the same amount doesn't change the shape of the knight's path, only its size.)

Answer 2

it may be assumed without loss of generality that $(p,q)=1$ and Patrick's argument shows we may assume both $p$ and $q$ are odd.

represent the moves as follows, with the indices taking values in $\{0,1\}$: $$ M[i,j] = ((-1)^ip,(-1)^jq) \\ N[i,j] = ((-1)^iq,(-1)^jp) $$ and denote the number of moves of each type by $m_{ij},n_{ij}$

to return to the same point requires $$ p\sum m_{ij} + q \sum n_{ij} \equiv_2 0 $$ (and a similar constraint with $p$ and $q$ interchanged) hence $\sum m_{ij} \equiv_2 \sum n_{ij}$

since the total number of moves is $\sum m_{ij}+\sum n_{ij}$, the required result follows

Answer 3

An alternative algebraic solution:

You have 8 possible moves $(p,q)$, $(p,-q)$, $(-p,q)$, $(-p,-q)$, $(q,p)$, $(q,-p)$, $(-q,p)$, $(-q,-p)$. Let $a_1,\cdots,a_8$ the number of each one of these moves ($a_i$ are nonnegative integers). Starting from $(0,0)$ you arrive at the point $$\left((a_1+a_2-a_3-a_4)p+(a_5+a_6-a_7-a_8)q,\:(a_5-a_6+a_7-a_8)p+(a_1-a_2+a_3-a_4)q\right)$$ In order to return to $(0,0)$ the following must hold $$(a_1+a_2-a_3-a_4)p+(a_5+a_6-a_7-a_8)q=0\\ (a_5-a_6+a_7-a_8)p+(a_1-a_2+a_3-a_4)q=0$$

Case 1: If $$a_1+a_2-a_3-a_4=0$$ then $$a_5+a_6-a_7-a_8=0$$ For each one of these equations the numbers of odds must be even. Thus the total sum $\sum_{i=1}^8{a_i}$ which is the total number of moves must be even.

Case 2: If $$a_1+a_2-a_3-a_4\neq 0$$ then $$p=\frac{a_7+a_8-a_5-a_6}{a_1+a_2-a_3-a_4}q$$ Replacing now into the second equation we obtain $$(a_5-a_6+a_7-a_8)(a_7+a_8-a_5-a_6)+(a_1-a_2+a_3-a_4)(a_1+a_2-a_3-a_4)=0$$ or equivalently $$(a_7-a_6)^2-(a_5-a_8)^2+(a_1-a_4)^2-(a_2-a_3)^2=0$$ and $$(a_7-a_6)^2+(a_1-a_4)^2=(a_2-a_3)^2+(a_5-a_8)^2$$ Consider again the total number of odds in the above equation. This must be even and therefore the total sum $\sum_{i=1}^8{a_i}$ which is the total number of moves must also be even for Case 2.

Answer 4

EDIT I realize now afterwards that I accidentally answered the wrong question, but it would feel a bit like a waste to delete it. Is it possible to archive as "wrong answer to the question posed, but maybe useful in other contexts".

---

Say the current coordinate is $(x,y)$, A horse jump is always $\pm 1$ in one dimension and $\pm 2$ in the other. For each single jump we alter modulo 2 for one and only one of $x$ and $y$. This shows a stronger result : that we can't end up in any of the positions with same divisibility with 2 if we start at a particular position and stop after an odd number of jumps.

The following octave code gives an illustrative image:

[xs,ys] = meshgrid(1:8,1:8);

MyImage = ((mod(xs,2)==1)&(mod(ys,2)==1))*1 + 1 *(xs==5&ys==3);

figure; imagesc(MyImage);

colormap gray;

If starting at the white position we can never reach any non-black square after an odd number of jumps.

---

Fun fact In my native language this piece is always called a horse. I guess the knight must have fallen off since it jumps so peculiarly.

Answer 5

Since they are orthogonal, I think we can separate the $p$ moves and $q$ moves as different entities, then regardless of the value of $p$ and $q$ (it won't even matter if they're not integers), we know that with looking only at one specific direction (either p or q, one dimensional case), it always takes even number of moves to get to the original position.

I.e. to get to the original position: $n \cdot forward + m \cdot backward = 0$, but if $forward = -backward$, then $n=m$ and the total number of steps is $n + m = 2n$ and, whatever the value of integer $n$, it will be even.

Combining the two dimensions, we will wait for both the two directions $p$ and $q$ to simultaneously reach its original position to determine the number of steps, but it won't matter since if either one of the directions reached its original position, it will always be even number of steps.

Answer 6

There is a simple argument to be made for the regular chess knight $p=2, q=1$ which can be extended to more general cases if we use $\gcd(p,q)$.

---

Let $x_i$ be the distance covered in the $x$-dimension on move $i$. Let $y_i$ be the distance in the $y$-dimension on move $i$. We affirm that

$$ |x_i|+|y_i| = p+q $$ $$ \gcd(p, q) = G $$

Two necessary but entirely insufficient conditions for the knight to have returned to his original position after $n = r+s$ moves such that $0 \le r \le n$ are:

1. $\sum\limits_{i=1}^{r+s} |x_i|+|y_i| \equiv 0 \pmod{2G}$
2. $\sum\limits_{i=1}^{r+s} \left( |x_i| \pmod{2G} \right) \equiv 0 \pmod{2G}$

We can derive constraints on $p$, $q$ and $n=r+s$ from those equations. $$ \begin{align} \sum\limits_{i=1}^{r+s} |x_i|+|y_i| &\equiv 0 \pmod{2G} \\ \sum\limits_{i=1}^{r+s} p+q &\equiv 0 \pmod{2G} \\ (r+s)(p+q) &\equiv 0 \pmod{2G} \\ rp+sp+rq+sq &\equiv 0 \pmod{2G} \end{align} $$ and $$ \begin{align} \sum\limits_{i=1}^{r+s} \left( |x_i| \pmod{2G} \right) &\equiv 0 \pmod{2G} \\ rp + sq &\equiv 0 \pmod{2G} \end{align} $$ whence we obtain by substitution of the second equation into the first $$ rq+sp \equiv 0 \pmod{2G} $$ Without loss of generality, let us select $r = 1 \pmod{2}$ and $s = 0 \pmod{2}$, so that $n$ is odd. Then we obtain $$ \begin{align} rp + sq &\equiv 0 \pmod{2G} \\ rq+sp &\equiv 0 \pmod{2G} \\ \\ (1)p + (0)q &\equiv 0 \pmod{2G} \\ (1)q+(0)p &\equiv 0 \pmod{2G} \\ \\ p &\equiv 0 \pmod{2G} \\ q &\equiv 0 \pmod{2G} \end{align} $$ Contradiction! $p$ and $q$ are both evenly divided by twice their GCD! Therefore, $r$ cannot be odd while $s$ is even and vice-versa. They must both have the same parity, and in this case $n=r+s$ will have even parity.

---

Why this works:

1. Strong Knight Conjecture: A knight has returned when $\sum_{i}^{n} x_i = 0$ and $\sum_{i}^{n} y_i = 0$.
2. Weak Knight Conjecture: A knight may have returned only if $\sum_{i}^{n} x_i = 0 \pmod{2}$ and $\sum_{i}^{n} y_i = 0 \pmod{2}$.
3. Ultraweak Knight Conjecture: A knight may have returned only if $\sum_{i}^{n} |x_i| = 0 \pmod{2}$ and $\sum_{i}^{n} |y_i| = 0 \pmod{2}$
4. Ultraultraweak Knight Conjecture: A knight may have returned only if $\sum_{i}^{n} |x_i| + |y_i| = 0 \pmod{2}$
5. If $p$ and $q$ are odd, (2) holds only when $n$ is even, despite all the weakening.
6. If $p+q$ is odd, (4) holds only when $n$ is even, despite all the weakening.
7. If $p$ and $q$ are both even, then we can reduce to the equivalent problem $p' = \dfrac{p}{\gcd(p,q)}, q' = \dfrac{p}{\gcd(p,q)}$, and then either (5) or (6) applies.

Answer 7

Without loss of generality, we can assume $p\ge q\ge0$. Two cases are easy to prove:

1. If $p+q$ is odd, the knight alternates between black and white squares, so it takes an even number of moves to return to whatever color you started on.

2. If $q=0$, the each move is either purely horizontal or purely vertical; it will require an even number of each type of move to get back to where you start, so an even number in all.

If $p+q$ is even, we can reinterpret the knight's move as being made in the two perpendicular diagonal directions. The total number of squares jumped in the reinterpretation is easily seen to be $p$. Since $p\lt p+q$ if $q\gt0$, we can say the magic word "induction" and call it a day (or a knight).

Answer 8

This uses complex numbers.

Define $z=p+qi$. Say that the knight starts at $0$ on the complex plane. Note that, in one move, the knight may add or subtract $z$, $iz$, $\bar z$, $i\bar z$ to his position.

Thus, at any point, the knight is at a point of the form: $$(a+bi)z+(c+di)\bar z$$ where $a$ and $b$ are integers.

Note that the parity (evenness/oddness) of the quantity $a+b+c+d$ changes after every move. This means it's even after an even number of moves and odd after an odd number of moves. Also note that: $$a+b+c+d\equiv a^2+b^2-c^2-d^2\pmod2$$ (This is because $x\equiv x^2\pmod2$ and $x\equiv-x\pmod2$ for all $x$.)

Now, let's say that the knight has reached its original position. Then: \begin{align} (a+bi)z+(c+di)\bar z&=0\\ (a+bi)z&=-(c+di)\bar z\\ |a+bi||z|&=|c+di||z|\\ |a+bi|&=|c+di|\\ \sqrt{a^2+b^2}&=\sqrt{c^2+d^2}\\ a^2+b^2&=c^2+d^2\\ a^2+b^2-c^2-d^2&=0\\ a^2+b^2-c^2-d^2&\equiv0\pmod2\\ a+b+c+d&\equiv0\pmod2 \end{align} Thus, the number of moves is even.

Interestingly, this implies that $p$ and $q$ do not need to be integers. They can each be any real number. The only constraint is that we can't have $p=q=0$.