Примерное время на чтение статьи: 4 минуты

В этой статье предлагаем познакомиться с решением классической задачи о переправе фермером на лодке через реку своего хозяйства без потерь.

Жили у фермера пёс и собачка,

Кот и цыплёнок, клевавший зерно.

Хозяйство немалое, да вот задачка:

В лодке должно оно провезено.

Лодка мала, а река широка.

Лодка вмещает троих лишь едва.

Пёс на собачку грозно рычит.

Собачка кота цапнуть вмиг норовит.

Котик цыплёнка гоняет с утра.

Цыплёнок зерно клюёт, ну и хандра

На нашего фермера тут нападёт.

В затылке почешет: «Ну, что же — вперёд!»

Попробуйте решить головоломку самостоятельно, а потом прочитайте статью и посмотрите наше видео.

Переправа через реку на лодке: анализ

Эта классическая логическая головоломка на переправу.

Она имеет ключевые признаки задач этого типа:

1. Ограниченные ресурсы — маленькая лодка, вмещающая двоих или троих (фермера + одного, двух «пассажиров»).
2. Система запретов. Ряд персонажей нельзя оставлять вместе без присмотра, так как это ведёт к конфликтам (пёс ↔ собачка, собачка ↔ кот, кот ↔ цыплёнок, цыплёнок ↔ зерно).
3. Цель — безопасно переправить всех через реку, соблюдая ограничения.
4. Пошаговая стратегия. Требуется найти последовательность переправ, исключающую конфликты.

Аналогичные головоломки:

• «Волк, коза и капуста» (классический вариант);
• «Лиса, курица и зерно»;
• «Пантера, свинья и овсянка» и др.

Анализ условия.

Анализируя конфликтные пары, которые нельзя оставлять без фермера (пёс ↔ собачка, собачка ↔ кот, кот ↔ цыплёнок, цыплёнок ↔ зерно), замечаем, что они состоят из соседей при расположении персонажей в один ряд: пёс, собачка, кот, цыплёнок, зерно. Значит, можно определить неконфликтные объекты, которые не являются соседями, в ряду расположены через одного. Это:

• пёс — кот — зерно;
• собачка — цыплёнок. — Это и будет первая пара, которую фермер переправит на лодке через реку на правый берег.

Остальных (пса, кота, зерно) он будет брать по очереди позже. Главное — никогда не оставлять «хищника» с «жертвой» без присмотра.

Переправа через реку на лодке: решение

Суть решения.

Нужно методично перевозить объекты, периодически возвращаясь за новыми и забирая обратно уже переправленных, чтобы не нарушать запреты. Ключевой приём — временно возвращать кого-то или что-то на исходный берег, чтобы освободить место для следующего «пассажира».

Всего переправа через реку на лодке состоит из 7 рейсов.

После перевозки первой неконфликтной пары у фермера будет два выбора, каждый из которых предоставит свои варианты:

Первый выбор. Оставляет обоих на правом берегу и во втором рейсе возвращается один. Дальнейшая переправа через реку на лодке будет иметь 6 вариантов.

Второй выбор. Оставляет одного из них на правом берегу, с другим возвращается во втором рейсе на левый берег. И здесь возникает ещё 2 варианта (седьмой и восьмой) дальнейшей переправы через реку на лодке.

Таким образом, до этого момента мы узнали о восьми вариантах решения головоломки о переправе через реку на лодке. На самом, деле, их больше. Попробуйте самостоятельно найти другие варианты.

Головоломка тренирует алгоритмическое мышление, умение планировать действия с учётом ограничений, анализировать последствия каждого шага. Это делает её популярной среди детей и взрослых.

Эту задачу можно отнести к дискретной (дискретный — состоящий из отдельных частей, прерывный, дробный) математике — точнее, к её прикладным разделам, связанных с оптимизацией, теорией графов и алгоритмическим мышлением.

Почему это дискретная математика?

1. Дискретные состояния системы. Задача описывает конечное число объектов и чётко определённые бинарные отношения между ними («нападает», «ест»). Система переходит из одного состояния в другое при каждой переправе.
2. Конечное пространство поиска. Все возможные конфигурации (кто на каком берегу) можно перечислить — это типичная дискретная структура. Проблема сводится к поиску пути в графе состояний.
3. Теория графов. Задачу можно моделировать как граф:

• Вершины — допустимые конфигурации объектов на берегах.
• Рёбра — разрешённые переходы (переправы).
• Цель — найти путь от начального состояния к конечному без попадания в «запрещённые» вершины (где кто-то подвергся нападению).

4. Алгоритмический подход.

1) Решение требует построения последовательности действий с проверкой условий на каждом шаге.

2) Логические ограничения. Условия типа «если оставить пса с собачкой — будет нападение» — это булевы ограничения на состояния.

Аналогии.

• Задачи о переправах (классика: «волк, коза и капуста») — стандартный учебный пример в курсах по дискретной математике и искусственному интеллекту.
• Поиск в пространстве состояний — метод, используемый в алгоритмах оптимизации.
• Констрейнт-программирование — решение задач с ограничениями на дискретных доменах.

Вывод. Хотя задача имеет «бытовую» формулировку, её суть — поиск дискретной последовательности переходов в системе с ограничениями. Это делает её типичным объектом изучения в дискретной математике, особенно в разделах, связанных с теорией графов, дискретной оптимизацией, алгоритмическим решением задач.

Советы при решении головоломки на переправу через реку на лодке:

1. Если будете решать с ребёнком, то посоветуйте ему делать рисунки на бумаге и представлять, что он работает с пазлом, то есть собирает «безопасные» группы.
2. Придумайте свой вариант с другими объектами. А можно усложнить цепочку, добавив ещё один персонаж.

Поделитесь в комментариях своим временем на решение!

А, может быть, у вас получились свои варианты?

Видео