Mfcttrf

A particle is allowed to move in the $mathbbZtimes mathbbZ$ 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.

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

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

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
beginalign
n + 2m &= a\
2n + m &= b
endalign
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
beginalign
n &= frac13(2b - a) \
m &= frac13(2a - b)
endalign
Since $n,m$ are nonnegative integers, we have
beginalign
0 &leq frac13(2b - a) \
0 &leq frac13(2a - b)
endalign
The first of these inequalities implies $b geq fraca2$, and the second implies $b leq 2a$, i.e. $2a geq b geq fraca2$.

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 = fraca + b3$. We compute
beginalign
n &= b - k = b - fraca + b3 = frac2b - a3 geq frac2fraca2 - a3 = fraca - a3 = 0 \
m &= a - k = a - fraca + b3 = frac2a - b3 geq frac2a - 2a3 = 0
endalign
Thus, $n$ and $m$ are nonnegative integers. Moreover
beginalign
(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)
endalign
By our original characterization of the accessible points, this shows that $(a,b)$ is an accessible point.

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