mathematics - $n$ couples crossing a river

There are $n$ couples on one side of the river. Nobody is on the other side. They have a boat that accommodates up to 2 people. For every trip across, someone(s) must bring the boat back as well. The aim is for all of them to cross the river.

There is one important rule:

No woman can be left (in the boat or either shore) with a man, unless her husband is also present.

There are no tricks, such as divorcing during the game, etc.

Give a formula to find the minimum number of boat trips required.

Answer

Note: This answers the question before the question was changed from "left alone ... with" to just "left ... with".

Definitions:

• 
  

  trip across means going from the original side to the destination side

  
  


• 
  
  

  woman left alone with a man means those individuals are the only two people in that place.

  
  

Send all the women across first. This requires $n-1$ trips, leaving the boat at the destination. One woman (call her W) returns.

Send all the men across. This requires $n-1$ trips, leaving the boat at the destination. W's husband returns and both go across (1 trip).

Total $2n-1$ trips across to the other side. Each trip across is matched with a trip back except for the last trip across, so we have $4n-3$ river crossings.

In the first phase, every woman is in the company of either only women or with her husband. In the second phase, W remains with her husband or is alone, and all other women are with at least the number of people they were with in the first phase.

This is minimal since each pair of river crossings can deposit only 1 person at the destination if someone must return with the boat. After $2n-2$ pairs of river crossings (and hence $2n-2$ trips across), only 2 people remain on the original side. They take the final trip across to total $2n-1$ trips across.

---

With the reworded question, we can still have the same number of river crossings with a different order.

The "left with" rule is taken to mean that a woman can be in a boat on her own or with another woman, or on a shore with her husband (or with only women). In particular, a woman is permitted to cross to the shore opposite her husband's, provided she does not disembark and provided she returns with another woman.

Pair each man $M_i$ with his wife $W_i$ for $i \in [1,n]$. Starting with $i=1$ and working through to $i=n$, send $M_i,W_i$ across, $W_i$ returns, picks up $W_{i+1}$ and goes across again. Then $W_{i+1}$ returns.

Each trip across deposits one person, so we still have $2n-1$ trips across and $4n-3$ river crossings.