Solution
Five Jealous Couples
Show the problem again
Five married couples stand on the left bank of a river. There is a single boat that holds at most 3 people and needs at least one person to row it (every trip, in either direction, carries 1 to 3 people; anyone can row). Jealousy rule: at no moment, on either bank or in the boat, may a woman be in the company of a man other than her husband unless her husband is also present. (A woman alone among women, or alone entirely, is fine.) There are no islands and nothing can be left in the water. What is the minimum number of one-way boat crossings needed to bring all ten people to the right bank?
Worked solution
The minimum is 11 crossings. An exhaustive breadth-first search over all legal bank configurations (with the boat's position) shows that no sequence of 10 or fewer crossings reaches the goal, and finds a sequence of 11. One such sequence, writing M for men and W for wives by number: M1 W1 cross; M1 returns; W2 W3 W4 cross; W1 returns; M2 M3 M4 cross; M2 W2 return; M1 M2 M5 cross; W3 returns; W1 W2 cross; W1 returns; W1 W3 W5 cross. The key idea is to ferry the wives first in a group while one husband holds the far bank's balance, then swap a couple back so the men can cross as a block.
Source: Variant of the classic jealous-husbands river puzzle; no traceable original source. Statement written for AxiomIQ.