Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
6 Formatting
source | link

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

DefinitionsDefinitions: '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.

  • 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 WW) returns.

Send all the men across. This requires $n-1$ trips, leaving the boat at the destination. W'sW'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.

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.

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.

5 Modified the solution for the changed question.
source | link

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.

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.

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.

4 Added a note regarding the change in question.
source | link

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.

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.

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.

3 Added formula for number of river crossings.
source | link
2 added 250 characters in body
source | link
1
source | link