IMO 2017 · Problem 3

A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit’s starting point, \(A_0\), and the hunter’s starting point, \(B_0\), are the same. After \(n-1\) rounds of the game, the rabbit is at point \(A_{n-1}\) and the hunter is at point \(B_{n-1}\). In the \(n^{\text{th}}\) round of the game, three things occur in order.

(i) The rabbit moves invisibly to a point \(A_n\) such that the distance between \(A_{n-1}\) and \(A_n\) is exactly 1.

(ii) A tracking device reports a point \(P_n\) to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between \(P_n\) and \(A_n\) is at most 1.

(iii) The hunter moves visibly to a point \(B_n\) such that the distance between \(B_{n-1}\) and \(B_n\) is exactly 1.

Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after \(10^9\) rounds she can ensure that the distance between her and the rabbit is at most 100?

Official text of the problem. Official problem paper (PDF)

Answer

No.

Solution

Fix any strategy for the hunter. We will construct legal rabbit moves and reports for which this strategy fails.

We will repeatedly use two possible rabbit paths that produce exactly the same reports. The hunter follows the same sequence of moves for both paths, so her response can be calculated from her fixed strategy before either path is followed. Consequently, we may select whichever path gives the desired outcome without violating the order of moves.

First, prescribe \(P_1=A_0\). Let \(B_1\) be the hunter’s response under her strategy, and choose \[ A_1=2A_0-B_1. \] Because \(A_0=B_0\) and \(B_0B_1=1\), both the rabbit’s first move and the tracking error have length \(1\), while \[ A_1B_1=2. \]

We now prove that whenever the distance \(d\) between the rabbit and hunter satisfies \[ 1\le d\le100, \] we can arrange the next \(200\) rounds so that their new distance \(d'\) satisfies \[ (d')^2>d^2+\frac12. \]

Choose coordinates with the hunter’s current position at \((0,0)\) and the rabbit’s current position at \((d,0)\). Put \[ L=\sqrt{200^2-1}. \] Consider the following two possible rabbit paths, indexed by \(\varepsilon\in\{-1,1\}\): \[ A_j^\varepsilon =\left(d+\frac{jL}{200},\,\frac{\varepsilon j}{200}\right), \qquad j=0,1,\ldots,200. \] Every rabbit move has length \[ \sqrt{\left(\frac L{200}\right)^2+\left(\frac1{200}\right)^2}=1. \] For round \(j\), prescribe the report \[ P_j=\left(d+\frac{jL}{200},\,0\right). \] These reports are valid for either path, because \[ |P_j-A_j^\varepsilon|=\frac j{200}\le1. \]

Let the hunter’s position after these \(200\) rounds be \((x,y)\). It is the same for both rabbit paths. Since she has made \(200\) moves of length \(1\), her displacement has length at most \(200\), and hence \(x\le200\).

Choose the rabbit path whose final vertical coordinate, either \(1\) or \(-1\), is farther from \(y\). The vertical separation is then \(1+|y|\ge1\). Define \[ \delta=200-L=\frac1{200+L}. \] We have \(0<\delta<1\). Thus the horizontal separation satisfies \[ d+L-x\ge d+L-200=d-\delta>0. \] It follows that \[ (d')^2\ge(d-\delta)^2+1. \] The identity \(L^2=200^2-1\) gives \[ 1+\delta^2=400\delta. \] Therefore, using \(d\le100\), \[ \begin{aligned} (d')^2-d^2 &\ge1-2d\delta+\delta^2\\ &=(400-2d)\delta\\ &\ge200\delta\\ &=\frac{200}{200+L} >\frac12. \end{aligned} \] This proves the claimed construction.

Starting from distance \(2\) after the first round, apply this construction in successive blocks of \(200\) rounds until a block ends with distance greater than \(100\). Such a block must occur among the first \(20\,000\) blocks: otherwise, the squared distance after those blocks would exceed \[ 2^2+20\,000\cdot\frac12=10\,004>100^2, \] a contradiction. Thus the distance exceeds \(100\) after at most \[ 1+20\,000\cdot200=4\,000\,001<10^9 \] rounds.

For every remaining round, the rabbit moves one unit directly away from the hunter’s current position, and the device reports the rabbit’s actual new position. If the distance before such a round is \(r>100\), the rabbit’s new position is at distance \(r+1\) from the hunter’s old position. By the triangle inequality, after the hunter’s unit move their distance is at least \[ (r+1)-1=r. \] Hence the distance remains greater than \(100\) through round \(10^9\).

Since this construction defeats every fixed hunter strategy, the hunter cannot ensure the required distance.

The solution was checked against the official IMO shortlist solutions.