River Crossing

This is the standard missionaries and cannibals problem. The solution using 11 crossings is well-known; I will prove that 11 crossings is necessary, proving that 11 crossings is indeed the minimum.

Clearly the number of crossings must be odd; each crossing, the raft changes sides, and at the end, everyone is on the opposite side of the river, so the raft must also be on the opposite side of the river. (Otherwise, who sent it back?) We can divide the crossings into forward crossings and backward crossings, forward being one going to the destination, and backward being one going from the destination. Each forward crossing can carry at most 2 animals, and each backward crossing must carry at least 1 animal back (otherwise, nobody is carrying the raft). Thus each pair of forward and backward crossings nets a total of at most 1 animal going across. All the crossings, except the last, can be paired off in forward and backward crossings; thus, if there are $p$ pairs, we can send off at most $p+2$ animals ( $p$ for the pairs and 2 for the last forward crossing). We need $p+2 \ge 6$ , so $p \ge 4$ . Thus there are at least 4 pairs of crossings, plus one final forward crossing, for a total of 9.

It now suffices to show that 9 crossings is not enough; the next available number, since it must be odd, is then 11. Assume that 9 crossings is enough; this means we need exact equality. Each forward crossing must carry two animals, and each backward crossing must carry one animal.

The first forward crossing must involve a tiger, which must be left on the other side. The reason is simple: after the first pair, there will be five animals on the original side, so we must have three bulls there (if two, they are outnumbered and eaten). Likewise, the last forward crossing must involve the last tiger.

Note that because we have three bulls, at some point we must have two bulls on side A and one bull on the other side B (because we cannot send all three bulls simultaneously). At this point, there must be two tigers on side A, and one tiger on side B; otherwise some bull will get eaten. This point is either after a forward crossing, or after a backward crossing. But if this is after a forward crossing, what is the next crossing (which must be backward)? If the raft is currently on side A, we cannot send anything: sending a bull means the other bull is eaten, while sending a tiger means the bull on side B will be eaten. So the raft must be on side B. Since side B has two animals, this means this is the point after the first forward crossing. Before this crossing, all three bulls were on side A; after the backward crossing that follows, all three bulls will return back to side A. Similar conclusion can be obtained if we assume this is after a backward crossing; it's the second-to-last crossing, and before the third-to-last crossing, all three bulls are already on side A. Thus in all cases, we showed that if there are two bulls on side A and one bull on side B, then this happens between having three bulls on side A and having three bulls back on side A. In other words, this is not part of crossing all bulls from one side to the other. But this is a contradiction, because we need some point where we have two bulls on side A and one bull on side B, which is part of crossing three bulls from one side to the other; otherwise we can't have all three bulls on the destination.

This shows that 9 crossings is not enough, and thus we need 11 crossings.

(I'm sure the argument can be cleaned up somehow, but I'm not sure how right now.)

1. First, let a tiger and a bull cross together.
2. Then, the bull should cross it back to the unsafe side.
3. Then, the two tigers on the unsafe side should cross.
4. Then one of the tigers should row it back.
5. It gets dropped off, and two of the bulls cross.
6. One of the bulls get dropped of, and one of the tigers cross with the other bull.
7. Next, the two bulls on the unsafe side cross.
8. With the bulls safe, the tiger on the safe side crosses.
9. The tiger picks up one of its fellow tigers and crosses.
10. One of the tigers gets dropped of, and the other one crosses.
11. The two tigers on the unsafe side cross for the last time.

1. 2 tigers cross
2. 1 tiger returns
3. 1 Tiger and 1 Bull cross
4. 1 tiger returns.
5. the tiger gets off and 2 bulls cross.all 3 bulls are now on the safe side.

6. The tiger returns from the safe side. All 3 tigers are now on the unsafe side.

7. 2 tigers cross

8 .1 tiger returns

9 2 tigers cross and all animals are now on the safe side

Thus the minimum number is 9 crossings, not 11.