Subset of knight's move in chess.

Question

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.

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

Answer 2

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)$?

Answer 3

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.

Answer 4

If $U$ is the number of move up twice moves, and $R$ is the number of move right twice moves, we have that the final position is $(2R+U,R+2U)$

For $P$, we have:

$ 2R+U = 30, R+2U=63$
$U = 30-2R$
$R+2(30-2R)=63$
$-3R+60=63$
$-3R=3$
$R=-1$

Since each move must be made a nonnegative integer number of times, this is impossible.

For $Q$, similar math gets that $3R=100$, which again does not permit a nonnegative integer solution.

Answer 5

Let a be the count of the first move and b be the count of the second move.

$$(x,y) = (2,1)a + (1,2)b$$

Where x an y are nonnegative integers representing our position and a position is reachable if a and b are both nonnegative integers.

$$x = 2a + b$$

$$y = 2b + a$$

We have two linear equations and two unknowns, so we expect exactly one pair of a and b for each pair of x and y, the question then is are a and b nonnegative integers?

$$2y = 4b + 2a$$

$$2y - x = 3b$$

$$b=\frac{2y-x}{3}=y-\frac{x+y}{3}$$

$$x = 2a + \frac{2y-x}{3}$$

$$3x = 6a + 2y-x$$

$$4x -2y = 6a$$

$$a = \frac{2x-y}{3}=x-\frac{x+y}{3}$$

Requiring that a and b are nonnegative integers now gives us several conditions.

1. $2y \geqslant x$
2. $x \geqslant 2y$
3. $x+y$ is divisible by 3

Your first position fails critera 1, your second position fails critera 2.