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:

$\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?$

1 Answers1

1

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)

enter image description here

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. enter image description here

An aedonist
  • 2,568
  • Not even a comment...I would be glad to edit if unclear... – An aedonist Jul 22 '17 at 20:19
  • Define the state of ray BP is on the counterclockwise of the ray BA to be left. Similarly define the right state. In this solution, it is assumed without proof that the L, R states are symmetric so that hunter does not detect difference between them. However, consecutive operation of rabbit will reveal the position because there are different feasible position of the detector depending on the previous state of the rabbit. – seoneo Jul 24 '17 at 09:02
  • @seoneo, I am not sure I understand how your comment applies to my solution. I simply build a bound using the uncertainty at each step, what happens among steps $n$ and $n+k$ for $k>1$ is irrelevant, I think.. – An aedonist Jul 24 '17 at 09:24
  • @Anaedonist I mean, moving toward the 'signal' may not best strategy for the Hunter. – seoneo Jul 24 '17 at 09:29
  • @seoneo, that is a good point of course (which is why I put an "if" in bold in my reply). Anyhow, I believe it is not insurmountable: one can easily find a rabbit and tracking device behaviour, that although suboptimal, suffices to escape. The rabbit moves in a straight line for $s$ steps (red-blue line on my diagram), and the tracking devices gives points on the red-green line. As long as the blue-green distance is less than one, the hunter has no better option than going straight, following the signal, as previous rabbit operation has not yet revealed anything. – An aedonist Jul 24 '17 at 10:59
  • After $s$ steps, whatever the hunter knows about the rabbit, the same argument could apply again. With this extension, my solution should hold, or not? – An aedonist Jul 24 '17 at 10:59
  • @Anaedonist Thanks for your response. Recently, I have not enough time to spent time on the web. However, I'll will check difference of your before and after posts sooner or later. By the say, have you check the posts in AOPS whose links appeared above? Especially, v_Enhence's argument is very clear which looks similar with yours. I do not mean your's is not clear. – seoneo Jul 25 '17 at 06:08
  • @seoneo, no I did not check the link yet, wanted to find a solution alone. I might well do shortly. – An aedonist Jul 25 '17 at 08:24