0
$\begingroup$

My friend told me a riddle yesterday: four people want to cross a bridge. They each will take $1$, $2$, $5$, and $10$ minutes respectively to cross the bridge. They can go across the bridge in groups of $2$, which will move as fast as the slowest person. However, they must also travel with a flashlight to not get eaten by the bridge troll. The group only has one flashlight, so after each crossing, someone must return across the bridge with the flashlight.

Question: What's the minimum time to cross the bridge?

Naively, you would send $1$ as the "chaperogne", in which case it takes $19$ minutes. However, there's a better solution. Send $1$ and $2$ together, send $1$ back, $5$ and $10$ together, $2$ back, $1$ and $2$ together, for a total of $17$ minutes.

There have been questions about this riddle on here before - my question is, can this be generalized? Formally, given a finite sequence of positive naturals $a_n$ corresponding to the "bridge-crossing times", is there a way to determine the optimal plan for getting across the bridge?

I suspect this is related to graph theory, which is definitely not my area.

$\endgroup$
  • $\begingroup$ See this paper. It turns out that the optimal plan for getting across is somewhat subtle. Also, this is discussed over at the code golf network. $\endgroup$ – Peter Kagey Apr 9 at 17:18
0
$\begingroup$

If you can prove (and I think it's true) that it never makes sense to send back two people, then the number of people remaining to make the trip (after an out-and-back-pair) decreases over time.

Once you know that, the problem becomes amenable to a dynamic programming (or memoization) approach, much like the knapsack problem and others like it. My rough intuition (from having taught the memoization approach to knapsack a few times over the years) is that this approach is likely to be slow and require lots of memory if many of the "times" are similar, and faster and less memory-hungry if the times differ by a lot (e.g., factors of 2).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.