Subset of knight's move in chess.

A particle is allowed to move in the $\mathbb{Z}\times \mathbb{Z}$ grid by choosing any of the two jumps:

1) Move two units to right and one unit up

2) Move two units up and one unit to right.

Let $P=(30,63)$ and $Q=(100,100)$, if the particle starts at origin then?

a) $P$ is reachable but not $Q$.

b) $Q$ is reachable but not $P$.

c) Both $P$ and $Q$ are reachable.

d) Neither $P$ nor $Q$ is reachable.

I could make out that the moves given are a subset of that of a knight's in chess. I think that it'd never be able to reach $(100,100)$ but I'm not sure of the reason. It has got to do something with the move of the knight but I cannot figure out what.

I don't have a very good idea about chess, so I'd be glad if someone could answer elaborately.

Solution 1:

Both possible moves increase the sum of coordinates by $3$, so any reachable position must have the sum of coordinates a multiple of $3$. This means $Q$ is not reachable, since its sum of coordinates is $200$, not divisible by $3$.

$P$ is also not reachable – to reach an $x$-coordinate of $30$ it must make at most $30$ jumps, which means that the highest $y$-coordinate it could reach is $2×30=60<63$.

Solution 2:

The above posts are certainly sufficient answers, but for fun I thought I would precisely characterize the set of points that can be reached from the origin.

Note that performing a move of type (1) amounts to adding $(2,1)$ to the particle's position vector, and, likewise, a move of type (2) amounts to adding $(1,2)$ to the particle's position vector. Therefore the points the particle can reach from the origin are precisely those points of the form $$ n(1,2) + m(2,1) = (n + 2m, 2n + m) $$ for nonnegative integers $n,m$. This is a precise characterization of the accessible points, but it isn't very easy to check.

It turns out that the much easier to check set of conditions

1. $a + b$ is divisible by $3$

2. $2a \geq b \geq \frac{a}{2}$

are necessary and sufficient for a point $(a,b)$ to be accessible.

To see this, suppose $(a,b)$ is accessible. Then there exist nonnegative integers $n,m$ such that \begin{align} n + 2m &= a\\ 2n + m &= b \end{align} Thus $$ a + b = 3n + 3m = 3(n + m) $$ which, since $n,m$ are nonnegative integers, shows that $a + b$ is divisible by $3$. Solving for $n$ and $m$, we find \begin{align} n &= \frac{1}{3}(2b - a) \\ m &= \frac{1}{3}(2a - b) \end{align} Since $n,m$ are nonnegative integers, we have \begin{align} 0 &\leq \frac{1}{3}(2b - a) \\ 0 &\leq \frac{1}{3}(2a - b) \end{align} The first of these inequalities implies $b \geq \frac{a}{2}$, and the second implies $b \leq 2a$, i.e. $2a \geq b \geq \frac{a}{2}$.

Conversely, suppose that conditions 1 and 2 hold for some point $(a,b)$. By condition 1, there exists an integer $k$ such that $a + b = 3k$. Take $n = b - k$ and $m = a - k$. Note that $k = \frac{a + b}{3}$. We compute \begin{align} n &= b - k = b - \frac{a + b}{3} = \frac{2b - a}{3} \geq \frac{2\frac{a}{2} - a}{3} = \frac{a - a}{3} = 0 \\ m &= a - k = a - \frac{a + b}{3} = \frac{2a - b}{3} \geq \frac{2a - 2a}{3} = 0 \end{align} Thus, $n$ and $m$ are nonnegative integers. Moreover \begin{align} (n + 2m, 2n + m) &= ((b - k) + 2(a - k) , 2(b - k) + (a - k)) = (b + 2a - 3k, 2b + a - 3k) \\&= (b + a + a - 3k, b + b + a - 3k) = (3k + a - 3k, b + 3k - 3k) = (a,b) \end{align} By our original characterization of the accessible points, this shows that $(a,b)$ is an accessible point.

Solution 3:

Note that starting from $(x,y)$ we can reach $(X,Y)\in\{(x+2,y+1),(x+1,y+2)\}$. In any case if $X+Y-(x+y)$ is divisible by $3$. This means that if we start from the origin $(0,0)$ then we can not reach $(X,Y)$ if $X+Y$ is not divisible by $3$. So you are correct $(100,100)$ is not reachable.

What about $(30,63)$?