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$.
The solution goes as follows:
Consider the ants' positions $a_k$ and $b_k$ after $k$ steps in the complex plane, assuming that their initial positions are at the origin and that all steps are parallel to one of the axes. We have $a_{k+1}-a_k=a_kq^k$ and $b_{k+1}-b_k=b_kq^k$ with $a_k,b_k\in \{1,-1,i,-i\}$.
If $a_n=b_n$ for some $n>0$, then:
$\sum\limits_{k=0}^{n-1}(a_k-b_k)q^k=0$, where $a_k-b_k\in\{0, \pm1 \pm i, \pm2, \pm2i\}$.
Note that the coefficients $a_k-b_k$ is always divisible by $1+i$ in Gaussian integers:
Hence $c_0+c_1q+…+c_{n-1}q^{n-1}=0$. Therefore if $q=\frac{a}{b}$ we have $a|c_0$ and $b|c_{n-1}$ in Gaussian integers, which is only possible if $a=b=1$.
Could you please explain a solution without the use of complex numbers and Gaussian integers?
Best Answer
Let's simplify the problem to the 1-D case first:
The approach that we take is similar to the given solution, where we apply the Rational Root Theorem for the appropriate field:
Let $a_k, b_k \in \{ 1, -1 \}$ denote whether the ant walked east or west for the kth step.
Then, we are given that $ \sum_{k\geq 0} a_k q^k = \sum b_k q^k$, and $ a_k \neq b_k$ for some $k$.
We have $ (a_k - b_k) q^k = 0$, and $ a_k - b_k \in \{ -2, 0, 2 \}$.
Since all of the coefficients are integers, we apply the rational root theorem to conclude that roots $q > 0 $ could only be $ \frac{1}{2}, 1, $ or $2$.
If $ q = 1$, we have a solution, eg $(a_1, a_2 ) = (-1, 1), (b_1, b_2 ) = (1, -1)$.
If $ q = 1/2$, then by considering the smallest $K$ in which $ a_K \neq b_K$, show that these ants can never meet at any point in time, not just whole minutes. (Basically, $2 \times \frac{1}{2^K} > \sum_{k> K } 2 \frac{1}{2^k}$ because we have finitely many steps.)
If $ q = 2$, then by considering the largest $K$ in which $a_K \neq b_K$, likewise show that these ants can never meet.
This solution also works for the 2-D case:
Let $a_k, b_k \in \{ 1, -1 , 0\}$ denote whether the ant walked east or west or north/south for the kth step. (In particular, we don't differentiate between the ants walking north or south.)
By focusing on the x-coordinate, we have $ (a_k - b_k) q^k = 0$, and $ a_k - b_k \in \{ -2, -1, 0, 1, 2 \}$.
The rest of the solution is identical to the 1-D case.
Note: