Maths Olympiad Prep

Library / /60 of 60

Number theory Difficulty 8.3 Shortlist Prove it Asia Pacific Mathematics Olympiad (APMO)

Larry and Rob are two robots travelling in one car from Argovia to Zillis. Both robots have control over the steering and steer according to the following algorithm: Larry makes a 9090^{\circ} left turn after every \ell kilometer driving from start; Rob makes a 9090^{\circ} right turn after every rr kilometer driving from start, where \ell and rr are relatively prime positive integers. In the event of both turns occurring simultaneously, the car will keep going without changing direction. Assume that the ground is flat and the car can move in any direction.
Let the car start from Argovia facing towards Zillis. For which choices of the pair ( ,r\ell, r ) is the car guaranteed to reach Zillis, regardless of how far it is from Argovia?

Solution

Let Zillis be dd kilometers away from Argovia, where dd is a positive real number. For simplicity, we will position Argovia at (0,0)(0,0) and Zillis at (d,0)(d, 0), so that the car starts out facing east. We will investigate how the car moves around in the period of travelling the first r\ell r kilometers, the second r\ell r kilometers, . . ., and so on. We call each period of travelling r\ell r kilometers a section. It is clear that the car will have identical behavior in every section except the direction of the car at the beginning.

Case 1: r2(mod4)\ell-r \equiv 2(\bmod 4). After the first section, the car has made 1\ell-1 right turns and r1r-1 left turns, which is a net of 2(r(mod4))2(\equiv \ell-r(\bmod 4)) right turns. Let the displacement vector for the first section be (x,y)(x, y). Since the car has rotated 180180^{\circ}, the displacement vector for the second section will be (x,y)(-x,-y), which will take the car back to (0,0)(0,0) facing east again. We now have our original situation, and the car has certainly never travelled further than r\ell r kilometers from Argovia. So, the car cannot reach Zillis if it is further apart from Argovia.

Case 2: r1(mod4)\ell-r \equiv 1(\bmod 4). After the first section, the car has made a net of 1 right turn. Let the displacement vector for the first section again be (x,y)(x, y). This time the car has rotated 9090^{\circ} clockwise. We can see that the displacements for the second, third and fourth section will be (y,x),(x,y)(y,-x),(-x,-y) and (y,x)(-y, x), respectively, so after four sections the car is back at (0,0)(0,0) facing east. Since the car has certainly never travelled further than 2r2 \ell r kilometers from Argovia, the car cannot reach Zillis if it is further apart from Argovia.

Case 3: r3(mod4)\ell-r \equiv 3(\bmod 4). An argument similar to that in Case 2 (switching the roles of left and right) shows that the car cannot reach Zillis if it is further apart from Argovia.

Case 4: r(mod4)\ell \equiv r(\bmod 4). The car makes a net turn of 00^{\circ} after each section, so it must be facing east. We are going to show that, after traversing the first section, the car will be at (1,0)(1,0). It will be useful to interpret the Cartesian plane as the complex plane, i.e. writing x+iyx+i y for (x,y)(x, y), where i=1i=\sqrt{-1}. We will denote the kk-th kilometer of movement by mk1m_{k-1},
which takes values from the set {1,i,1,i}\{1, i,-1,-i\}, depending on the direction. We then just have to show that
k=0r1mk=1 \sum_{k=0}^{\ell r-1} m_{k}=1
which implies that the car will get to Zillis no matter how far it is apart from Argovia.

Case 4a: r1(mod4)\ell \equiv r \equiv 1(\bmod 4). First note that for k=0,1,,r1k=0,1, \ldots, \ell r-1,
mk=ik/(i)k/r m_{k}=i^{\lfloor k / \ell\rfloor}(-i)^{\lfloor k / r\rfloor}
since k/\lfloor k / \ell\rfloor and k/r\lfloor k / r\rfloor are the exact numbers of left and right turns before the (k+1)(k+1)st kilometer, respectively. Let ak(k(mod))a_{k}(\equiv k(\bmod \ell)) and bk(k(modr))b_{k}(\equiv k(\bmod r)) be the remainders of kk when divided by \ell and rr, respectively. Then, since
ak=kkkk(mod4) and bk=kkrrkkr(mod4) a_{k}=k-\left\lfloor\frac{k}{\ell}\right\rfloor \ell \equiv k-\left\lfloor\frac{k}{\ell}\right\rfloor(\bmod 4) \quad \text{ and } \quad b_{k}=k-\left\lfloor\frac{k}{r}\right\rfloor r \equiv k-\left\lfloor\frac{k}{r}\right\rfloor(\bmod 4)
we have k/kak(mod4)\lfloor k / \ell\rfloor \equiv k-a_{k}(\bmod 4) and k/rkbk(mod4)\lfloor k / r\rfloor \equiv k-b_{k}(\bmod 4). We therefore have
mk=ikak(i)kbk=(i2)kiak(i)bk=(i)akibk m_{k}=i^{k-a_{k}}(-i)^{k-b_{k}}=\left(-i^{2}\right)^{k} i^{-a_{k}}(-i)^{-b_{k}}=(-i)^{a_{k}} i^{b_{k}}
As \ell and rr are relatively prime, by Chinese Remainder Theorem, there is a bijection between pairs (ak,bk)=(k(mod),k(modr))\left(a_{k}, b_{k}\right)=(k(\bmod \ell), k(\bmod r)) and the numbers k=0,1,2,,r1k=0,1,2, \ldots, \ell r-1. Hence
k=0r1mk=k=0r1(i)akibk=(k=01(i)ak)(k=0r1ibk)=1×1=1 \sum_{k=0}^{\ell r-1} m_{k}=\sum_{k=0}^{\ell r-1}(-i)^{a_{k}} i^{b_{k}}=\left(\sum_{k=0}^{\ell-1}(-i)^{a_{k}}\right)\left(\sum_{k=0}^{r-1} i^{b_{k}}\right)=1 \times 1=1
as required because r1(mod4)\ell \equiv r \equiv 1(\bmod 4).

Case 4b: r3(mod4)\ell \equiv r \equiv 3(\bmod 4). In this case, we get
mk=iak(i)bk m_{k}=i^{a_{k}}(-i)^{b_{k}}
where ak(k(mod))a_{k}(\equiv k(\bmod \ell)) and bk(k(modr))b_{k}(\equiv k(\bmod r)) for k=0,1,,r1k=0,1, \ldots, \ell r-1. Then we can proceed analogously to Case 4a to obtain
k=0r1mk=k=0r1(i)akibk=(k=01(i)ak)(k=0r1ibk)=i×(i)=1 \sum_{k=0}^{\ell r-1} m_{k}=\sum_{k=0}^{\ell r-1}(-i)^{a_{k}} i^{b_{k}}=\left(\sum_{k=0}^{\ell-1}(-i)^{a_{k}}\right)\left(\sum_{k=0}^{r-1} i^{b_{k}}\right)=i \times(-i)=1
as required because r3(mod4)\ell \equiv r \equiv 3(\bmod 4).

Now clearly the car traverses through all points between (0,0)(0,0) and (1,0)(1,0) during the first section and, in fact, covers all points between (n1,0)(n-1,0) and (n,0)(n, 0) during the nn-th section. Hence it will eventually reach (d,0)(d, 0) for any positive dd.

To summarize: (,r)(\ell, r) satisfies the required conditions if and only if
r1 or r3(mod4) \ell \equiv r \equiv 1 \quad \text{ or } \quad \ell \equiv r \equiv 3 \quad(\bmod 4)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.