Урок 9. Процессы: переливания, взвешивания, переправы

Математика · ~55 минут

🎯 Что ты узнаешь

• Как решать задачи на переливания (отмерить 4 литра кувшинами 3 и 5 литров).
• Как искать фальшивую монету на чашечных весах за наименьшее число взвешиваний.
• Как переправлять волка, козу и капусту через реку, не устроив беды.
• Главную идею всех таких задач: думать про состояния и переходы между ними.

📖 Разбираемся в теме

Ты наверняка видел такое в кино: герой стоит перед бомбой, рядом два ведра — на 3 литра и на 5 литров, и нужно отмерить ровно 4 литра, иначе всё взорвётся. Звучит как магия? На самом деле это обычная школьная задача, и сегодня ты будешь щёлкать такие как орешки. А заодно научишься ловить фальшивые монеты и перевозить через реку волка, козу и капусту — да так, чтобы все остались целы.

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

💡 Лайфхак: Любую такую задачу представляй как лабиринт: состояния — это комнаты, разрешённые действия — двери между ними. Иногда удобнее идти от начала, а иногда — от цели назад (вспомни анализ с конца из урока про игры).

Переливания

Есть несколько сосудов без делений; мы умеем только: наполнить сосуд доверху из источника, вылить сосуд полностью, или перелить из одного в другой (пока первый не опустеет или второй не наполнится). Состояние — сколько литров в каждом сосуде. Цель — получить нужный объём.

Взвешивания

Чашечные весы не показывают вес — они лишь говорят, какая чаша тяжелее, или что равновесие. Каждое взвешивание имеет три возможных исхода: левая тяжелее, правая тяжелее, равно. Поэтому одно взвешивание может различить максимум 3 случая, два взвешивания — $3\times 3 = 9$ случаев, три — $27$. Это ключ к тому, чтобы понять, сколько взвешиваний нужно.

Переправы

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

✍️ Разбор примеров

Пример 1. Есть два кувшина: на 3 литра и на 5 литров, без делений. Рядом кран с водой и раковина (можно выливать). Как отмерить ровно 4 литра?

⏱ Попробуй сам, прежде чем читать. Записывай состояние парой (в 3-литровом; в 5-литровом) и ходи: налить / вылить / перелить.

Как рассуждаем. Будем записывать состояние парой (в кувшине 3 л; в кувшине 5 л). Начинаем с (0; 0). Цель — чтобы где-то оказалось 4 литра.

1. Наполним 5-литровый доверху: (0; 5).
2. Перельём из 5-литрового в 3-литровый, пока тот не наполнится. В 3-литровый влезет 3 л, значит из 5-литрового уйдёт 3, останется 2: (3; 2).
3. Выльем 3-литровый: (0; 2).
4. Перельём оставшиеся 2 литра из большого в маленький: (2; 0).
5. Снова наполним 5-литровый доверху: (2; 5).
6. Дольём из 5-литрового в 3-литровый до краёв. В 3-литровом уже 2 литра, влезет ещё 1. Значит из 5-литрового уйдёт 1 литр, останется $5 - 1 = 4$: (3; 4).

В 5-литровом кувшине ровно 4 литра! Вот и обезврежена «бомба» из начала урока.

Ответ: 4 литра отмеряются за 6 шагов по схеме выше.

Пример 2. Те же кувшины 3 и 5 литров. Можно ли отмерить 4 литра другим путём — сначала используя маленький кувшин?

Как рассуждаем. Да, есть «зеркальный» путь. Состояние (3 л; 5 л).

1. Наполним 3-литровый: (3; 0).
2. Перельём всё в 5-литровый: (0; 3).
3. Снова наполним 3-литровый: (3; 3).
4. Дольём в 5-литровый до краёв: в нём было 3, влезет ещё 2, значит из маленького уйдёт 2, останется 1: (1; 5).
5. Выльем 5-литровый: (1; 0).
6. Перельём 1 литр в большой: (0; 1).
7. Наполним маленький: (3; 1).
8. Перельём всё в большой: $1 + 3 = 4$: (0; 4).

Ответ: да; получаем 4 литра в большом кувшине, но дольше — за 8 шагов. Первый путь короче.

🤔 А знаешь ли ты? К одной цели почти всегда ведут разные пути — как в лабиринте. Один короче, другой длиннее. Правильных ответов может быть несколько; математики любят искать самый короткий.

Пример 3. Есть 8 литров воды в большом бидоне и два пустых кувшина — на 3 и на 5 литров. Воду доливать неоткуда (8 литров — это всё). Как разделить воду поровну, чтобы получилось 4 и 4 литра?

Как рассуждаем. Теперь нет крана: вода только переливается между бидоном (8 л, но это «сосуд» с текущим содержимым), кувшином 5 и кувшином 3. Состояние — тройка (бидон; 5-литровый; 3-литровый), в сумме всегда 8. Старт (8; 0; 0). Цель — где-то 4 и 4 (например, бидон 4, пятилитровый 4, трёхлитровый 0).

1. Нальём из бидона в 5-литровый доверху: (3; 5; 0).
2. Из 5-литрового нальём в 3-литровый доверху: (3; 2; 3).
3. Выльем 3-литровый обратно в бидон: (6; 2; 0).
4. Перельём 2 литра из 5-литрового в 3-литровый: (6; 0; 2).
5. Нальём из бидона в 5-литровый доверху: (1; 5; 2).
6. Дольём из 5-литрового в 3-литровый до краёв (там 2, влезет 1): (1; 4; 3).
7. Выльем 3-литровый в бидон: (4; 4; 0).

Теперь в бидоне 4 литра и в 5-литровом кувшине 4 литра — поровну!

Ответ: да, делится поровну (4 и 4) по схеме выше.

Пример 4. Есть 9 монет, одинаковых на вид. Одна из них фальшивая и тяжелее остальных (настоящие весят одинаково). Дано чашечные весы без гирь. Как за 2 взвешивания наверняка найти фальшивую?

⏱ Попробуй сам. Подсказка: у весов 3 исхода, значит и монеты дели на… сколько групп?

Как рассуждаем. Подсчитаем возможности: фальшивой может быть любая из 9 монет — 9 случаев. Два взвешивания дают $3\times 3 = 9$ исходов — ровно столько, сколько нужно. Значит шанс есть, если делить монеты на три равные группы (под три исхода весов).

Разделим 9 монет на три группы по 3: A, B, C.

Взвешивание 1: на левую чашу группу A, на правую группу B.

• Если равновесие — фальшивая не в A и не в B, значит она в группе C.
• Если левая тяжелее — фальшивая (она тяжёлая) в группе A.
• Если правая тяжелее — фальшивая в группе B.

В любом случае мы знаем группу из 3 монет, среди которых фальшивая. Обозначим эти три монеты $x, y, z$.

Взвешивание 2: кладём $x$ на левую чашу, $y$ на правую.

• Равновесие — фальшивая $z$.
• Левая тяжелее — фальшивая $x$.
• Правая тяжелее — фальшивая $y$.

📌 Запомни: На чашечных весах не дели монеты пополам! Дели на три группы — под три исхода весов. Тогда каждое взвешивание режет число подозреваемых втрое, и это самый быстрый способ.

Ответ: двух взвешиваний достаточно; делим по 3, потом из тройки сравниваем две монеты.

Пример 5. Есть 8 монет, одна легче (фальшивая), остальные одинаковы. Найди её за 2 взвешивания.

Как рассуждаем. Возможностей 8, а два взвешивания различают до 9 — должно хватить. Но 8 на три равные группы не делится. Поступим хитро: разделим на группы 3, 3, 2.

Взвешивание 1: 3 монеты против 3 монет.

• Если равновесие — фальшивая среди оставшихся 2 монет (тех, что не взвешивали).
• Если одна чаша легче — фальшивая (она лёгкая) среди тех 3 монет, что на лёгкой чаше.

Случай «равновесие»: осталось 2 монеты, одна легче. Взвешивание 2: одна против другой — лёгкая чаша покажет фальшивую.

Случай «нашли тройку с фальшивой»: взвешивание 2 — одну монету против другой из этой тройки. Равновесие → фальшивая третья; иначе лёгкая чаша указывает на фальшивую.

Ответ: 2 взвешиваний достаточно; делим 3-3-2.

Пример 6. Через реку нужно перевезти волка, козу и капусту. Лодка маленькая: за раз помещается только перевозчик и один «груз». Нельзя оставлять без присмотра волка с козой (волк съест козу) и козу с капустой (коза съест капусту). Волк и капуста друг другу безразличны. Как перевезти всех?

⏱ Попробуй сам. Подсказка: кто здесь самый «проблемный»? И не бойся возить кого-то обратно.

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

1. Перевозчик берёт козу на тот берег (на исходном остались волк и капуста — они мирные). Возвращается один.
2. Берёт волка на тот берег. Но там уже коза — нельзя их оставить! Поэтому, высадив волка, забирает козу обратно. Теперь на том берегу волк, на этом — коза и капуста (перевозчик с ними).
3. Высаживает козу на исходном берегу, берёт капусту и везёт на тот берег. Там теперь волк и капуста — они мирные. Возвращается один.
4. Берёт козу и везёт на тот берег. Готово: все трое переправлены.

Проверим, что ни разу не было беды: коза оставалась без присмотра только тогда, когда враги (волк или капуста) были на другом берегу. Всё чисто.

Ответ: перевозим козу, возвращаемся; везём волка, козу забираем обратно; везём капусту, возвращаемся; везём козу. Всего 7 рейсов лодки.

💡 Запомни главное

• Думай про состояния и переходы между ними; задача — найти путь от старта к цели.
• В переливаниях записывай состояние как набор чисел и делай шаги: налить доверху / вылить / перелить до края.
• Часто помогает идти от цели назад или возить «обратно» (как козу).
• На чашечных весах у каждого взвешивания три исхода: дели предметы на три группы.
• $k$ взвешиваний различают до $3^k$ случаев: 1 → 3, 2 → 9, 3 → 27.
• В переправах найди «нарушителя» (того, кого нельзя оставить ни с кем) и оберегай его.

📝 Домашнее задание

1. Кувшины 3 и 5 литров, кран и раковина. Отмерь ровно 1 литр. (Подсказка: загляни в шаги примера 2.)

2. Кувшины 3 и 5 литров, кран и раковина. Отмерь ровно 2 литра.

3. Кувшины 4 и 9 литров, кран и раковина. Отмерь ровно 6 литров.

4. Есть 4 монеты, одна тяжелее. За сколько взвешиваний её точно найти? Опиши схему.

5. Есть 3 монеты, одна тяжелее. Хватит ли одного взвешивания? Как?

6. Есть 27 монет, одна тяжелее. За сколько взвешиваний найти? Почему именно столько? (Подумай про $3^k$.)

7. Через реку надо перевезти волка, козу и капусту (правила как в примере 6). Можно ли обойтись меньше, чем за 7 рейсов? Объясни.

8. ⭐ Есть 12 монет, одна фальшивая, но неизвестно, легче она или тяжелее настоящих. Докажи, что за 3 взвешивания можно и найти фальшивую, и узнать, легче она или тяжелее. (Подсказка: сначала прикинь, сколько всего вариантов и хватает ли $3^3 = 27$ исходов; потом дели по 4.)