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?
All are invited to submit their solutions to
email@example.com; solutions to upstarts and
discussion will be posted at http://cs.nyu.edu/cs/faculty/
Dennis Shasha ( firstname.lastname@example.org) is a professor
of computer science in the Computer Science Department
of the Courant Institute at New York University, New
York, USA, as well as the chronicler of his good friend the
omniheurist Dr. Ecco.
Copyright held by author.
[CONTINUED FROM P. 104]
Publish Your Work
ACM o;ers a variety of
Open Access publishing options
to ensure that your work is
disseminated to the widest
possible readership of computer
scientists around the world.
Please visit ACM’s website
to learn more about
ACM’s innovative approach
to Open Access at: