Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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 there are X couples on the left and Y couples on the right, with boat on the left:
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.
