A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's initial point coincides with the hunter's initial point . After rounds of the game, the rabbit is at point and the hunter is at point . In the -th round, three things occur in order:
(i) The rabbit moves invisibly to a point such that the distance between and is exactly .
(ii) A tracking device reports a point to the hunter. The only guarantee is that the distance between and is at most .
(iii) The hunter moves visibly to a point such that the distance between and is exactly .
Is it always possible for the hunter to choose a strategy such that after rounds, the distance between the hunter and the rabbit is guaranteed to be at most ?
No, the hunter cannot guarantee that the distance is at most 100 after rounds.
No, the hunter cannot guarantee that the distance is at most 101 after rounds.
No, the hunter cannot guarantee that the distance is at most 102 after rounds.
No, the hunter cannot guarantee that the distance is at most 99 after rounds.
Hint 1: Think about what the tracking device's error means: the hunter's information about the rabbit's position has an inherent uncertainty of radius 1 per round.
Hint 2: Consider a 1-dimensional version first: if the rabbit always moves right, and the tracker reports a point within distance 1, can the hunter keep up?
Hint 3: The key is that the errors accumulate like a random walk. After rounds, the uncertainty grows proportionally to , which for far exceeds 100.
Answer: No. The hunter cannot guarantee the distance is at most 100.
Key idea: The rabbit can use a strategy based on random-walk-like movements that cause the tracking device's information to be essentially useless. Even though the tracker reports a point within distance 1 of the rabbit, the uncertainty is enough for the rabbit to "drift" away.
Step 1 (Rabbit's strategy): The rabbit moves in a fixed direction (say, along a line). At each step, the rabbit moves distance 1 along this line. The tracker reports a point within distance 1 of the rabbit's position, but this point could be anywhere in a disk of radius 1.
Step 2 (Hunter's dilemma): The hunter must move distance exactly 1 per step. Even with the tracking information, the hunter's best guess of the rabbit's position has an error that can accumulate. The expected squared distance between the hunter and rabbit grows like (similar to a random walk), so after steps, the distance can be , far exceeding 100.
Step 3 (Rigorous bound): One can formalize this by showing the rabbit can maintain a strategy where the hunter's information gain per round is bounded, while the positional uncertainty grows. The adversary (rabbit) uses the 1-unit "noise" in the tracking to ensure the squared distance grows linearly, making it impossible to keep distance under 100 after rounds.
Ready to track your progress and master these topics?
Create a free account