Missionaries, Cannibals

Three missionaries and three cannibals must cross a river with a boat which can carry at most two people at a time. However, if on one of the two banks of the river the missionaries get outnumbered by the cannibals, they will get eaten. How can all 6 men cross the river without anybody gets eaten?

Remark: The boat cannot cross the river with no people on board.

Label the missionaries M1, M2, M3 and the cannibals C1, C2, C3. Then:

1. M1 and C1 cross the river, M1 comes back.
2. C2 and C3 cross the river, C2 comes back.
3. M1 and M2 cross the river, M1 and C1 come back.
4. M1 and M3 cross the river, C3 comes back.
5. C1 and C2 cross the river, C1 comes back.
6. C1 and C3 cross the river.

Now, everyone is on the other side.

Friends and Enemies

Show that in each group of 6 people, there are either 3 who know each other, or 3 who do not know each other.

Let’s call the people A, B, C, D, E, F. Person A either knows at least 3 among B, C, D, E, F, or does not know at least 3 among B, C, D, E, F.

Assume the first possibility – A knows B, C, D. If B and C know each other, C and D know each other, or B and D know each other, then we find a group of 3 people who know each other. Otherwise, B, C, and D form a group in which no-one knows the others.

If A doesn’t know at least 3 among B, C, D, E, F, the arguments are the same.