Communications of the ACM
Last byte
Feedback for Foxes
Credit: Getty Images
The early history of differential games gave us the parable of the homicidal chauffeur. The chauffeur, it seems, wants to use his car to collide with a person running on an infinite plane. The car is faster but less maneuverable than the runner. The general question is: What is a good strategy for each?
In this Upstart Puzzle, I will simplify and discretize the problem in order to discuss the interrelated questions of feedback, impossibility, and time complexity. To begin, consider the scenario of the figure in this column. There is a scared rabbit inside a straight corridor C that is glass-lined so the position of the rabbit is known to any observer. A fox starts outside the corridor at a point such that the line segment of length D from the fox to the rabbit is perpendicular to C (hereafter, the perpendicularity condition). The fox's goal is to be able to catch the rabbit, which it can do from at most one unit away.
Figure. Suppose a rabbit can move one unit per second inside a corridor and a fox two units per second whether inside or outside. Further suppose the fox can change direction once outside the corridor and can take either direction once inside the corridor. When and how should the fox change direction outside the corridor to minimize the time needed until the fox is at most one unit away from the rabbit inside the corridor?
To start, assume the fox is initially 100 units away and moves twice as fast (two distance units per second) as the rabbit.
Warm-Up: How long would it take the fox to catch the rabbit if the fox goes straight to the corridor and then turns in the direction of the rabbit? Assume the rabbit does everything it can to get away.
Solution to Warm-Up: The fox will reach the corridor in 50 seconds at two units per second, the rabbit will be at most 50 units away. In the worst case, the fox will catch the rabbit in another 50 seconds. This gives a total of 100 seconds.
Question: Suppose the fox is allowed to change direction just once while outside the corridor. Can the fox catch the rabbit in 80 seconds or less?
Solution: Yes. The fox can turn after 30 seconds to point in the direction of the rabbit at that time. The rabbit will have left its original resting place and traveled at most 30 units away. At that time the fox will be only 40 units away from the corridor. The diagonal between the fox and the rabbit is therefore at most of length 50, so in another 25 seconds, the fox will be at the corridor. At that point the rabbit may be 25 units away. The fox will then capture the rabbit in another 25 seconds. This gives a total time of 80 seconds.
Question: Suppose the fox starts 100 units away from the rabbit but could change direction at any time. How slowly could the fox move but still catch the rabbit in 100 time units?
Solution: The fox could move as slowly as sqrt(2) distance units per time unit. The approach is as follows: The fox continually maintains itself at a point that satisfies the perpendicularity condition. If the rabbit moves one unit in a time period, this will require the fox to move sqrt(2) units to be one unit closer to the corridor and still be perpendicular. So in 100 units it will be right on top of the rabbit in the corridor.
Question: Suppose the rabbit can go anywhere on an infinite floor and the fox is initially also on the floor but 100 units away. The fox can turn seven times and goes twice as fast as the rabbit. Can the fox guarantee to catch the rabbit in 100 seconds? Is it possible to do better?
Solution: Here is a simple method. The fox goes directly toward where the rabbit is. After 50 seconds, the fox arrives. The rabbit may have gone 50 meters away. The fox goes to that point and arrives in 25 seconds. The rabbit may have gone 25 meters away. So, at each turning point the time and distance goes down by half: 100, 50, 25, 12.5, 6.25, 3.125, 1.5625, 0.7812, which is less than 1. We need at most seven turns. Note that the time cannot be shorter because the rabbit could just go directly away from the fox in which case the fox still needs 100 seconds to catch the rabbit.
"Fun" question (suggested by my colleague Ernie Davis): Suppose the fox is distance d away, can move at speed d (d > 1) units per second (while the rabbit still can move only one unit per second), but can never turn. Suppose the fox is aimed at the initial position of the rabbit but cannot turn. At which angle should the rabbit move to always be at least one unit away from the fox?
Now for the Upstarts.
Upstart 1: Suppose the fox is at an initial distance d from the corridor, satisfies the perpendicularity condition, travels at a speed of s, and can make k direction changes while outside the corridor. What is the optimal strategy for the fox to minimize the worst-case time to catch the rabbit?
Upstart 2: The rabbit is a sea serpent and the fox is a diver. So this generalizes Upstart 1 so that both the rabbit and the fox are moving in three dimensions with the rabbit moving at speed l and the fox at speed s. What is the minimum value of k (direction changes) for which this is always possible?
Upstart 3: In the three-dimensional scenario of Upstart 2, is there a general expression for the trade-off between the number k of direction changes and time complexity, once k exceeds the minimum number of direction changes necessary?
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.
No entries found