Solution
Fifteen Soldiers and Two Boys
Show the problem again
Fifteen soldiers and two boys stand on one bank of a river. The only boat holds either one soldier or up to two boys (never a soldier together with a boy, and never two soldiers), and needs at least one person aboard to move. Every trip, in either direction, counts as one crossing. What is the minimum number of crossings needed to get all seventeen people to the other bank?
Worked solution
The answer is 61. A soldier can only cross if the boat is on his bank, and the boat comes back only with a boy, so each soldier forces a four-crossing cycle: both boys cross, one boy returns, the soldier crosses, the other boy returns. A breadth-first search over (soldiers left, boys left, boat side) confirms the cost is 4 per soldier plus 1: after fifteen cycles (60 crossings) both boys are on the starting bank and the boat has just returned, and one last crossing carries both boys over, giving 4 x 15 + 1 = 61. Smaller squads give 5, 9, 13, ... crossings, consistent with 4n + 1.
Source: Classic river-crossing puzzle (soldiers and boys) in wide circulation; no traceable original source. Statement written for AxiomIQ.