The problem I need to solve is written as the following:
Four people want to cross a bridge on a very dark night. They all begin on the same side and want to do the crossing as quickly as possible. A maximum of two persons can cross the bridge at one time. Any group that crosses, either 1 or 2 people, must have a flashlight with them. There is only one flashlight. The flashlight must be walked back and forth, it cannot be thrown. Each person walks at a different speed. A pair must walk together at the rate of the slower person’s pace, no one can be carried.
Here is the list of persons and their speed:
- $A$ ~ $1\text{ min}$
- $B$ ~ $2\text{ min}$
- $C$ ~ $5\text{ min}$
- $D$ ~ $10\text{ min}$
What is the least amount of time needed to get all four people across the bridge?
Here's how I solved it:
Since each person inevitably has to cross the bridge, the only fact we can manipulate is that someone has to come back each time to get the next person.
$A$ and $D$ cross first, then $A$ goes back. $A$ and $B$ cross second, then $A$ goes back. $A$ and $C$ cross third. In total, that gives me $((10+1) + (2+1) + 5)\text{ min}=(11+3+5)\text{ min}=19\text{ min}$.
The T.A. in class, though, said $19$ was an incorrect answer.
Thoughts?
Your solution is this:
$$\begin{align} ABCD&|&0\\ BC&|AD&10\\ ABC&|D&11\\ B&|ACD&16\\ AB&|CD&17\\ &|ABCD&19 \end{align} $$
whereas you can do this:
$$\begin{align} ABCD&|&0\\ CD&|AB&2\\ ACD&|B&3\\ A&|BCD&13\\ AB&|CD&15\\ &|ABCD&17 \end{align}$$