Let $a$ and $b$ be two positive integers satifying $gcd(a, b) = 1$. Consider a pawn standing on the grid point $(x, y)$. A step of type A consists of moving the pawn to one of the following grid points: $(x+a, y+a),(x+a,y-a), (x-a, y + a)$ or $(x - a, y - a)$. A step of type B consists of moving the pawn to $(x + b,y + b),(x + b,y - b), (x - b,y + b)$ or $(x - b,y - b)$. Now put a pawn on $(0, 0)$. You can make a (nite) number of steps, alternatingly of type A and type B, starting with a step of type A. You can make an even or odd number of steps, i.e., the last step could be of either type A or type B. Determine the set of all grid points $(x,y)$ that you can reach with such a series of steps.
Problem
Source: Dutch IMO TST 2015 day 2 p1
Tags: grid, points, lattice points, combinatorics, combinatorial geometry
BlazingMuddy
30.08.2019 22:53
Any grid points $(x, y)$ with $x + y$ even.
Reinterpreting the points on the grids using Gaussian integers instead of Cartesian coordinates, the answer is equivalent to any Gaussian integers divisible by $1 + i$. A step of type A would be interpreted as moving from a point $z$ to $z + (1 + i)ac$ for some $c\in \{1, i, -1, -i\}$, while a step of type B would be interpreted as moving from a point $z$ to $z + (1 + i)bc$ for some $c\in \{1, i, -1, -i\}$. Obviously, as each step doesn't change value of the point that the pawn stands on modulo $1 + i$, all reachable points must be divisible by $1 + i$. Now, we claim that indeed they are all reachable.
Consider the set $T = \{(1 + i)(ac + bd) : c, d\in \{1, i, -1, -i\}\}$; that is, $T$ is the set of all Gaussian integers $t$ such that the pawn can move from $z$ to $z + t$ after performing exactly 2 steps, one of type A and another of type B. Observe that for any $c\in \{1, i, -1, -i\}$, we have $(1 + i)(a+bc) \in T$. Also, for any $t, u\in T$, we have $tc, t + u\in T$ for each $c\in \{1, i, -1, -i\}$, so if $t\in T$, we would also obtain that any point divisible by $t$ is also an element of $T$. We divide into two cases:
Case 1: $a + b$ is odd.
We claim that $1 + i\in T$, which is sufficient to prove our whole claim.
Since $a + b$ is odd, so is $a - b$, and thus $\gcd(a + b, a - b) = \gcd(a + b, 2a) = \gcd(a + b, a) = 1$ (in $\mathbb{Z}$). Using Bezout's lemma, there exists $q, r\in \mathbb{Z}$ such that $q(a+b) + r(a-b) = 1$. Now, since $(1 + i)(a + b) \in T$ and $(1 + i)(a - b) \in T$, we have $1 + i = (1 + i)(q(a + b) + r(a - b)) \in T$, so we are done.
Case 2: $a$ and $b$ are odd.
First, we claim that $2\in T$.
In this case, $\gcd(a + bi, a - bi) = \gcd(a + bi, 2bi) = \gcd(a + bi, 2i) = \{(1 + i)c : c\in \{1, i, -1, -i\}\}$ (in $\mathbb{Z}[i]$) as $\gcd(a + bi, b) = 1$. By Bezout's lemma, there exists $q, r\in \mathbb{Z}[i]$ such that $q(a + bi) + r(a - bi) = 1 - i$, and since $(1 + i)(a + bi), (1 + i)(a - bi)\in T$, we find $2 = (1 + i)(1 - i) \in T$.
Finally, let $z$ be an arbitrary point divisible by $1 + i$. If $2 | z$, then $z\in T$. Otherwise, since $a$ is odd, we would have $2 | z - a(1 + i)$, so $z - a(1 + i) \in T$. This implies that the pawn can reach $z - a(1 + i)$ from $0$ using a valid sequence of alternating steps ending with a step of type $B$. Then, we finish with the step $z - a(1 + i) \mapsto z$ of type $A$.