%U2.tex: ``The Generalized U2-Flashlight Microsoft 5-Minute Puzzle''
%a Plain TeX file by Shalosh B. Ekhad and Doron Zeilberger
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in
%end macros
 
\centerline
{\bf The Generalized U2-Flashlight Microsoft 5-Minute Puzzle}
\bigskip
\centerline{ {\it 
Shalosh B. EKHAD{$\,^1$} and Doron ZEILBERGER
}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA. 
%\break
{\eighttt [ekhad, zeilberg]@math.temple.edu} 
{\eighttt http://www.math.temple.edu/\Tilde [ekhad,zeilberg]/ },
Sept. 29, 1998. Supported in part by the NSF.
This article is accompanied by a Maple package
{\eighttt GetMicrosoftJob} available from the second author's
website.
We thank Dr. Jane Legrange for bringing the Microsoft
puzzle to our attention. This puzzle, discussed in
the forum {\eighttt alt.brain.teasers} goes as follows:
  U2 has a concert that starts in 17
  minutes and they must all cross a
  rope bridge to get there.  All four
  men begin on the same side of the
  bridge.  You must help them across to
  the other side.  It is night.
  There is one flashlight.  A maximum
  of two people can cross at one
  time.  Any party who crosses, either 1
  or 2 people, must have the
  flashlight with them.  The flashlight
  must be walked back and forth, it
  cannot be thrown, etc.
  Each band member walks at a
  different speed.  A pair must walk
  together at the rate of the slower
  man's pace. The rates are:
  Bono -  1 minute to cross,
  Edge -  2 minutes to cross,
  Adam-  5 minutes to cross,
  Larry- 10 minutes to cross.
} 
}
 
{\bf 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).
 
{\bf 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< \dots < 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, \dots, a_n)$, equals
$$
B_n(a_1, \dots, a_n):={{\min} \atop {0 \leq r \leq [n/2] -1}}
\left [\, \,
(n-2-r)a_1+(2r+1)a_2+ \sum_{i=3}^{n-2r} a_i+\sum_{i=0}^{r-1} a_{n-2i}
\,\,\right ] \,\,.
$$
{\bf Proof}: Obviously $a_n$ should only cross once.
If his companion is to return, he should be the fastest,
$a_1$, whereas, if he is to never return, you can't
go wrong by making him $a_{n-1}$. But in the latter
case, two scouts should be sent first, one of whom will
come back with the flashlight, and the other one
to bring it latter back. You can't go wrong by
making these scouts $a_1$ and $a_2$, hence
we have the obvious recurrence, when $n>3$:
$$
A_n(a_1, \dots , a_n)=
\min \left (\,\, a_1+a_n+A_{n-1}(a_1, \dots, a_{n-1}) \,\,,\,\,
a_1+2a_2+a_n+A_{n-2}(a_1, \dots, a_{n-2})\,\, \right ) \quad,
$$
subject to the obvious initial conditions
$A_2(a_1,a_2)=a_2$, $A_3(a_1,a_2,a_3)=a_1+a_2+a_3$. 
But it is purely routine to see that
the same recurrence, and initial conditions, are satisfied 
with $A$ replaced by $B$. \halmos
 
If the winner in the above minimum was $r$, then
one possible way the crossing could be
done is with the $2r$ slowest people crossing
first in pairs, $\{a_n,a_{n-1}\}$,  $\{a_{n-2},a_{n-3}\}, \dots $ 
with the two fastest ($a_1$ and $a_2$) serving
as scouts, followed by $a_1$ leading in turn, the
remaining $n-2r-1$ people, returning each time
to fetch another guy. In particular, 
$A_4(1,2,5,10)=\min (19,17)=17$, with $r=1$.
 
\bye
 
 
 
 
 
 
 
 
 
 
 
 
 
 
