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:
$\text{1) }$ The rabbit moves invisibly to a point $A_n$ such that the distance between $A_{n-1}$ and $A_n$ is exactly $1.$
$\text{2) }$ 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.$
$\text{3) }$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?$
Best Answer
My attempt is sketched as follows.
We need to verify if the hunter can find a strategy allowing her to remain within 100 units after 109 iteration, whatever the rabbit and the tracking device do.
It makes then sense to consider the best possible strategy for the hunter, chasing a rabbit doing the same, while the tracking device “helps” the rabbit as much as possible. Let then denote as $d_{i}$ the distance between the rabbit and the hunter at the $i$th iteration.
The rabbit will try to maximise the distance from the hunter, by taking one step along the line going through him and the hunter.
Next, the device will do the worst it can for the hunter: it will select the point within a circle of radius 1 centered at the rabbit that will minimise the distance gain as the hunter steps (in the sketch below, the hunter is marked by the red spot, the rabbit by the blue, and the "eworst" tracking device signal by the green spot)
Such point is placed around the circumference, and it is such that the segment connecting it to the hunter is tangent to the circumference.
If the best strategy for the hunter is to move towards the signal given by the tracking device, moving along this segment has the least projection along the hunter-rabbit line. The angle $\alpha$ between the hunter-worst tracking device signal and hunter-rabbit line is given by $\alpha = sin^{-1} \frac{1}{d_{i} + 1} $ These consideration yield the following recursive formula $$ d_{i+1} = d_{i} + 1 - \sqrt{1- (\frac{1}{d_{i}+1})^2}$$ The sequence is monotonically decreasing and concave. We fix $d_i = 100$, and verify that $d_{i+1} – d_{i} \approx 10^-5$.
My claim is hence that the hunter will not achieve the required target after $10^9 $ (I do not even know if the claim is correct, let alone the process, but worth a go).
EDIT The point was left open whether following the tracking device signal is the optimal strategy for the hunter. As @seoneo pointed out, previous information might provide additional information to the hunter. The problem can be circumvented by showing that there exist a, albeit suboptimal, strategy for the rabbit, in control of the tracking device (this can be assumed following the problem formulation), sufficient to increase the distance fast enough. The rabbit can choose to move about one of the dotted lines in red, and further decide to have a signal sent on the middle blue line. This is possible until the distance between the rabbit and the blue line is $<1$. As long as this condition holds, the hunter has no better strategy than to continue along the blue line. Once the distance between the rabbit and the blue line is $<1$, even if the hunter came to knowing the rabbit position, a new iteration could be performed, following the same strategy: the hunter goes towards the rabbit along the “updated” blue line, and the latter chooses one of the “updated” red lines. The trigonometry I presented is unaffected.