10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Although the motivation of this problem is the movement of a chess piece, the problem is not really about chess; all you need is logic and rules $1$ and $2$ above. (In actual chess, the knight can make up to eight different moves, with the $1$ and $2$ unit increments replaced by $\pm1$ and $\pm2$.) $\endgroup$ – Brian Tung Jun 27 '19 at 18:39
  • $\begingroup$ @BrianTung: Good point, and as the answers show this allows many fewer squares to be reached because the sum $\bmod 3$ of the coordinates is maintained. The particle cannot go backwards in either direction, so both coordinates are monotonic. $\endgroup$ – Ross Millikan Jun 27 '19 at 19:58
24
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ It may also be worth exploring briefly why this logic doesn't apply to a real chess knight, which isn't restricted to the upper-right quadrant of movement and can thereby reach every square of the board. In the upper-left and lower-right quadrants the coordinate sum changes by ±1, while in the lower-left quadrant it decreases by 3. $\endgroup$ – Chromatix Jun 28 '19 at 3:13
  • 4
    $\begingroup$ @Chromatix That is simply because you can reach $(0,1)$ with three ordinary knight moves, and because you can here reflect those moves to reach $(\pm1,0)$ and $(0,\pm1)$, hence every square. $\endgroup$ – Parcly Taxel Jun 28 '19 at 4:08
18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Indeed very interesting, Thank you for the exact conditions. $\endgroup$ – Tapi Jun 27 '19 at 20:01
  • 1
    $\begingroup$ For what it's worth you can slightly simplify (at most marginally, it's really a matter of opinion) this argument with some modular arithmetic. In particular, solving the system of linear equations for $m$ and $n$ explicitly as you've done, on may by the same logic note the necessary inequality and sum. But furthermore, one may immediately note, as is done that, if the inequality is satisfied, $m$ and $n$ will be positive, and one may also note that $2a-b \equiv 2b-a \equiv -(a+b) \pmod 3$, so that we've produced a working pair without explicitly considering such a $k$ $\endgroup$ – Cade Reinberger Jun 28 '19 at 3:00
  • 2
    $\begingroup$ I wanted to avoid modular arithmetic in favor of a more elementary answer, but you're right that it would condense the exposition. The one upshot of my approach is that you get explicit expressions for $n$ and $m$, which, as can be easily checked, are unique. My answer tells you how to move the knight to get from the origin to an accessible point. That's beyond the scope of OP's original question, but I do think it's kind of interesting. $\endgroup$ – Charles Hudgins Jun 28 '19 at 6:15
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'd say "a nonnegative integer number of times"; of course some destination squares can be reached with all $U$ moves or all $R$ moves. Otherwise a fine solution. $\endgroup$ – bof Jun 29 '19 at 6:50
0
$\begingroup$

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.

$\endgroup$

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.