36
$\begingroup$

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?

$\endgroup$
  • 7
    $\begingroup$ Unless I'm misinterpreting the problem, you don't have to show that you can make the knight return to its original position after an even number of moves (that's easy: just do the 'inverse' moves in the right order, i.e. take back all the moves). But rather answer the question: Why can't I make it go there and back in an odd number of moves? $\endgroup$ – Roland Dec 5 '15 at 10:22
  • 7
    $\begingroup$ Completely unrelated to your current work, but there's a domino tiling argument here to get rid of half the cases. Tile the board with dominoes, where one half of each domino is white and the other black (basically turn it into a standardly-coloured chessboard). Then at every move, the knight must move from white to black or black to white, if $p+q$ is odd, so it must take an even number of moves to get from any black square to any black square; in particular, from its starting square to its starting square. $\endgroup$ – Patrick Stevens Dec 5 '15 at 10:23
  • $\begingroup$ Aha. It's an induction. $\endgroup$ – Patrick Stevens Dec 5 '15 at 10:36
  • 4
    $\begingroup$ Also, you can't assume its final positions will be $(pk,qr)$ because you can interchange the $p$ and $q$. For example you could after two moves be at $(p+q,p+q)$. $\endgroup$ – Morgan Rodgers Dec 5 '15 at 10:37
  • $\begingroup$ Conjecture: The "range" of the knight (the set of points that the knight can visit) is either a scaled version of the original board (i.e. of the form $\{(ka,kb):a,b\in\Bbb Z\}$) or a scaled version of the board rotated 45 degrees (i.e. of the form $\{(ka,kb):a,b\in\Bbb Z\ \&\\a+b\equiv0\pmod2\}$). $\endgroup$ – Akiva Weinberger Dec 6 '15 at 0:08
91
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ @GuarangTandon This is precisely my argument, but put into much more straightforward words. You may find mine easier to read than it was, in the light of this one. $\endgroup$ – Patrick Stevens Dec 5 '15 at 14:27
  • $\begingroup$ There seems to be a gap in this proof. Consider the case $p = q = 2$. You divide this by $2$ to get into case II, and show that an even number of these short-moves is required. Fair enough. But you're supposed to be proving that an even number of long-moves is required. So you still need to show what prevents the number of short-moves (which we know is even) from being $2$ modulo $4$, such that the number of long-moves is odd. $\endgroup$ – Steve Jessop Dec 5 '15 at 15:05
  • 4
    $\begingroup$ @Steve: I'm not saying "make two short moves for every long move". I'm saying "make one short move for every long move". The new path will have the same shape as the old path, and the number of moves is unchanged. $\endgroup$ – TonyK Dec 5 '15 at 15:07
  • 6
    $\begingroup$ The cases can be viewed by colorings: Case I is the normal chessboard coloring. For case II, color the chessboard in vertical stripes. For case III, color it in blocks of $\gcd(p,q)\times\gcd(p,q)$ squares. In each case, every move changes the color of the square under the knight. $\endgroup$ – Paul Sinclair Dec 5 '15 at 18:30
  • 1
    $\begingroup$ @PaulSinclair : Ah. You're right. Yet ... there should be one coloring to rule them all. $\endgroup$ – Eric Towers Dec 5 '15 at 19:30
19
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ Looks good to me! $\endgroup$ – TonyK Dec 6 '15 at 1:02
  • $\begingroup$ I haven't learnt complex numbers, so this one goes off my head, anyway, +1! $\endgroup$ – Gaurang Tandon Dec 6 '15 at 2:57
  • $\begingroup$ @GaurangTandon I'll try to give you a quick crash-course. Basically, instead of writing $(p,q)$ for a point on the plane, you write $p+qi$. ($1$ is identified with the point $(0,1)$; $i$ here refers to the point $(1,0)$.) The bar over the $z$ means "complex conjugate." If $z=p+qi$, then $\bar z=p-qi$. Geometrically, it's $z$ reflected in the $x$-axis. (Cont'd) $\endgroup$ – Akiva Weinberger Dec 6 '15 at 4:41
  • $\begingroup$ Adding complex numbers (points) works like you'd expect; $(A+Bi)+(a+bi)=(A+a)+(B+b)i$. Multiplication is weirder; we define $i^2$ to be $-1$ (for reasons you'll see in a bit). Thus, using FOIL, $(A+Bi)(a+bi)=(Aa-Bb)+(Ab+Ba)i$. The nice thing is that multiplying by $i$ rotates a number 90 degrees. For example, if $z=p+qi$, then $iz=i(p+qi)=ip-q=-q+pi$. If you try graphing a few examples, you'll see that $-q+pi$ is $p+qi$ rotated 90 degrees around the origin. (Cont'd) $\endgroup$ – Akiva Weinberger Dec 6 '15 at 4:46
  • $\begingroup$ Conjugation plays well with multiplication. $\overline{xy}=\bar x\cdot\bar y$. I'll omit the proof. Define $|z|$ (the magnitude of $z$) to be the distance from $z$ to $0$. Thus, if $z=p+qi$, then $|z|=\sqrt{p^2+q^2}$ by the Pythagorean theorem. Note that $|z|=|\bar z|$. Also, $\sqrt{z\bar z}=\sqrt{(p+qi)(p-qi)}=\sqrt{p^2+q^2}=|z|$. Thus, given $z$ and $\bar z$, we can find $|z|$ by the formula $|z|=\sqrt{z\bar z}$. Another nice thing is that magnitudes play well with multiplication; $|xy|=|x|\cdot|y|$. Proof: $|xy|=\sqrt{xy\overline{xy}}=\sqrt{x\bar x}\sqrt{y\bar y}=|x||y|$. (Cont'd) $\endgroup$ – Akiva Weinberger Dec 6 '15 at 4:52
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Wow! This is wonderful solution and exactly the way I wanted to do it. Thanks! I will accept your answer in a day or two, provided there are no better answers. $\endgroup$ – Gaurang Tandon Dec 5 '15 at 12:07
  • 1
    $\begingroup$ @GaurangTandon You are welcome! $\endgroup$ – RTJ Dec 5 '15 at 12:20
  • $\begingroup$ You should probably expand the last argument a bit, like: the number of odd squares must be even (because 0 is even), every odd square consists of one odd and one even a_i (thus total number of odd a_i from this is even), every even square consists of an even number of odd a_i (thus total number of odd a_i from this is also even). $\endgroup$ – hkBst Mar 9 '16 at 13:45
6
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I like how you use the diagonals to reinterpret the knight's move if p+q is even. I think you could even eliminate case 2 if you instead induct on the largest coordinate instead of on the sum. That way the contrast (number of cases to consider) with the current top answer is more pronounced. $\endgroup$ – hkBst Mar 9 '16 at 14:06
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why does returning to the same point require $p$ of the first type of moves and $q$ of the second? $\endgroup$ – Sandeep Silwal Dec 6 '15 at 18:19
  • $\begingroup$ By (p,q)=1, did you mean gcd(p,q)=1? I suppose this follows from a scaling argument if it is not initially the case. And if you eliminate all factors of 2 from one side, then the only way for p+q to be even is if both are odd. Then we can reuse case 2 from TonyK's answer: each coordinate changes from odd to even and vice versa with every step, so there must be an even number of steps. $\endgroup$ – hkBst Mar 9 '16 at 14:45
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why can we separate the $p$ moves and $q$ moves? Remember that the knight can move $p$ up and $q$ right, and well as $p$ right and $q$ up. The $p$ of the first move is not orthogonal to the $q$ of the second. $\endgroup$ – Akiva Weinberger Dec 6 '15 at 0:47
  • $\begingroup$ Like Akiva says, if for example p=2, q=1, then forward does not have to equal -backward, since 2!=1. Given Akiva's answer which shows that p and q need not be integer (but you can rescale such that at least one is), I cannot help but feel that there must be some way to rescue your argument, but I do not see it. $\endgroup$ – hkBst Mar 9 '16 at 14:28
  • $\begingroup$ This question clearly has a goal to help young people to become curious in wanting to learn more mathematics. Your attitude does not help here. $\endgroup$ – mathreadler Mar 10 '16 at 10:00
0
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ I do not see why your necessary conditions hold. $\endgroup$ – hkBst Mar 9 '16 at 14:39
  • $\begingroup$ @hkBst In order to have returned to (0,0), every sum of motions in the $x$ and $y$ directions must be canceled by an equal and opposite sum of motions. If we now ignore axes, we can say that in order to have returned, for every motion of magnitude $+p$ (whether it was taken in $x$ or $y$ direction), there has to be another, corresponding motion $-p$ (we don't care whether it was taken in the same axis as the $+p$ motion). That means 1. They must sum up to 0 when the knight has returned and 2. Their absolute sum is $(2r|p|+2s|q|)$ for some $r,s$. Whence comes the weakened, necessary condition. $\endgroup$ – Iwillnotexist Idonotexist Mar 9 '16 at 17:44
0
$\begingroup$

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;

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ As the problem is stated, the length of the jump is not given to be $1$ in one direction and $2$ in the other. That is correct for the piece in chess (whether a knight or horse) but not necessarily here. $\endgroup$ – Ross Millikan Dec 5 '15 at 23:08
  • $\begingroup$ Yep you are right. That was sloppy of me to not notice. $\endgroup$ – mathreadler Dec 6 '15 at 11:37
  • $\begingroup$ Given the standard checkering of a chessboard and the knight being color-changing, the stronger claim (that in an odd number of moves no squares of the same color can be visited) immediately follows. Thus I fail to see any residual merit to your answer. Please correct me if I missed something. $\endgroup$ – hkBst Mar 9 '16 at 14:33
  • $\begingroup$ Hello hkBst. This question is probably not at all aimed for what you would consider merit - it is for increasing young peoples' curiosity in mathematics and encourage them to study mathematics. $\endgroup$ – mathreadler Mar 10 '16 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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