Assume there are four people who need to cross a narrow bridge at night using a single flashlight.
-
Each person
i
requires a different, known amount of time
ti
to cross the bridge when walking alone.
-
At most two people can be on the bridge at the same time.
-
Whenever one or two people cross, they
must
carry the flashlight with them.
-
If two people cross together, the time for that crossing is the
maximum
of their two individual times (they must move at the speed of the slower person).
-
The flashlight cannot be thrown or sent by any means other than being carried by a person walking back across the bridge.
You are given the four crossing times t1,t2,t3,t4 (positive integers). You may assume, without loss of generality, that they are sorted so that
t1≤t2≤t3≤t4.
Tasks:
-
Determine a strategy (sequence of crossings and returns) that minimizes the
total
time required for all four people to end up on the other side of the bridge with the flashlight.
-
Express the minimal total time in terms of
t1,t2,t3,t4
and clearly describe the order in which people cross and who returns with the flashlight.
Do not write code; just provide the final minimal total time and explain your reasoning and crossing sequence step by step.