# Generalizing this flashlight puzzle

My friend told me a riddle yesterday: four people want to cross a bridge. They each will take $$1$$, $$2$$, $$5$$, and $$10$$ minutes respectively to cross the bridge. They can go across the bridge in groups of $$2$$, which will move as fast as the slowest person. However, they must also travel with a flashlight to not get eaten by the bridge troll. The group only has one flashlight, so after each crossing, someone must return across the bridge with the flashlight.

Question: What's the minimum time to cross the bridge?

Naively, you would send $$1$$ as the "chaperogne", in which case it takes $$19$$ minutes. However, there's a better solution. Send $$1$$ and $$2$$ together, send $$1$$ back, $$5$$ and $$10$$ together, $$2$$ back, $$1$$ and $$2$$ together, for a total of $$17$$ minutes.

There have been questions about this riddle on here before - my question is, can this be generalized? Formally, given a finite sequence of positive naturals $$a_n$$ corresponding to the "bridge-crossing times", is there a way to determine the optimal plan for getting across the bridge?

I suspect this is related to graph theory, which is definitely not my area.

• See this paper. It turns out that the optimal plan for getting across is somewhat subtle. Also, this is discussed over at the code golf network. – Peter Kagey Apr 9 at 17:18