Дано:
- 3 миссионера и 3 людоеда.
- Лодка вмещает 2 человека.
- Миссионеры боятся оставаться в меньшинстве перед людоедами.
Найти:
- Можно ли переправить всех миссионеров и людоедов через реку, соблюдая условие, что миссионеры не остаются в меньшинстве.
Решение:
1. Обозначим количество миссионеров и людоедов на левом берегу как M (миссионеры) и C (людоеды) соответственно. Изначально M = 3 и C = 3.
2. На правом берегу начальное состояние: 0 миссионеров и 0 людоедов.
3. Лодка может переправить 2 человека за раз, при этом всегда должно оставаться хотя бы 1 миссионер на каждом берегу, если на берегу есть людоеды, чтобы избежать ситуации, когда миссионеры будут в меньшинстве.
4. Разработаем план переправы:
- Первый этап: переправляем 2 людоедов на правый берег. (Левый берег: M = 3, C = 1; Правый берег: M = 0, C = 2)
- Возвращаем 1 людоеда обратно на левый берег. (Левый берег: M = 3, C = 2; Правый берег: M = 0, C = 1)
- Переправляем 2 людоедов на правый берег. (Левый берег: M = 3, C = 0; Правый берег: M = 0, C = 3)
- Возвращаем 1 людоеда обратно на левый берег. (Левый берег: M = 3, C = 1; Правый берег: M = 0, C = 2)
- Переправляем 2 миссионеров на правый берег. (Левый берег: M = 1, C = 1; Правый берег: M = 2, C = 2)
- Возвращаем 1 миссионера и 1 людоеда обратно на левый берег. (Левый берег: M = 2, C = 2; Правый берег: M = 1, C = 1)
- Переправляем 2 миссионеров на правый берег. (Левый берег: M = 0, C = 2; Правый берег: M = 3, C = 1)
- Возвращаем 1 людоеда обратно на левый берег. (Левый берег: M = 0, C = 3; Правый берег: M = 3, C = 0)
- Переправляем 2 людоедов на правый берег. (Левый берег: M = 0, C = 1; Правый берег: M = 3, C = 2)
- Возвращаем 1 людоеда обратно на левый берег. (Левый берег: M = 0, C = 2; Правый берег: M = 3, C = 1)
- Переправляем 2 людоедов на правый берег. (Левый берег: M = 0, C = 0; Правый берег: M = 3, C = 3)
5. Во время всех перемещений количество миссионеров и людоедов на каждом берегу всегда оставалось таким образом, чтобы количество миссионеров не было меньше количества людоедов, где это критично.
Ответ:
- Да, миссионеры и людоеды могут переправиться через реку, следуя предложенному плану.