[Math] Riddle: Minimum time to cross the bridge

puzzle

I've recently been asked to solve a riddle, which sounds something like that:

There are 4 people on the one side of the bridge. They have only 1 flashlight. It takes respectively 1, 2, 5 and 10 minutes for those people to cross the bridge. Rules for crossing the bridge:

  1. Bridge can hold up to 2 people at the same time.
  2. People can't cross the bridge without carrying a flashlight.
  3. If 2 people are crossing the bridge at the same time, their speed is equal to the slower one's speed.

Question: what is the minimum of time required for all four of them to cross the bridge?

It is clear that at the beginning two people cross the bridge, then one of them goes back, then another two crosses and so on…

The answer for the riddle is: (hover to see)

17 minutes:
1 min. and 2 min. crosses the bridge. (+2 minutes);
1 min. goes back. (+1 minute);
10 min. and 5 min. crosses the bridge. (+10 minutes);
2 min. goes back. (+2 minutes);
1 min. and 2 min. crosses the bridge. (+2 minutes).

But my question is: Is there any mathematical way to count the solution without just guessing?

Best Answer

There are only 6 choices for who goes first, two for who comes back, 3 for who goes next, 3 for who goes back, making $6\times2\times3\times3=108$ ways to get across the bridge; one could calculate them all, and take the best one; no guessing needed.

Perhaps a better way is to note that if 5 doesn't go with 10 then there has to be a trip that takes 10 and another trip that takes 5, so those two trips alone already take 15. So it's probably better if 5 and 10 go together.

If they go first, then 5 has to come back, and again we've used 15 (and 5 still has to go again, making at least 20). So it's probably best if they don't go first.

So we're left with 1 and 2 going first, one of them coming back, then 5 and 10 going together, the other of 1 and 2 coming back, then 1 and 2 going together again.

Related Question