Let $q$ be a positive rational number. Two ants are initially at the same point $X$ in the plane. In the $n$-th minute $(n = 1,2,...)$ each of them chooses whether to walk due north, east, south or west and then walks the distance of $q^n$ metres. After a whole number of minutes, they are at the same point in the plane (not necessarily $X$), but have not taken exactly the same route within that time. Determine all possible values of $q$. Proposed by Jeremy King, UK
Problem
Source: BMO 2018
Tags: algebra
09.05.2018 17:30
do u have a pdf of the problems?
09.05.2018 20:21
Firstly $q=1$ works. We assume $q \neq 1$. Now write $q=\frac{p}{r}$ where $(p,r)=1$. Firstly we prove $r=1$. Let $m$ be the first minute the ants come back together after having gone on different routes. Note $m \geq 2$. WLOG the last move was a horizontal move. For contradiction take $r>1$ We consider the moves in the horizontal direction of ant $A,B$ only considering ones that were a different sign: $$\pm q^{a_1} \pm q^{a_2} \pm \cdots \pm q^{a_x}=\pm q^{b_1} \pm \cdots \pm q^{b_y}$$Where we let $a_1 <a_2<\cdots$ and similarly for $b$. As the last move is horizontal WLOG $b_y=m$. But now multiplying through by $r^{m-1}$ if $a_x<m$ then the $LHS$ is an integer but the $RHS$ isn't so we must have $a_x=m$. Furthermore $a_x,b_y$ must have opposite signs (due to minimality of $m$) and hence: $$2q^m \in \mathbb{Z} \Leftrightarrow \frac{2p^m}{r^m} \in \mathbb{Z} \Leftrightarrow \frac{2}{r^m} \in \mathbb{Z}$$But as $r,m>1$ we have $r^m \geq 4>2$ which is a contradiction so $r=1$. We now consider $q \in \mathbb{Z}$. At minute $n$ we let $A_n,B_n$ be the positions of ant $A,B$ respectively. Let $v_k=\vec{A_kB_k}$.Note that: $$v_k-v_{k-1}=\begin{pmatrix} \pm 2 q^k \\ 0 \end{pmatrix} \, , \, \begin{pmatrix} \pm q^k \\ \pm q^k \end{pmatrix} \, , \, \begin{pmatrix} 0 \\ 0 \end{pmatrix} \equiv \begin{pmatrix} 0\\ 0 \end{pmatrix} \mod{q^k}$$Let $l$ be the first minute at which the paths differ so: $$v_r=\begin{pmatrix} \pm 2 q^r \\ 0 \end{pmatrix} \, , \, \begin{pmatrix} \pm q^r \\ \pm q^r \end{pmatrix}$$For the latter as $v_k$ is unchanged $\mod{q^r+1}$ for $k \geq r$ it follows it can never equal $\begin{pmatrix} 0 \\ 0 \end{pmatrix}$.This is also the case for the former if $q \neq 2$. So we must have $q=2$ in which case: $v_r = \begin{pmatrix} q^{r+1} \\ 0 \end{pmatrix}$. Now considering $v_{r+1} \mod{2^{r+2}}$ we see we can never have $v_{r+1} \equiv \begin{pmatrix} 0 \\ 0 \end{pmatrix} \mod{2^{r+2}}$ but for $k \geq r+1$. $v_{r+1}$ is unchanged $ \mod{2^{r+2}}$ which gives a contradiction. So $q=1$ is the only possibility.
10.05.2018 19:30
The distance covered by the $i$-th ant ($i \in \{1, 2\}$) in the $j$-th direction ($j \in \{x, y\}$) after $n$ steps has to be $\sum_{k=1}^{n}a_{ijk}q^k$, where $a_{ijk}$ can only be $1$, $-1$ or $0$, when the projection of the ant on the $j$-axis moves in the positive direction, moves in the negative direction, or stays at the same point respectively, on the $k$-th step. Observe that $a_{ixk}$ is $1$ or $-1$ iff $a_{iyk} = 0$ and consider the polynomials $P_i(x) = \sum_{k=1}^{n}(a_{ixk} + a_{iyk})x^k$ and $Q_i(x) = \sum_{k=1}^{n}(a_{ixk} - a_{iyk})x^k$ which have coefficients equal to $1$ or $-1$. Then if both ants have covered distance $d_x$ on the $x$-axis and $d_y$ on the $y$-axis, we have $P_1(q) = P_2(q) = d_x + d_y$ and $Q_1(q) = Q_2(q) = d_x - d_y$, meaning that $q$ is a root of the polynomials $P = \frac{P_1 - P_2}{2}$ and $Q = \frac{Q_1 - Q_2}{2}$ whose coefficients are all equal to $0$, $1$ or $-1$. If both $P$ and $Q$ are identically equal to zero, we have for every $k \leq n$: $a_{1xk} + a_{1yk} = a_{2xk} + a_{2yk}$ and $a_{1xk} - a_{1yk} = a_{2xk} - a_{2yk}$. Adding and subtracting these two we have for every $k \leq n$: $a_{1xk} = a_{2xk}$ and $a_{1yk} = a_{2yk}$. This means that the two ants have moved in exactly the same way, contradiction. Thus at least one of $P$, $-P$, $Q$ and $-Q$, WLOG $P$, is a nonzero monic polynomial with integer coefficients having $q$ as a root, meaning that $q$ has to be integer. Let $m = deg(P)$, then $q^m$ is a sum of different terms of the form $q^l$ for $l \leq m-1$, meaning that $q^m \leq 1 + q + ... + q^{m-1}$. The last can be true for $q = 1$ which clearly works in our problem (for example, let the ants move in the opposite directions and then come back), but for $q > 1$ it is equivalent to $q^m \leq \frac{q^m - 1}{q - 1} \leq q^m - 1$, a contradiction. Thus $q=1$ is the only possible value.
11.05.2018 10:20
This problem was proposed by Jeremy King of the United Kingdom.
15.11.2018 07:22
Here's a shorter solution, hopefully correct: Hamel wrote: Let $q$ be a positive rational number. Two ants are initially at the same point $X$ in the plane. In the $n$-th minute $(n = 1,2,...)$ each of them chooses whether to walk due north, east, south or west and then walks the distance of $q^n$ metres. After a whole number of minutes, they are at the same point in the plane (not necessarily $X$), but have not taken exactly the same route within that time. Determine all possible values of $q$. We show that $q=1$ is the only possibility. Claim: $q \in \{1,2,2^{-1}\}.$ Proof: Consider the ants in the complex plane. Let the $i$th move of ant $1, 2$ be denoted by $\varepsilon_i, \varepsilon'_i$ respectively. Clearly $\varepsilon_i, \varepsilon_i' \in \{\pm 1, \pm i\}.$ Then we have (if they meet at the $n$th minute) \begin{align} \sum_{i=1}^n \varepsilon_iq^i=\sum_{i=1}^n \varepsilon_i'q^i \Leftrightarrow \sum_{i=1}^{n} \left( \varepsilon_i-\varepsilon_i' \right) q^{i-1}=0 \end{align}(note that we have divided the sides by $q)$ Conjugating $(1)$ we find that for every $\varepsilon_i,$ $1,-1$ remain unchanged while $i \mapsto -i$ and $-i \mapsto i.$ Thus adding this conjugated equation to $(1)$ we find that every coefficient of $q^k$ is either $0, \pm 2$ or $\pm 4.$ Noting that the root of this polynomial is a positive rational, we get by the Rational Root Theorem that $q \in \{1,2,2^{-1}\},$ as claimed. $\square$ Clearly, $q=1$ works. Now for $q=2,$ call the $\text{left-right}$ moves as $i$ moves and the $\text{up-down}$ moves as $j$ moves. Since their paths are not exactly the same, hence at least one of the $i, j$ moves are different for the two ants, say $i.$ But note for the $i$ moves we must then have $\pm 2^{x_1} \pm \cdots \pm 2^{x_r}=\pm 2^{y_1}\pm \cdots \pm 2^{y_s}$ for some $r,s, \{x_i\} \ne \{y_i\}$ and $x_1 < \cdots x_r$ and $y_1 < \cdots y_s.$ Take the positive terms on one side and the negative on the other, and then you have a contradiction as you get two binary numbers are equal. When $q=2^{-1},$ we move in the reverse direction, i.e. start at the endpoint and move towards the starting point. Then the case $q=2^{-1}$ melts to the case $q=2.$ which we have shown is not possible. $\blacksquare$
07.11.2024 23:39
P2 let us say that they reach $(x,y)$ from $(0,0)$, then we take any m from n powers of $q^n$ with positive and negative sign for $x$ and $y$ twice for $2$ different ways to go, I will go with an example of $n=7$, lets say $^3+q-q^5 = x = q^2+q^7$ and $q^4-q^2-q^6+q^7 = y = q^3+q+q^4+q^5-q^6$ then $q^3+q-q^5-q^2-q^7=0$ and $q^4-q^2-q^6+q^7 -(q^3+q+q^4+q^5-q^6)= -q^2+q^7-q^3-q-q^5=0$, when we add both of them we are left with a coefficient of $\pm2$ or $0$, which we can take $2$ common to give this(with some terms missing) $q^n \pm q^{n-1} \pm ...\pm1=0$ and for rational solutions assume some $a/b$(reduced) then, after multiplying on both sides with $b^n$($n$ is highest power left) observe that $b|1$ and $a|1$, so $q$ can be only $1$. Edit: Someone suggested me that I forgot to prove that the polynomial after summing can also have all $0$ coefficients, for that they provided a fix which was to subtract them and if it was still a zero polynomial then the paths weren't distinct. Awesome fix.