last byte
I
M
A
G
E
B
Y
A
N
D
R
I
J
B
O
R
Y
S
A
S
S
O
C
I
A
T
E
S
,
U
S
I
N
G
A
N
I
M
A
L
A
R
T
B
Y
M
A
R
Y
S
A
N
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?
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
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.
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
Upstart Puzzles
Feedback for Foxes
Searching for the best strategy for shifty maneuvers.
DOI: 10.1145/3372389 Dennis Shasha
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?
[CONTINUED ON P. 103]
