Prove that it is always possible to have solution of $2^k - a\cdot m = n$ when $k\ge 0, a \ge 0$ and $\operatorname{gcd}(m,n) = 2^x$

Question

I recently encountered a coding question which I was not able to solve but when I saw other's solution then I found out that they are using GCD property to deduce optimized solution.

Below is the problem statement.

There exists an infinitely large grid. You are currently at point (1, 1), and you need to reach the point (targetX, targetY) using a finite number of steps.

In one step, you can move from point (x, y) to any one of the following points:

• (x, y - x)
• (x - y, y)
• (2 * x, y)
• (x, 2 * y)

Given two integers targetX and targetY representing the X-coordinate and Y-> coordinate of your final position, return true if you can reach the point from (1, 1) using some number of steps, and false otherwise.

Accepted Solution:

class Solution {
    public boolean isReachable(int targetX, int targetY) {
        int gcd = gcd(targetX, targetY);
        return (gcd & (gcd - 1)) == 0;
    }

    int gcd(int x, int y) {
        if (x < y) return gcd(y, x);
        if (y == 0) return x;
        return gcd(y, x % y);
    }
}

So basically solution exists only if $GCD(targetX, targetY) = 2^k, k >= 0$.

I asked for the proof $2^k - a\cdot m = n$ when $k\ge 0, a \ge 0$ and $\operatorname{gcd}(m,n) = 2^x$ because we can always go to the point $(m, 1)$ from point $(1,1)$ but to go to the point $(m, n)$ from there we will need to prove the above statement.

I am not able to understand why this is necessary and sufficient condition?

Can someone please add a proof of this along with some intuition.

Answer 1

I would rephrase the problem as follows. We have four allowed transformations to get away from point $(x,y).$ \begin{align*} A\, &: \,\begin{pmatrix}x\\y\end{pmatrix}\longmapsto \begin{pmatrix}1&0\\-1&1\end{pmatrix}\cdot\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}x\\y-x\end{pmatrix}\\[8pt] B\, &: \,\begin{pmatrix}x\\y\end{pmatrix}\longmapsto \begin{pmatrix}1&-1\\0&1\end{pmatrix}\cdot\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}x-y\\y\end{pmatrix}\\[8pt] C\, &: \,\begin{pmatrix}x\\y\end{pmatrix}\longmapsto \begin{pmatrix}2&0\\0&1\end{pmatrix}\cdot\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}2x\\y\end{pmatrix}\\[8pt] D\, &: \,\begin{pmatrix}x\\y\end{pmatrix}\longmapsto \begin{pmatrix}1&0\\0&2\end{pmatrix}\cdot\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}x\\2y\end{pmatrix} \end{align*}

Any path from $(1,1)$ to $(x,y)$ is $P(1,1)^T=(x,y)^T$ where $P$ is a word over the alphabet $A,B,C,D,$ i.e. any finite product of these four matrices. It is immediately clear that every path has a determinant $2^k$ for some non-negative integer $k$ depending on the number of matrices $C,D$ in $P.$

Let $P=\begin{pmatrix}a&b\\c&d\end{pmatrix}.$ Then $a+b=x\, , \,c+d=y\, , \,ad-bc=2^k.$

We have now a word problem, so ordering the matrices within $P$ could be the next step. I would start with $C$ and $D$ and pull them at the beginning of $P.$

Another possibility is to prove that all values $a,b,c,d$ can be reached as long as the determinant $ad-bc$ is a power of two.