# $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.

• If "left alone" means they are the only two people in one place, then the rule needs rephrasing. Apr 2, 2015 at 11:59
• The rule should be rephrased either way. The only way a woman can be "left alone" with a man and have her husband present is if her husband is that man. The way it is worded seems to imply that a woman cannot be "left anywhere" with a man (regardless of how many men/women are present) unless her husband is present, even though it states the other. Apr 2, 2015 at 17:37
• So basically, all women must be in a group composed either solely of women, or including her husband? Apr 2, 2015 at 20:18
• Can we reverse the genders in this puzzle so it's not yet another case of classic sexism you always see in logic/philosophy books/courses/instructors? Apr 4, 2015 at 15:05
• @ghosts Not sure why you said it doesn't make sense the other way around... both the puzzle and the implied lack of trust are isomorphic to the gender-flipped version. Apr 6, 2015 at 13:20

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.

• so if there are 5 couples, according to you it will take $2*5-1=9$ trips. But with each trip you can actually only drop 1 person to the other side, because somebody has to bring the boat back, so in 9 trips you can get at most 6 people on the other side. What about the other 4? Apr 2, 2015 at 21:00
• @Novarg that is not what he is saying. He is saying it takes 2*5-1 trips from the starting point to the destination (which is technically what it sounds like the question is asking for?) and 2*5-2 trips in the other direction... Apr 2, 2015 at 21:04
• @Novarg Warlord 099 is correct - I took the term 'trip across' in the question to mean something different from 'back'. I used the term 'river crossings' to include both. Apr 2, 2015 at 22:35
• I've edited my answer to show formulas for both 'trips across' and 'river crossings'. Apr 2, 2015 at 22:55
• @Lawrence, oh, ok. My bad. Here's your +1 :) Apr 3, 2015 at 5:28

One way to keep couples together would be this process:

Husband A ferries Wife A.
Husband B ferries Husband A.
Husband B ferries Wife B.
Husband C ferries Husband B.
Etc.

So, the only time a woman is alone with a man is:
On the far shore, Wife A and Husband A.
On the near short, Wife N and Husband N, before Husband N ferries Husband N-1.
On the boat, each wife is ferried by their husband.

As for total trips, there are $4n-3$ total trips across.

Edit: Surprisingly, if we reverse the genders for the solution, the clause about women being without their husbands is fulfilled.

• When Husband B is ferrying Husband A, Wife B is 'left with' husband C, etc without Husband B present. Apr 4, 2015 at 16:42

When there are X couples on the left and Y couples on the right, with boat on the left:

• Couple A cross from left to right.
• Husband A gets out, Wife A goes back.
• Wife B gets in boat with Wife A. Both cross.
• Wife A gets out, now with her husband.
• Wife B goes back.

We now have X-1 couples on the left and Y+1 couples on the right, and at no time was any woman left with a man, but without her husband. There are moments when a boat arrives that a woman is in the boat and her husband is on the far shore, but she remains in the boat with no man in the boat with her.

Repeat the process X times. When there is only one couple on the left, they cross and the process is done; no one goes back.

This takes N-1 (round) trips, which has to be the minimum. Each trip to the right takes two people (the maximum) and each trip to the left takes one (the minimum). This would be the minimum number of trips necessary if there were no restrictions on who could be left with whom.

• Technically speaking it would take N-2 round trips and 1 one-way trip. N-1 round trips would leave you with the boat and a minimum of one person back on the original shore. Apr 7, 2015 at 18:28