Numbers nonexistent

Question

This problem is one of the hardest problems I have ever encountered.

If you don't trust links, here it is:

There are some Couples wanting to cross a river by a boat. The boat can carry at most 3 persons at a time and of course cannot cross the river by itself with no one on board.

The problem is that all the husbands are extremely jealous. So no woman can be in the presence of another man unless her husband is also present. Even a woman alone in a boat at a bank which has other men on that shore without her husband is not permissible.

In other words at no point of time can women outnumber men on bank or shore because that would mean some woman is husband-less!

It may be assumed that everyone knows how to row and all persons on the boat disembark and board at the same time.

Given the constraints provided, the maximum number of couples that can be transported across the river is $n$.

The minimum number of one-way trips needed to transport these couples is $m$.

Find $n \times m$.

I can tell you right now that I wouldn't expect anyone to have solved it without cheating (there are ways).

I don't know where to begin, or even get a number solution.

How would you do this problem?

Answer 1

It can be done with a maximum of $n=5$ couples in $m=11$ trips, for a product of $55$.

First, let's show that more than $5$ couples cannot cross.

If both banks have a man, then every woman must be with her husband so that he won't be jealous. So, if a crossing step starts and ends with men on both banks, it must keep couples together, so it must move exactly one couple (more would exceed the boat's capacity of $3$).

Also, if we say that couples are crossing from the left bank to the right bank, then a crossing left to right cannot increase the number of men on the left, and vice versa. Moreover, a crossing changes the number of men by at most $3$.

Now, let's categorize the legal states by how many men are on each bank and which bank the boat is on. We'll label a state 4-2 if it has 4 men on the left and 2 on the right. This doesn't fully describe the state, since it ignores women, but this suffices for this proof.

We draw a graph of the possible transitions between these states based on the restrictions we found above. The left column lists states with the boat on the left bank, and similarly for the right.

Observe that for $n=6$ or more, the start state at the top doesn't connect to the solution state at the bottom, so $6$ or more couples cannot cross.

But, for $5$ couples, they connect.

We now show that $5$ couples can indeed cross, and it makes a minimum of $n=11$ steps. Note that the segment from 3-2 on the left to 2-3 must be used. Moreover, all steps in the problem are reversible and the banks are symmetric, so it suffices to reach the solution state from after this central move, and play the steps backwards and mirror from before the move to reach the start state.

The central segment has one couple go from right to left, making there be $3$ couples on the left and $2$ on the right. From here, the graph show that $3$ men must travel right, leaving $3$ women on the left and nobody else.

Now, with all men on the right, it's easy to resolve in $4$ more moves by only moving women. One woman take the boat left and brings back $3$ women, then one woman ferries left again and bring the last women over. This can't be shortened, since an even number of moves must be done, and $2$ moves is plainly too few.

The middle $3$ moves are forced, so $m=4+3+4=11$ moves is optimal.

Answer 2

xnor posted his answer as I was writing this, so I decided to go ahead and finish it in any case. I think my solution is a bit more elementary, if more convoluted and less general.

I will show that the maximum possible value for $n$ is $5$. First, we show five is possible.

---

Let men be $\{A,B,C,D,E\}$ and women $\{a,b,c,d,e\}$, where a man and woman are married if they're the same letter.

1. Get $a,b,c$ across, then get $c$ back. ($a,b$ on the other side)
2. Get $c,d$ across, then get $d$ back. ($a,b,c$ on the other side)
3. Get $A,B,C$ across, get $C,c$ back. ($A,a,B,b$ on the other side)
4. Get $C,D,E$ across, get $a$ back. ($A, B, b, C, D, E$ on the other side)
5. Get $a,c, d$ across, then get $a$ back. ($A,B,b, C,c, D,d, E$ on the other side)
6. Get $a, e$ across.

---

We now show that $n\geq6$ cannot be done.

An opening move can consist of taking a couple, or one to three women across, but regardless of the situation the only possibility is some women are left on the other side. Now, no men can cross if there are at least four women waiting on the other side. We will show that if three or less women are on the other side, then no solution can be achieved, which completes the proof.

If three women are on the other side and any men cross, then it must be that those three women's husbands crossed. In that case, the only possibility (aside from undoing the crossing) is that a couple comes back. We thus have $k \geq 4$ couples on one side, and two couples on the other side, and must take some people across.

In this situation, any man that goes across must take his woman with him, and any woman that goes across must take her man with her, so the only possibility is a couple going across. But this precisely undoes our last move, so nothing was gained. This is the big difference from $n=5$; when $n=5$, $k=3$ and we could take the three men across, leaving three women behind since no other men were in their presence.

If two women are on the other side and any men cross, then it must be that those two women's husbands crossed. Moreover, no other man or woman may have crossed: the man would leave his wife behind in presence of other men, and the woman would be in the presence of two men in the boat, without her husband.

We thus have $k \geq 4$ couples on one side, and two couples on the other side, and must get some people back. If only men come back, it must be that both men came back, undoing the previous move. If any woman comes back, her husband must also come back, so it must be that a couple comes back. We now have $k \geq 5$ couples on one side, and a single couple on the other side, and must take some people across. This fails exactly as in the previous case ($k \geq 4$ and two couples on the other side).

Finally, if a single woman is on the other side and any men cross, then it must be that her husband crossed. If only he crossed, we have $k \geq 5$ couples on one side and a couple on the other side, and must get some people back. This fails as above.

If more people crossed with him, it must be that another couple did. We now have $k \geq 4$ couples on one side, and two couples on the other side, and must get some people back. Once again, we fall into a previous a failing case.

---

I think that finding the maximal $n$ was the 'hardest' part of the question, and toying around with it, arguments similar to the ones above will show that the solution I presented uses a minimal number of trips ($m = 11$). There are other ways to reach a solution (particularly the opening moves, leading to having three women waiting on the other side), but in no fewer trips.