16. В лодке, вмещающей только двух человек, через реку должны переправиться три миссионера и три каннибала. Миссионеры боятся остаться в меньшинстве. Только один миссионер и один каннибал умеют грести. Помогите им переправиться.

Обозначим гребущего миссионера как М, двух остальных — м₁ и м₂; гребущего каннибала — К, остальных — к₁ и к₂. Стрелка → означает переправу на другой берег, ← — возвращение. В лодке должны быть М или К, поскольку только они умеют грести.

1. М и К →.
2. М ←.
3. К и к₁ →.
4. К ←.
5. М и м₁ →.
6. М и К ←.
7. м₁ и м₂ →.
8. К ←.
9. К и к₂ →.
10. К ←.
11. М и К →.

Ни на одном берегу каннибалов не становится больше, чем миссионеров, если на этом берегу есть миссионеры. Все пассажиры каждой переправы включают умеющего грести.

Ответ: все трое миссионеров и трое каннибалов могут переправиться.