38 analysis/minimum.time.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
38 analysis/minimum.time.p
N people can walk or drive in a two-seater to go from city A to city B. What
is the minimum time required to do so?
analysis/minimum.time.s
Let the speed of the car be v, the speed of a walking person be u, and
the distance between cities by L. We want to minimize T, the time t
at which all persons are at displacement x=L (city B), when they all
start at displacement x=0 (city A) at time t=0.
I'll assume that the solution has everyone starting out from city A at
the same time t=0 arriving in city B at the same time t=T so nobody is
standing around idly waiting. Let's plot everyone's movements on a
graph showing coordinates (t,x). Then at time t just after 0, (N-2)
walkers are on the line L0 through (0,0) with slope dx/dt = u, and 2
in the car are on a line through (0,0) with slope v, and at t just
before T, (N-2) walkers are on the line L1 through (T,L) with slope u,
and 2 in the car are on a line through (T,L) with slope v. Obviously
L1 lies "above" L0 (greater x coordinate given the same t coordinate).
In between t=0 and t=T, the car zigzags between L0 and L1 along lines
of slope v and -v, picking up people from L0 and dropping them off at
L1. I will not prove that this is the optimal strategy; in fact you
can make an infinite number of variations on it which all come up with
the same elapsed time.
Now examine the graph again. Say the car travels distance r between
picking someone up and dropping that person off, and distance s back
to pick up the next person. The car makes (N-1) trips forward and
(N-2) trips back to pick up and ferry everyone, so its total travel is
vT = (N - 1)r + (N - 2)s = (N - 2)(r + s) + r
Moreover the car makes (r-s) net displacement on each round trip, plus
r displacement on the extra forward trip, so
L = (N - 2)(r - s) + r
Note that a person walks distance (r-s) in the time it takes the car to
go (r+s), so
r - s = (u/v)(r + s)
A little algebraic manipulation of this equation shows us that
r - s = r * 2u/(v + u) r + s = r * 2v/(v + u)
Plug this into the equation for L, and we get the first important
piece of information, how far the car should drive before dropping off
the passenger (once you know this, you tell it to the driver and this
guarantees the people get to B in minimum time):
L = r + (N - 2) r * 2u/(v + u) = r * (v + u + (N - 2)*2u)/(v + u) v + u r = ------------ L 2uN + v - 3u
We can also find out what the elapsed time T will be:
vT = (N - 2)r*2v/(v + u) + r = r * ((N - 2)*2v + v + u)/(v + u) 1 2vN - 3v + u T = - * ------------ r v v + u
Therefore
2vN - (3v - u) T = -------------- (L/v) 2uN + v - 3u
-- David Karr (karr@cs.cornell.edu)
Continue to:
My Books
