0

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?

Gintas K
  • 765

1 Answers1

5

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.

Gerry Myerson
  • 179,216
  • But you're guessing! There are two probably's in there. – TonyK Apr 16 '15 at 09:55
  • 1
    Not really. Once you've seen that you can do it in 17, you can rule out 5 and 10 going together first. And if 5 doesn't go with 10, then their trips take 15, and three more trips are needed, that will take at least 3, hence, 18. The "probablys" tell you what to expect, but you can ignore them and calculate the three cases to see that the third case gives 17 while the others must give more. – Gerry Myerson Apr 16 '15 at 10:52
  • I'm curious as to why it doesn't seem to matter whether 1 or 2 comes back first? – Robin Andrews May 23 '23 at 12:20
  • 1
    @Robin, they both have to come back eventually, and then cross again, so it doesn't matter which one comes back first. – Gerry Myerson May 23 '23 at 13:26