This article is from the Puzzles FAQ, by Chris Cole firstname.lastname@example.org and Matthew Daly email@example.com with numerous contributions by others.
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?
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)
L = r + (N - 2) r * 2u/(v + u) = r * (v + u + (N - 2)*2u)/(v + u) v + u r = ------------ L 2uN + v - 3u
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
2vN - (3v - u) T = -------------- (L/v) 2uN + v - 3u