You have four people at a bridge... one HAS to carry a flashlight as they cross, but only two can cross at a time. And nobody can go alone.
It only takes the first person 1 minute to cross. The second person takes 2 minutes. The third person takes 5 minutes. And the last one takes 10 minutes.
If the person who takes 1 minute goes with the person who takes 10, it automatically takes 10 minutes.
How many minutes will it take them all to cross at the quickest?
Subscribe to:
Post Comments (Atom)
1 comment:
The key is realizing that the problem is not possible if there was only 1 flashlight. As each group crossing requires exactly 2 people (cannot cross alone mean > 1 and only 2 can cross at a time means <=2) so the first group that crosses will both have to come back as there would be no flashlight for the rest of the team to cross with. However, this puts the whole crossing into a loop where the entire team can never all make it on the other side. Therefore, the only possibility is for there to be more than 1 flashlight. If that were the case, then the problem is simply one of minimizing the sum time of the crossings. Since each crossing takes the amount of time that it takes the slowest member, the solution is simply one where the person that takes 10 mins goes with the person that takes 5. This leaves the person who takes 1 min to go with the person who takes 2 mins for a total time of 12 minutes (with the longer time being 15 minutes.)
Post a Comment