From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Subject: Re: combinatorial problem.
Date: 6 Jun 2000 16:41:55 GMT
Newsgroups: sci.math
Summary: Comparing ways to cross a bridge

In article <393D143A.AA6F3C8F@KUB.NL>, S108502  <E.C.vEersel@KUB.NL> wrote:

>"U2" have a concert that starts in 17 minutes and they must all cross a
>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
>flash light. A maximum of two people can cross at one time. Any party
>who crosses, either 1 or 2 people, must have the flash light 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:
>
>Bono - 1 minute to cross
>Edge - 2 minute to cross
>Adam - 5 minute to cross
>Larry - 10 minute to cross

>Is there really no trick to it???

No trick is necessary (but given Microsoft's business practices perhaps
trickery would win you the job...), that is, there are solutions of
this type: 2 of the 4 cross one way, one of those two returns; 2 of
the 3 cross the first way, one of the three returns; the remaining two
cross the first way. As you can see there are only 6*2*3*3 possible
solutions to investigate of this type.

If you can't think your way through the options, you could run to a
computer. Here's some lame Maple code to check all the options:

lef:=proc(S) global A,B,t: A:=sort([op({op(A)} minus S)]):
	     B:=sort([op({op(B)} union S)]):t:=t+max(op(S)):end:
rig:=proc(S) global A,B,t: A:=sort([op({op(A)} union S)]):
	     B:=sort([op({op(B)} minus S)]):t:=t+max(op(S)):end:

for i to 3 do for j from i+1 to 4 do 
for k from 1 to 2 do 
for l from 1 to 3 do 
for m from 1 to 3 do 
A:=[1,2,5,10]:B:=[]:t:=0:
lef({A[i],A[j]}):rig({B[k]}):lef({op(A)} minus {A[l]}):rig({B[m]}):lef({op(A)}):
if t<20 then print(i,j,k,l,m,t):fi:
od:od:od:od:od: