Bridge Crossing

Logic Level 2

Four people need to cross a dark bridge, but at most two people can cross at once. They have only one light to guide them across, so they must walk at the pace of the slower person.

If the times in which they can each cross the bridge are 1, 2, 7, and 10 minutes, what is the shortest time (in minutes) needed for all four to get across the bridge?


The answer is 17.

Pratyush Pushkar by Pratyush Pushkar , 28, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Pratyush Pushkar
May 17, 2015

The fastest time is 17 minutes.

The initial solution most people will think of is to use the fastest person as an usher to guide everyone across. How long would that take? 10 + 1 + 7 + 1 + 2 = 21 minutes. But we can do better.

1 and 2 go cross

2 comes back

7 and 10 go across

1 comes back

1 and 2 go across (done)

Total time = 2 + 2 + 10 + 1 + 2 = 17 minutes.

25 Helpful 1 Interesting 2 Brilliant 1 Confused

Nice. An important step you've missed however is to prove that there is no shorter time than 17 17 min.

Siddhartha Srivastava - 6 years ago

Log in to reply

That's a good point! Does anyone see how to show that this is the minimum possible time?

Hint: This plan uses 5 bridge crossings (3 across, 2 back). One approach is to show that the answer to all three of these questions is "no":

  • Is it possible to use fewer bridge crossings?
  • If we use 5 bridge crossings, is it possible to do better than 17 minutes?
  • If we use 7 or more bridge crossings, is it possible to do better than 17 minutes?

Eli Ross Staff - 5 years, 7 months ago

Log in to reply

For the journey to be completed in less than 17 minutes, (a) the two slowest walkers must travel together (if they travel separately this takes 10 + 7 = 17 minutes), and (b) after travelling together neither of the two slowest travellers can travel back across the bridge (this would also take 10 + 7 = 17 minutes). Because of (a) and (b) the two fastest walkers would have to travel across the bridge to begin with, and 1 of them would have to take the torch back across the bridge. Then because of (a) the two slowest walkers would need to travel across the bridge, and because of (b) the remaining fast walker would need to take the torch back across the bridge. Then the two fastest walkers must travel back across the bridge to complete the task. This process takes 17 minutes, and the task cannot be completed in any other way without violating either (a) or (b).

Tim Hefferon - 5 years, 7 months ago

Log in to reply

@Tim Hefferon – Awesome explanation!

Eli Ross Staff - 5 years, 7 months ago

well you can try that and let us know

Pratyush Pushkar - 5 years, 5 months ago

What if 10 & 7 go first and then 1 & 2 go across? is it compulsory to one of them get back or can I send them in pair...??

Shams Xix - 5 years, 4 months ago

Log in to reply

"They have only one light to guide them across."

Someone has to bring the light back across, or else they can't see!

Eli Ross Staff - 5 years, 4 months ago

Hah I missed the part where there is only 1 light as in real life I can't possibly image this situation. Who needs a freaking light to cross a bridge anyways? Honestly 10 and 7 should go together just after 1 and 2 making the whole thing take 10 minutes! 1 and 2 can be slow enough to use the light of the 2 slowest and get there just before them! My answer is 10 minutes and I'm not budging!

Chris White - 5 years, 7 months ago

Log in to reply

  1. Go ahead and cross a bridge without a light and when it's awfully dark. Tell me if you succeed without falling from the sides.
  2. Go ahead and cross a bridge with four people at once while the bridge clearly says a limit of two people. Tell me if you succeed without falling from the bridge breaking.

Ivan Koswara - 5 years, 4 months ago

Its a logic problem, not a real life problem. Think of a two man boat rowing across a river with people able to row at different speeds. Does that make it better for you?

Mark Brown - 2 years, 11 months ago

10 & 7 cross, 1 goes to get the light and comes back. 2 &1 cross. 14 minutes

Stephen Morente - 5 years, 7 months ago

Log in to reply

How can 1 goes get the light without the light?

H. Phước Dương - 5 years, 7 months ago

if they can cross without the light 7&10 cross then 2&1 cross without the light . 12 min.

Greg White - 5 years, 7 months ago
Hasmik Garyaka
Oct 25, 2018

Let it be that people with 1 and 2 min are on the left side, and with 7 and 10 of the right side. Then they all will cross the river in 13 min.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

In that case, it will only take 12 minutes if one pair crosses and then the other

Pun It - 2 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...