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