$n$ monsters and $n$ people

There are $n$ monsters (M) and $n$ people (P) on the left side of a river. Nobody is on the right.
They have a boat that can hold up to 2 beings. At no point on time may either of these be true: $$M_{shore1}+M_{boat}>P_{shore1}+P_{boat}$$ $$M_{shore2}+M_{boat}>P_{shore2}+P_{boat}$$

What is the minimum number of boat trips required for
(a) $n=4$
(b) $n=5$
(c) $n=100$

Also provide a formula for arbitrary $n$, if possible.

P.S. I have found a solution using induction. I'm not sure if it is optimal, I'll post it soon, if needed.

• I assumed all cases above 3 were impossible. – Joe Z. Apr 2 '15 at 2:44

TL;DR The general formula for fewest trips is:

$4n-3$

Giving values for (a), (b), (c):

(a) 13
(b) 17
(c) 397

The possible combinations for the first trip are: MM, MP, PP, M, P. We can immediately discount a first trip carrying an individual as the return trip would need to be made by that individual, causing no change to the number of beings on the second shore and therefore unnecessarily increasing the number of trips.

It follows that exactly 2 beings must occupy the first trip and exactly 1 of these beings must be on the return trip, leaving 1 being on the second shore.

Case MM:

Upon boarding the boat, the second inequality is true:
$M_{shore2}+M_{boat}>P_{shore2}+P_{boat}$
$0+2 > 0+0$
This contradicts the condition that "At no point on time may either of these be true".
$\therefore$ MM is not a valid first trip.

Case PP:

Upon disembarking the boat, the first inequality is true:
$M_{shore1}+M_{boat}>P_{shore1}+P_{boat}$
$n+0 > n-2+1$
This contradicts the condition that "At no point on time may either of these be true".
$\therefore$ PP is not a valid first trip.

Case MP:

Upon reaching the second shore, P may choose to disembark. This makes the first inequality true:
$M_{shore1}+M_{boat}>P_{shore1}+P_{boat}$
$n-1+1>n-1+0$
$\therefore$ P may not disembark on this trip.
Suppose then that M disembarks. This satisfies the condition.
$M_{shore1}+M_{boat} \le P_{shore1}+P_{boat}$
$n-1+0 \le n-1+1 \implies n-1 \le n$
$M_{shore2}+M_{boat} \le P_{shore2}+P_{boat}$
$1+0 \le 0+1 \implies 1 \le 1$

With this knowledge, we can deduce that the second trip to shore 2 must also have at least one P in the boat.

Case MP:

Upon boarding the boat, the second inequality is true.
$M_{shore2}+M_{boat} > P_{shore2}+P_{boat}$
$1+1 > 0+1$
$\therefore$ because this contradicts the rule, we know MP is an invalid second trip.

Case PP:

This satisfies the condition.
$M_{shore1}+M_{boat} \le P_{shore1}+P_{boat}$
$n-1+0 \le n-2+1 \implies n-1 \le n-1$
$M_{shore2}+M_{boat} \le P_{shore2}+P_{boat}$
$1+0 \le 1+1 \implies 1 \le 2$

We can extend this logic to arbitrary $M_{shore2} = k$.

P must be on the boat, leaving us two possibilities: $P_{shore2} \in \{k-1, k\}$

Case $P_{shore2} = k$:

M boards the boat piloted by P for the trip to shore 2.
In transit:
Shore 1: $(n-k-1) + (1) \le (n-k) + (1)$
Shore 2: $(k) + (1) \le (k) + (1)$
Once landing and M disembarks:
Shore 1: $(n-k-1) + (0) \le (n-k) + (1)$
Shore 2: $(k+1) + (0) \le (k) + (1)$
If this is the last trip, P also disembarks (just make sure to get off the boat after M).

Case $P_{shore2} = k-1$:

P boards the boat piloted by P for the trip to shore 2.
In transit:
Shore 1: $(n-k) + (0) \le (n-(k-1)-1) + (2)$
Shore 2: $(k) + (0) \le (k-1) + (2)$
Once landing and P disembarks:
Shore 1: $(n-k) + (0) \le (n-(k-1)-1) + (1)$
Shore 2: $(k) + (0) \le (k-1+1) + (1)$
If this is the last trip, the second P also disembarks.

The total number of trips to shore 2 are:

$2n-1$ Since we are only letting off one being per trip, we need to take $2n$ trips. Subtract $1$ because the last trip lets off two beings.

The total number of trips returning to shore 1 are:

$2n-2$ We make the same number of return trips as we made initial trips, less one because we don't make a final return.

This gives us a total number of trips as:

$2n-1 + 2n-2$
$= 4n-3$

This is optimal because it takes 2 beings on the trip to shore 2 and returns with only 1 being. In order to reduce the number of trips, the boat would need to carry more than 2 beings or the return trip would need to be made with nobody in the boat.

Given the constraint that monsters must not outnumber people anywhere, your process is: Human in boat (stays in boat as ferryman), ferry monster, ferry human, ferry monster, ferry human, etc.

So, trips = $4n-3$

• Somebody has to bring the boat back to the left shore as well as. – ghosts_in_the_code Apr 1 '15 at 14:36
• @ghosts_in_the_code I think he's saying that the "Human in boat" at the beginning stays in the boat until the end. – KSmarts Apr 1 '15 at 14:45
• If the human ferries the second human, then there are $n-1$ monsters and $n-2$ humans on the left side. – Joe Z. Apr 2 '15 at 2:46
• You're neglecting the humans in the boat, which brings the human count up to $n$ – JonTheMon Apr 2 '15 at 12:57

At least one person must always stay in the boat, otherwise we'll have this contradiction:

$M1 + MB > P1 + PB$
$M2 + MB > P2 + PB$
Summing, assuming PB=0:
$(M1+M2) +2MB > (P1+P2)$
Since $(M1+M2)=(P1+P2)$ the above condition would be always verified, making the problem impossible.

So, one human does the ferryman, transporting the others across the river. He starts with a monster, then comes back to shore 1, brings a human to shore 2, comes back to shore 1 and restarts. There are $2n-1$ creatures to be transported in addition to the sailor, and for each one (except the last) the ferryman must come back to shore 1.
Overall it requires $2\times(2n-1)-1 = 4n-3$

1. n=4 requires 13 trips
2. n=5 requires 17 trips
3. n=100 requires 397 trips