Задача о миссионерах и людоедах
Задача о миссионерах и людоедах, или о каннибалах и миссионерах — классическая задача на пересечение реки.Тесно связана с ней задача о ревнивых мужьях, она же задача о рыцарях и оруженосцах.
Формулировки
- Задача о миссионерах и людоедах. Три миссионера и три людоеда должны пересечь реку на лодке, способной выдержать не более двух человек. При этом на одном берегу не может оставаться больше людоедов, чем миссионеров (иначе миссионеров съедят). Лодка также не может пересечь реку без людей на борту.
Более сложный вариант:
- Задача о ревнивых мужьях. Три женатые пары должны пересечь реку на лодке с теми же условиями и с ограничением, что ни одна из жён не может находиться без мужа в присутствии другого мужчины.
Заметим, что на одном берегу не могут находиться женщин больше, чем мужчин.Таким образом, при замене мужчин миссионерами и женщин людоедами любое решение задачи о ревнивых мужьях также станет решением задачи о миссионерах и людоедах.
Последняя задача известна также в формулировке про рыцарей и оруженосцев — оруженосца в отсутствие его рыцаря обижают другие рыцари.
История
Первое известное упоминание о варианте о ревнивых мужьях находится в средневековом тексте Propositiones ad Acuendos Juvenes, приписываемом Алкуину, умершему в 804 году.В этой формулировке присутствуют три пары братьев и сестёр, но ограничительный фактор всё тот же: ни одна из женщин не может быть в компании другого мужчины без своего брата.В этом же тексте содержится задача о волке, козе и капусте.
С XIII по XV века задача стала известной по всей северной Европе, уже с мужьями и жёнами в формулировке.В более поздней формулировке появляются три пары хозяев и слуг или рыцарей и оруженосцев.Упрощённый вариант с миссионерами и людоедами появляется в конце девятнадцатого века.
Вариации
Очевидным обобщением является изменение числа ревнивых пар, вместимости судна или обоих параметров.
- Если лодка вмещает двух человек, то
- две пары требуют пять поездок,
- для четырёх или более пар задача не имеет решения.
- Если лодка может вместить троих, то можно перевезти до 5 пар.
- Если лодка может выдержать четырёх человек, то возможно перевезти любое количество пар.
- Если в середине реки добавить остров, то любое число пар может пересечь реку на двухместной лодке.