Generalized knight going from one corner of a box to the other

88 Views Asked by At

Generalize the notion of a knight from chess to a $(x, y)$-knight such that $x \leq y$ and the knight can move any of the $8$ combinations defined by $(\pm x, \pm y)$ or $(\pm y, \pm x)$. Thus a chess knight is a $(1, 2)$-knight.

A $(x, y)$-knight starts at $(0,0)$ and wishes to go to the position $(m, n)$ while staying within the rectangle lattice defined by these two opposite corners. Is there any literature about when this is possible for a $(x, y)$-knight?

I think there may be something involving $\gcd(x, y)$ here due to the definition of gcd being the minimal positive value of $ux+vy$, but there are some complications using this method that I can't resolve.

1

There are 1 best solutions below

0
On

Partial answer only. For unrestricted boards.

An individual move has $8$ possible forms: $(\pm x, \pm y), (\pm y, \pm x)$. In a path from $(0,0)$ to another location, count how many moves are made of each type: $$\begin{array} {cc}{\begin{array} {c|c} \text{count} & \text{move}\\\hline a_0 &(+x, +y)\\a_1&(+x,-y)\\a_2&(-x,+y)\\a_3&(-x,-y)\end{array}}&{\begin{array} {c|c} \text{count} & \text{move}\\\hline b_0 &(+y, +x)\\b_1&(+y,-x)\\b_2&(-y,+x)\\b_3&(-y,-x)\end{array}}\end{array}$$

The final position $(u,v)$ is the sum of all the individual moves, so $$u = (a_0+a_1-a_2-a_3)x + (b_0 + b_1 - b_2 - b_3)y\\v = (a_0-a_1+a_2-a_3)x + (b_0 - b_1 + b_2 - b_3)y$$ i.e., any position occupied must have linear combinations of $x, y$ as its coordinates.

Now suppose $m = Ax + By, n = Cx + Dy$ for some $A, B, C, D$. In order for this position to be reached, we must have $$a_0+a_1-a_2-a_3 = A\\b_0 + b_1 - b_2 - b_3 = B\\a_0-a_1+a_2-a_3 = C\\b_0 - b_1 + b_2 - b_3 = D$$ And so $$a_0 - a_3 = \frac{A+C}2\\a_1 - a_2 = \frac{A-C}2\\b_0 - b_3 = \frac{B+D}2\\b_1 - b_2 = \frac{B-D}2$$ Which is clearly accomplishable (with non-negative move counts) provided that $A$ and $C$ have the same parity, and $B$ and $D$ have the same parity.

So the problem reduces to which $m,n$ can be expressed as linear combinations of $x, y$ with the same parity on the coefficients of $x$ and of $y$.