B5 Переправы и перевозки

Идея метода: свести задачу о переправке людей (предметов, животных) через реку, мост или иное препятствие к анализу минимального числа рейсов, порядка действий или оптимальной стратегии.

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

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

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

• Формула минимального числа рейсов для $n$ человек с лодкой на 2 места, у которых разная скорость: переправа $n$ человек требует $2(n-2)+1 = 2n-3$ рейсов, если за каждый обратный ход лодку ведёт самый быстрый из оставшихся на дальнем берегу. Условие: $n \geq 2$, лодка вмещает ровно 2 человека. Когда использовать: когда нужно минимизировать время/число переходов через реку при одной лодке.

• Принцип инвариантности числа: если каждый рейс перемещает ровно $k$ человек в одну сторону, а в обратном направлении идёт $1$ человек, то каждые два рейса суммарно перебрасываются $k-1$ человек. Условие: в каждом рейсе назад обязательно возвращается хотя бы один. Когда использовать: для нижней оценки числа рейсов.

• Лемма о невозможности: если среди $n$ участников есть условие несовместимости (волк и коза, кошка и мышь), то задача сводится к поиску допустимого порядка. Если ограничений $k$ и лодка везёт одного, задача не всегда разрешима: проверяем граф совместимости. Когда использовать: задачи типа «фермер, волк, коза, капуста».

• Ввести переменную «кто возвращается». Обозначить, какой человек (самый быстрый, самый лёгкий) ходит туда-обратно как «ферри» — это часто сразу даёт оптимальный алгоритм.
• Разбить процесс на фазы. Каждая фаза = один «пакет» переправы. Для $n$ человек при лодке на 2 — фаза: двое переплывают, один возвращается.
• Нижняя оценка через инвариант. Подсчитать, сколько «полезных» перемещений (в нужную сторону) происходит за каждые 2 рейса, и отсюда получить нижнюю оценку числа рейсов.
• Построить граф состояний для задач с условиями несовместимости: вершины — допустимые состояния (кто где находится), рёбра — допустимые рейсы. Ищем путь от начального состояния к конечному.
• Симметрия задачи. Если условие симметрично (левый и правый берег равноправны), проверить: можно ли применить стратегию зеркально.
• Жадный алгоритм + проверка оптимальности. Для задач минимизации: предложить жадную стратегию, затем доказать, что отклонение от неё не улучшает результат.

Поверхностные признаки (что буквально написано):
- В условии есть «лодка», «мост», «паром», «переправа», «берег», «перевезти».
- Упоминается вместимость: «лодка вмещает не более $k$ человек», «мост выдерживает $w$ кг».
- Есть условие, что кто-то должен возвращаться назад (иначе лодка не вернётся).

Структурные признаки (форма выражения, объекты):
- Группа объектов нужно переместить из A в B с ограничениями на каждый шаг.
- Среди объектов есть пары «несовместимых» (не могут быть оставлены вместе без надзора).
- Задача содержит параметр: найти минимальное число рейсов для $n$ человек/предметов.

Цель задачи (что от тебя хотят):
- Найти минимальное число переходов/рейсов/шагов.
- Доказать, что переправа возможна или невозможна при данных ограничениях.
- Описать оптимальную стратегию (последовательность рейсов).

Задача 1. Пятеро туристов переправляются через реку

Условие: Пятеро туристов хотят переправиться через реку на лодке, которая вмещает не более 2 человек. Время переправы каждого туриста: 1, 2, 5, 8, 10 минут. При совместном плавании пара движется со скоростью медленнейшего. Какое минимальное суммарное время переправы всех пятерых?

Источник: классическая олимпиадная задача (тренировочная)

Как думать (рассуждение ученика):
1. Вижу: лодка на 2 человека, разные скорости — это классическая задача на переправу. Триггер: «лодка вмещает не более 2 человек», «время переправы», «минимальное время».
2. Метод: задача на оптимальную переправу. Стратегия: самые медленные переправляются вместе, а быстрый (1 мин) выступает «паромщиком».
3. Первый ход: попробую две стратегии и сравню. Стратегия A: быстрейший (1) всегда сопровождает медленных. Стратегия B: двое медленных переправляются без быстрейшего.
4. Ключевая идея: медленные (8 и 10) обязательно должны плыть вместе, иначе мы платим 10+8=18 за два рейса вместо 10 (при одном совместном). Значит, нужно организовать так, чтобы 8 и 10 плыли в одной лодке.

Решение:
Обозначим туристов по временам: $A=1, B=2, C=5, D=8, E=10.

$Стратегия:$
1. A$ и B переплывают → 2 мин. A возвращается → 1 мин.
2. D и E переплывают → 10 мин. B возвращается → 2 мин.
3. A и C переплывают → 5 мин. A возвращается → 1 мин.
4. A и B переплывают → 2 мин.

Итого: $2+1+10+2+5+1+2 = 23$ мин.

Альтернатива (A всегда паромщик): $1+1+1+1+\ldots$ — каждый раз A возвращается, но тогда D и E плывут отдельно: платим 8+10=18 за их рейсы плюс накладные расходы. Итог хуже.

Ответ: 23 минуты.

Что в этой задаче было главным для понимания метода: ключевая идея — переправить двух самых медленных вместе, а роль «быстрого паромщика» поочерёдно выполняют A и B. Это не очевидно без разбора стратегий.

Задача 2. Фермер, волк, коза и капуста

Условие: Фермер должен перевезти через реку волка, козу и кочан капусты. Лодка вмещает фермера и одного пассажира. Без фермера: волк съест козу, коза съест капусту. Как переправить всех?

Источник: классическая логическая задача (тренировочная)

Как думать (рассуждение ученика):
1. Вижу ограничения несовместимости: (волк, коза) без фермера — плохо; (коза, капуста) без фермера — плохо. Волк и капуста вместе — нормально.
2. Метод: граф состояний. Состояние = (что на левом берегу, что на правом, где лодка).
3. Первый ход: сначала нужно убрать козу — она несовместима с обоими. Везу козу.
4. Ключевая идея: «проблемный» объект (коза) должен побывать на правом берегу первым, а потом, когда везём волка или капусту — козу временно возвращаем.

Решение:
Фермер перевозит козу → (волк, капуста слева; коза справа).
Фермер возвращается → везёт волка → (капуста слева; волк, коза справа).
Фермер возвращается с козой → везёт капусту → (коза слева; волк, капуста справа).
Фермер возвращается → везёт козу → все справа. Итого 7 рейсов.

Ответ: 7 рейсов, стратегия описана выше.

Что в этой задаче было главным: «возврат» проблемного объекта назад — нестандартный ход, который открывает граф состояний. Без него кажется, что задача нерешаема.

• Ошибка: забыть учесть обратные рейсы. Считают только рейсы «туда», игнорируя, что кто-то должен вернуть лодку. → Каждый «туда», кроме последнего, порождает обратный рейс — включай их в подсчёт.
• Ошибка: считать, что быстрейший должен ездить туда-обратно всегда. Для задачи с 4+ людьми иногда выгодно, чтобы второй-быстрый возвращался, пока первый ждёт. → Проверяй обе стратегии явным подсчётом.
• Ошибка: не проверить нижнюю оценку. Предъявил стратегию, но не доказал, что быстрее нельзя. → Используй аргумент: сколько «полезных» переходов совершается за 2 рейса, и отсюда оцени снизу.
• Ошибка: в задачах с несовместимостью не перебрать все состояния. Кажется, что одно решение — единственное, хотя есть другое. → Явно строй граф состояний или доказывай единственность.
• Ошибка: нарушить ограничение в промежуточном состоянии. Забыть, что коза и капуста не могут оставаться вместе даже на секунду. → Проверяй каждый промежуточный шаг, а не только начало и конец.