[seqfan] Re: Fwd: puzzle : crossing a bridge

franktaw at netscape.net franktaw at netscape.net
Mon Nov 10 04:43:54 CET 2008

It seems like the following recursive strategy is optimal, in almost 
general case:

With 1 or 2 people, they just cross.
With 3 people, the fastest person escorts the other two across (in 
With n > 3 people, the 2 fastest cross.  One (either of them) returns, 
the 2 slowest cross.  The other fast person returns, reducing to the 

So if the time for the nth fastest person is b(n) -- fastest first -- 
the cost
for 1 is b(1), for 2 it's b(2), for 3 it's b(1) + b(2) + b(3), and for 
n > 3,
it's b(1) + 2b(2) + b(n) + T(n-2).

I think this is optimal as long as b(3) - b(2) >= b(2) - b(1); we have 
have at least one crossing for every other speed from the high end, and
this seems to minimize the overhead cost of doing so.

(For any k > 2 with b(k) - b(2) < b(2) - b(1), you just have the 
person escort that person across and come back, and apply the above
strategy for any remaining people.)

If this strategy is optimal, we would get T(n) =
which, after the 1,2,7 start, is T(n) = T(n-2) + 2^n + 5.

Franklin T. Adams-Watters

-----Original Message-----
From: Maximilian Hasler <maximilian.hasler at gmail.com>

Dear SeqFans,

I just ran across http://www.nsta.org/quantum/bridgarc.asp,
which inspired me the following generalization:

Assume there is a group of n persons who want to cross a narrow bridge
which can only be crossed by a maximum of 2 persons at the same time.
In addition, those who cross the bridge need to have with them the
only lantern which the group possesses, and their speed is that of the
slower person.
What is the minimum time T(n) for the group to cross, if person #n
needs 2^(n-1) minutes to cross.

I get T(n) = 1,2,7,15,28,... (but I may have missed better solutions).

So far this matches A000148: Number of partitions into non-integral 

but for the next I don't get 45 (which is, I think, impossible since
in addition to 2 + 32 + 1 + 8 = 43, more than another 2 minutes are

Then a further generalization would be to replace 2^n by any other
(say, positive) sequence. This could be called the BRIDGE
transformation of that sequence. (Actually, instead of "bridge" I'd
prefer "tunnel" (dark & narrow in a natural way), but well, let's pay
that tribute to the tradition.)

Thanks for your comments.
PS: Obviously one could pre-pend T(0)=0 to the sequence.

More information about the SeqFan mailing list