Европа · задача 18
Волк, коза и капуста
Как звучало тогда
Некий человек должен был перевезти через реку волка, козу и кочан капусты. Лодка же была такова, что кроме себя он мог взять только одного. А приказано ему было перевезти всё в целости. Скажи, кто может, как переправить их невредимыми?
Условие
Человеку надо перевезти через реку волка, козу и капусту. В лодку помещается он сам и только один из троих. Волка нельзя оставлять с козой, козу — с капустой. Как переправиться? Каково наименьшее число рейсов?
Показать ответ
7 рейсов
О чём эта задача
Задача решается перебором положений: их восемь допустимых, и они образуют граф, в котором надо пройти из одной вершины в другую. Путей ровно два, оба длиной семь, и они зеркальны — второй раз возить назад можно либо козу, либо козу же. То, что задача про графы, стало видно только через тысячу сто лет после Алкуина: у него это загадка для монастырской школы.
Разбор — «как решали тогда» и «как решают сейчас» — для этой задачи ещё не написан.