
A2. Two ants start at the same point in the plane. Each minute they choose whether to walk due north, east, south or west. They each walk 1 meter in the first minute. In each subsequent minute the distance they walk is multiplied by a rational number $q>0$. They meet after a whole number of minutes, but have not taken exactly the same route within that time. Determine all possible values of $q$.

(United Kingdom)


## Solution.

Answer: $q=1$.

Let $x_{A}^{(n)}$ (resp. $x_{B}^{(n)}$ ) be the $x$-coordinates of the first (resp. second) ant's position after $n$ minutes. Then $x_{A}^{(n)}-x_{A}^{(n-1)} \in\left\{q^{n},-q^{n}, 0\right\}$, and so $x_{A}^{(n)}, x_{B}^{(n)}$ are given by polynomials in $q$ with coefficients in $\{-1,0,1\}$. So if the ants meet after $n$ minutes, then

$$
0=x_{A}^{(n)}-x_{B}^{(n)}=P(q)
$$

where $P$ is a polynomial with degree at most $n$ and coefficients in $\{-2,-, 1,0,1,2\}$. Thus if $q=\frac{a}{b}(a, b \in \mathbb{N})$, we have $a \mid 2$ and $b \mid 2$, i.e. $q \in\left\{\frac{1}{2}, 1,2\right\}$.

It is clearly possible when $q=1$.

We argue that $q=\frac{1}{2}$ is not possible. Assume that the ants diverge for the first time after the $k$ th minute, for $k \geqslant 0$. Then

$$
\left|x_{B}^{(k+1)}-x_{A}^{(k+1)}\right|+\left|y_{B}^{(k+1)}-y_{A}^{(k+1)}\right|=2 q^{k}
$$

But also $\left|x_{A}^{(\ell+1)}-x_{A}^{(\ell)}\right|+\left|y_{A}^{(\ell+1)}-y_{A}^{(\ell)}\right|=q^{\ell}$ for each $l \geqslant k+1$, and so

$$
\left|x_{A}^{(n)}-x_{A}^{(k+1)}\right|+\left|y_{A}^{(n)}-y_{A}^{(k+1)}\right| \leqslant q^{k+1}+q^{k+2}+\ldots+q^{n-1}
$$

and similarly for the second ant. Combining (1) and (2) with the triangle inequality, we obtain for any $n \geqslant k+1$

$$
\left|x_{B}^{(n)}-x_{A}^{(n)}\right|+\left|y_{B}^{(n)}-y_{A}^{(n)}\right| \geqslant 2 q^{k}-2\left(q^{k+1}+q^{k+2}+\ldots+q^{n-1}\right)
$$

which is strictly positive for $q=\frac{1}{2}$. So for any $n \geqslant k+1$, the ants cannot meet after $n$ minutes. Thus $q \neq \frac{1}{2}$.

Finally, we show that $q=2$ is also not possible. Suppose to the contrary that there is a pair of routes for $q=2$, meeting after $n$ minutes. Now consider rescaling the plane by a factor $2^{-n}$, and looking at the routes in the opposite direction. This would then be an example for $q=1 / 2$ and we have just shown that this is not possible.

