A good friend of mine send me this quiz which was found in compendium at her university. The course was about Mathematical Programming. I have copied the quiz directly.
Warning, this assignment is rather hard. It should have been used in a Microsoft during hiring interviews.
Four persons have to cross a bridge. The times each needs to cross it are:
- 5 min
- 10 min
- 20 min
- 25 min.
It is dark and they only have one lamp, we have the following constraints:
- the bridge can only be crossed if one has a lamp, while it is too dark.
- 2 persons at most are allowed to be on the bridge at the same time.
- the speed of a pair is determined by the speed of the slower person.
- the lamp can last only an hour.
- the lamp cannot be thrown.
Can you figure out a way so that the four men can cross the bridge in 60 minutes.
Here is how I solved it. It is a classical problem where you need to move back and forth a couple of times.
Crossing time for each person
A – 5 minutes.
B – 10 minutes.
C – 20 minutes.
D – 25 minutes.
The plan is as the following
|0 minutes||A B C D|
|10 minutes||C D||A & B walks over||A B|
|15 minutes||A C D||A walks back||B|
|40 minutes||A||C & D walks over||B C D|
|50 minutes||A B||B walks back||C D|
|60 minutes||A & B walks over||A B C D|