[seqfan] Fwd: puzzle : crossing a bridge

Maximilian Hasler maximilian.hasler at gmail.com
Mon Nov 10 02:45:44 CET 2008


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.




More information about the SeqFan mailing list