Four people need to get across a bridge that can only support two at a time.

Additional material

[ Editor: the puzzle as posted in 1996 by chintalapati sekhar
<schinta@eng.clemson.edu> used a lantern, crossing times of 1, 2, 5 and
10 minutes, and asked whether all four can cross in less than 18
minutes.  The timed schedule: ]

1 and 2 cross:   2 min.
1 returns:       3 min.
10 and 5 cross: 13 min.
2 returns:      15 min.
1 and 2 cross:  17 min.

The other variation has 1 and 2 returning in opposite order,
which, obviously, takes the same amount of time.

-- Ken Kelley <kkelley@athena.mit.edu>

The general case: n people crossing a bridge.

There are a group of n people who want to cross a fragile bridge at
night.  The bridge can only support two people at once.  The group only
has only one flashlight, which is needed in order to cross the bridge
safely.  The flashlight cannot be thrown back across the bridge.  The n
people take different times to cross the bridge.  The time taken for two
people to cross the bridge together is the time it takes for the slowest
of them to cross.  What is the minimum time for all n people to cross
the bridge?

-- Brendan Owen <bdowen@ee.mu.oz.au>

To decide who should make the first trip, you only need to know the
speeds of the fastest two and the slowest two.  Label them F1, F2, S2,
S1.  The first two trips should either be:

CASE1:  F1 and F2 then S2 and S1.
CASE2:  F1 and S1 then F1 and S2.

In other words, do you save more time by having the two slowest make
the trip together than you waste by having the second fastest make
one of the return trips.  This translates to use CASE1 if
2*F2 <= F1 + S2 and CASE2 if 2*F2 > F1 + S2.

If you did CASE1 and there are four or more people left to cross,
simply repeat the process.  If you did CASE2 or there are less than
four people left, the fastest should accompany everyone left.

Solving the general case simply involves repeatedly solving the
n=4 case.  For n = 4, there are two formulas for the minimum time:

2*F1 + F2 + S2 + S1 if 2*F2 > F1 + S2
F1 + 3*F2 + S1 if 2*F2 <= F1 + S2

In the general case, there are Int(n/2) formulas to express the
possible minimum times.  The problem quickly becomes tedious
without offering any actual content beyond the n=4 stage.

-- Kevin Green <kdg977@dialnet.net>

See Kev's post in a previous thread for a great explanation.
Here is the answer though

Let  ai  be the time of the  ith  fastest person

0 < a1 <= a2 <= ......... <= an

Recursive

T1=a1
T2=a2
T3=a1+a2+a3
Tn=Min(T(n-2) + a1 + 2*a2 + an, (n-3)*a1 + Sum[1 <= i <= n](ai))

Final

T1=a1
Tn=(n-2)*a1-2a2+Sum[1<=i<=n](ai)
       +Min[1 <= i <= floor(n/2)](i*(2*a2 - a1)-Sum[1 <= j < i](a(n+1-2*j)))

-- Brendan Owen <bdowen@ee.mu.oz.au>

A variant with different times was posted in 1996:

    4 Adventurers (Peter, Robert, Andrew and Sam) are on a trip through
    the Amazon forest.  Strolling along in the forest they forget the
    time.  As it gets dark, they arrive at a bridge over a steep canyon.
    ... They decide to go across the bridge.  But by examining the
    bridge, they find out that the bridge can only carry two persons at
    a time and they have only one torch.  The torch is a modern torch
    which shows how long the batteries last.  The display says 60
    minutes.  Now comes the tricky part.  Peter can run the bridge in 5
    minutes, Robert in 10, Andrew needs 20 minutes and Sam is the slowest
    with 25 minutes.

    How can all of them get to the other side in 60 minutes?  The bridge
    is too long so they can't throw the torch back, once one of them is
    over the bridge.  So two of them have to go over, one has to run back
    to get the next one.

    -- Mick Galvin <mgalvin@iol.ie>

Not even higher mathematics - just seeing a non-obvious approach.

Peter and Robert cross     10 minutes
Peter returns               5 minutes
Andrew and Sam cross       25 minutes
Robert returns             10 minutes
Peter and Robert cross     10 minutes
                           --
Total                      60 minutes

(A similar puzzle has been posted here a couple times in the past couple
months, replacing 5/10/20/25/60 with 1/2/5/10/17.)

-- Ed Murphy <ford@bayside.net>

Shalosh B. Ekhad and Doron Zeilberger, "The Generalized U2-Flashlight
Microsoft 5-Minute Puzzle", Department of Mathematics, Temple
University, Philadelphia, Sept. 29, 1998 (a one-page paper,
accompanied by a Maple package GetMicrosoftJob from the second
author's website).

   Abstract: The celebrated U2-flashlight puzzle, allegedly posed by
   Microsoft to job applicants, who were required to solve it in 5
   minutes, is generalized from four people to an arbitrary number of
   people, with general crossing times, and then completely solved
   (in linear time).

   Theorem: If n people have to cross a (at most) two-person bridge,
   and they are equipped with one flashlight, and their times of
   crossing are a_1 < ... < a_n, and when two people go together, they
   walk at the slower's pace, then the shortest possible total time
   for everyone to cross the bridge, let's call it A_n(a_1, ..., a_n),
   equals

      B_n(a_1, ..., a_n) :=
         min over 0 <= r <= [n/2] - 1 of
         [ (n-2-r)a_1 + (2r+1)a_2 + sum(i=3..n-2r) a_i
                                  + sum(i=0..r-1) a_(n-2i) ].

-- Shalosh B. Ekhad and Doron Zeilberger

[ Editor: summary.  The proof is by the recurrence A_n = min(a_1 + a_n
+ A_(n-1)(a_1, ..., a_(n-1)), a_1 + 2a_2 + a_n + A_(n-2)(a_1, ...,
a_(n-2))) for n > 3, with A_2 = a_2 and A_3 = a_1 + a_2 + a_3, which
B_n also satisfies: the slowest person crosses once, either with a_1,
who comes back, or with a_(n-1), after a_1 and a_2 have gone over as
scouts.  If r gives the minimum, the 2r slowest cross in pairs
{a_n, a_(n-1)}, {a_(n-2), a_(n-3)}, ... with a_1 and a_2 as scouts,
and then a_1 escorts the remaining n-2r-1 people one at a time.  For
the U2 puzzle, A_4(1, 2, 5, 10) = min(19, 17) = 17, with r = 1. ]

[ Editor: the paper was in the TODO collection as
bridge_crossing.pdf. ]