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

[franktaw at netscape.net]

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

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

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 
to
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 
fastest
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) =
1,2,7,15,28,52,97,185,358,...
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 
powers.

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
needed).

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.
Maximilian
PS: Obviously one could pre-pend T(0)=0 to the sequence.