A stone placed on the $X-Y$ plane moving along points with positive integer co-ordinates. When the stone is at $(x,y)$, it can be moved to $(3x,y)$ or $(x,3y)$ or $(x-z,y-z)$ where $z \in \mathbb{Z}^+$. Find all possible value $m,n$ of order pair $(m,n)$, where $m, n \in \mathbb{Z}^+$ such that the stone can be moved from $(m,n)$ to $(0, 0)$.

Is my answer correct ?

Consider 2 cases :

1) $x\not= y$, WLOG, $y>x$.

Let $l \in \mathbb{N}_0$ such that $3^lx \leq y<3^{l+1}x $

Since $3x-x$ is even, $x-y=(x-z)-(y-z)$ and $0-0=0$, so $m,n$ have the same parity.

$\exists t \in \mathbb{N}_0$, $y=3^lx+2t$

Since $y<3^{l+1}x $ so $t<3^lx$.

Thus, $(x,y) = (x,3^lx+2t) \rightarrow (3^lx,3^lx+2t)$

As $t<3^lx$, so $(3^lx,3^lx+2t) \rightarrow (t,3t) \rightarrow (3t,3t) \rightarrow (0, 0)$

2) $x=y$ we get $(x,y)\rightarrow (x-y,y-y)\rightarrow (0, 0)$

Answer : All positive integers, $m, n$ that have the same parity or $m\equiv n(\bmod{2})$.

  • $\begingroup$ Sounds like we are allowed to make a sequence moves as long as each move obeys the rules? Are we to assume that $x\ge0,y\ge0$ throughout, or does the playing arena also contain points with negative coordinates (not that it matters much because once the stone dips into the negative side it can never come back?). $\endgroup$ – Jyrki Lahtonen Aug 24 '17 at 13:17
  • $\begingroup$ Anyway, your method looks fine to me. $\endgroup$ – Jyrki Lahtonen Aug 24 '17 at 13:19
  • $\begingroup$ take (x,y)=(1,3), we then get (3,3),(1,9), and and pairing with a difference of two so it doesn't go directly to (0,0).I think this was @JyrkiLahtonen's point. $\endgroup$ – user451844 Aug 24 '17 at 13:23
  • $\begingroup$ @ Jyrki Lahtonen♦, Edited, thank you. $\endgroup$ – carat Aug 24 '17 at 13:31
  • $\begingroup$ Ok. I was slightly worried about starting positions like $(x,y)=(2,0)$ that satisfies the parity condition, but won't let you move away from the $x$-axis. $\endgroup$ – Jyrki Lahtonen Aug 24 '17 at 13:32

You're right, but there is an easier way of going about it (in my opinion).

You're totally right to say that $m$ and $n$ must have the same parity, since multiplying an integer by $3$ preserves parity, and reducing $m$ and $n$ by the same integer $z$ preserves their relative parity. Ergo, since $0$ and $0$ have the same parity, so too must $m$ and $n$.

There are then, as you say, two cases. The case $m=n$ is trivial, and in the case $m\neq n$ (setting $m<n$ w.l.o.g.), one can always reduce $(m,n)$ to $(1,n-m+1)$, where $n-m+1$ is odd because we insist $m\equiv n\ (\mathrm{mod\ 2})$. Then we can just repeat the following two steps:

  • Triple the $1$: $(1,x) \to (3,x)$
  • Subtract $2$ from each integer: $(3,x) \to (1,x-2)$

Repeat until we are left with $(1,3)$, which we must reach eventually. This then goes to $(3,3)$ and hence we reach $(0,0)$.

  • $\begingroup$ Nice and easy. Thank you very much ! $\endgroup$ – carat Aug 24 '17 at 13:42

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.