Как львам и антилопам гну пересечь реку

Три льва и три антилопы гну бегут от пожара. Перед ними река с крокодилами (естественно, это ж Африка), так что просто форсировать реку опасно. К счастью, у их берега есть плот, на нем можно добраться на другой берег. Но есть несколько проблем.

  1. На плоту может одновременно находиться максимум двое животных (любых).
  2. Плот без животных вообще на другой берег не поплывет, потому что кто-то должен им управлять.
  3. Если на каком-то берегу львов окажется больше, чем гну, хищнические инстинкты львов возьмут над ними верх, и от гну останутся рожки да ножки.

Вопрос: как животные должны воспользоваться плотом, чтобы всем перебраться на другой берег за минимальное количество ходок?

Посмотреть решение

Есть два варианта развития событий, каждый из которых позволяет достичь нужного результата за одинаковое количество ходок плота. При первом варианте сначала на другой берег плывет пара животных разных видов, при втором — одни львы.

Сначала разберем первый вариант.

Вариант 1

  1. На второй берег плывут лев и гну. Лев остается на берегу, а гну возвращается назад. (2 ходки плота).
  2. На второй берег плывут два льва. Один остается, второй возвращается. (+2 ходки).
  3. Теперь на втором берегу уже два льва. Поэтому единственный вариант — отправить туда двух гну (для соблюдения паритета). Назад на первый берег возвращается пара из одного льва и одного гну (потому что при любом другом варианте на каком-то берегу окажется больше львов, чем гну, а сам собой плот обратно не поплывет). (+2 ходки).
  4. На второй берег плывет пара гну. Единственный лев, остававшийся на втором берегу, плывет обратно на первый. (+2 ходки).
  5. Лев забирает своих сородичей по одному. (+3 ходки).

Итого, чтобы все животные безопасно перебрались на другой берег, понадобится 11 ходок плота.

Вариант 2

Если первыми на другой берег плывут два льва, для переправы всех животных все равно понадобится 11 ходок. Единственное отличие второго варианта в том, что в первой ходке одного льва на второй берег доставляет не гну, а другой лев. Все остальные ходы такие же.

Пишите ваши варианты развития событий в комментариях.

python books logo

Марк Лутц «Изучаем Python»

Скачивайте книгу у нас в телеграм

×