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

Математика

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

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

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

Представь: нужно отмерить ровно 4 литра воды, а под рукой только два кувшина без делений — на 3 литра и на 5 литров. Линейкой воду не измеришь, но задача всё равно решается: несколькими переливаниями из кувшина в кувшин. Сегодня ты научишься решать такие задачи-переливания, а заодно находить фальшивую монету на весах без гирь и перевозить через реку волка, козу и капусту так, чтобы все остались целы. Объединяет их одно: ответ находят не вычислением, а продуманной последовательностью действий.

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

Решить задачу — значит найти цепочку состояний от начального к нужному, делая только разрешённые шаги.

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

Что такое процесс

Процесс — это когда с системой снова и снова повторяют какое-то действие (или несколько действий), и она проходит через ряд состояний:

Здесь $S_0$ — начало, а стрелка — один шаг процесса. Переливания, взвешивания, переправы — всё это процессы. Но процессов гораздо больше: перекладывание камней из кучки в кучку, стирание чисел на доске и замена их другими, перекрашивание клеток… Про такие задачи математики задают три главных вопроса:

1. Куда можно попасть? Какие состояния достижимы, а какие — нет никогда?
2. Закончится ли процесс? Или он может крутиться вечно?
3. Сколько шагов нужно? Можно ли оценить число шагов сверху или снизу?

Сегодня мы разберём инструменты, которые отвечают на эти вопросы, и увидим их в переливаниях, взвешиваниях и переправах.

Инвариант: то, что не меняется

Иногда во время процесса какая-то величина вообще не меняется, что бы мы ни делали. Такую величину называют инвариантом (от латинского invariabilis — «неизменный»). Инвариант — сторож: если в цели он должен быть одним, а в старте он другой, то цель недостижима, и никакая цепочка шагов не поможет.

📌 Запомни: Инвариант — это величина, одинаковая во всех достижимых состояниях. Если у старта и у цели инварианты разные, путь между ними невозможен. Это способ доказать, что чего-то сделать нельзя.

Простой пример из переливаний. Пусть есть бидон с 8 литрами и два кувшина, а крана и раковины нет: воду только переливают. Тогда общее количество воды всегда $8$ литров: сколько бы мы ни переливали, сумма не меняется. Это инвариант. Значит, состояние, где воды стало $7$ или $9$ литров, недостижимо, и доказывать это перебором не нужно.

Полуинвариант: то, что меняется в одну сторону

А теперь — главный герой урока. Часто во время процесса есть величина, которая меняется только в одну сторону: например, только убывает (или только растёт). Такую величину называют полуинвариантом (иногда — монотонной величиной или «моновариантом»).

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

Зачем это нужно? Полуинвариант — это доказательство, что процесс не может длиться вечно. Рассуждение такое:

Пусть при каждом шаге некоторая величина строго убывает, и при этом она всегда остаётся целым неотрицательным числом (то есть $\ge 0$). Тогда шагов может быть только конечное число! Ведь она стартует с какого-то числа $N$, каждый шаг сбрасывает её хотя бы на $1$, а меньше нуля она стать не может. Значит, шагов не больше $N$.

Это и есть знаменитое «процесс обязательно закончится». Целое число не может бесконечно уменьшаться, оставаясь неотрицательным, рано или поздно оно упрётся в дно, и делать новый шаг станет нельзя. А это часто означает, что мы пришли к цели.

🤔 А знаешь ли ты? Полуинварианту не обязательно убывать ровно на 1. Достаточно, чтобы он строго уменьшался хотя бы на какую-то величину и был ограничен снизу. Главное — движение в одну сторону и наличие «дна» (оценка снизу) или «потолка» (оценка сверху).

Оценка сверху и снизу

Чтобы полуинвариант «сработал», нужны две вещи:

• Направление. Доказать, что величина при каждом шаге меняется в одну сторону (скажем, убывает).
• Граница. Показать, что дальше некуда: есть оценка снизу (величина $\ge$ чего-то) или оценка сверху (величина $\le$ чего-то).

Направление + граница = процесс конечен. А заодно граница часто даёт и число шагов: если величина стартует с $N$, падает хотя бы на $1$ за шаг и не опускается ниже $0$, то шагов не больше $N$. Вот тебе оценка сверху на длину процесса.

⚠️ Осторожно: Одного «величина убывает» мало! Число может убывать вечно: $10>9.9>9.99>\dots$, и не кончиться. Спасает именно целость (или другая граница): целое неотрицательное число убывать бесконечно не может. Всегда проверяй обе части.

Взвешивания — тоже про оценку. Число «подозреваемых» монет — это величина, которую мы загоняем вниз: каждое удачное взвешивание делит её примерно на $3$. А снизу она ограничена единицей (когда подозреваемый один, мы нашли фальшивку). Так связаны процесс, полуинвариант и оценка.

Переливания

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

В переливаниях с краном и раковиной прячется красивый инвариант. Если у нас кувшины на $a$ и $b$ литров, то отмерить можно ровно те объёмы, которые кратны наибольшему общему делителю чисел $a$ и $b$. Для $3$ и $5$ их НОД равен $1$, поэтому отмерить можно любое целое число литров от $0$ до $8$, в том числе и наши $4$. А вот кувшинами $4$ и $6$ (их НОД равен $2$) нечётное число литров не отмерить никогда: наливаем и выливаем мы только порциями по $4$ и $6$ литров, обе чётные, и переливание чётность сохраняет, поэтому в каждом кувшине всегда оказывается чётное число литров. Это инвариант чётности!

Взвешивания

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

Обрати внимание, как здесь работает оценка снизу: если случаев больше, чем $3^k$, то за $k$ взвешиваний точно не справиться. Исходов физически не хватит, чтобы их различить. Это доказывает, что меньшим числом взвешиваний обойтись нельзя. А оценка сверху (схема деления на три группы) показывает, что нужного числа взвешиваний достаточно. Когда обе оценки сходятся, мы нашли точный ответ.

Переправы

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

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

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

Пример 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. Заметь инвариант: общее количество воды всегда равно $8$ — это нам ещё пригодится для проверки. Состояние — тройка (бидон; 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 литра — поровну! Проверка инвариантом: на каждом шаге сумма трёх чисел равна $8$, значит нигде не ошиблись в арифметике.

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

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

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

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

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

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

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

В любом случае мы знаем группу из 3 монет, среди которых фальшивая (подозреваемых стало $3$ вместо $9$: полуинвариант упал втрое). Обозначим эти три монеты $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,\dots ,10$. За один ход разрешается стереть любые два числа $a$ и $b$ и вместо них написать одно число — их сумму $a+b$. Так делают, пока на доске не останется одно число. Сколько ходов понадобится? И какое число останется в конце?

⏱ Попробуй сам. Подумай: какая величина при каждом ходе меняется предсказуемо?

Как рассуждаем. Здесь два разных наблюдения, и оба про процессы.

Сколько ходов? Следим за полуинвариантом «сколько чисел на доске». В начале их $10$. Каждый ход убирает два числа и добавляет одно, то есть их количество убывает ровно на $1$. Оно всегда целое и не может стать меньше $1$. Стартовали с $10$, хотим дойти до $1$, значит ходов ровно $10-1=9$. Никак не больше и не меньше: полуинвариант убывает строго на единицу, и число шагов посчитано железно.

Какое число останется? А тут работает инвариант «сумма всех чисел на доске». Стирая $a$ и $b$, мы пишем $a+b$: общая сумма не меняется! Значит она всё время равна начальной:

Когда останется одно число, оно и есть эта сумма — $55$.

💡 Лайфхак: В процессах ищи сразу два вида величин. Инвариант (не меняется) отвечает на «что будет в конце». Полуинвариант (меняется в одну сторону) отвечает на «закончится ли и за сколько шагов». Часто в одной задаче полезны оба.

Ответ: ровно $9$ ходов; в конце останется число $55$.

Пример 7. (Процесс обязательно закончится.) В одной кучке лежит $7$ камней, в другой — $10$. Двое по очереди делают ходы: за ход можно взять из одной кучки сколько угодно камней (хотя бы один). Игрок, взявший последний камень, выигрывает. Докажи, что игра не может тянуться бесконечно: рано или поздно камни кончатся.

Как рассуждаем. Нас просят не найти победителя, а доказать, что процесс конечен. Возьмём полуинвариант: общее число камней на столе. В начале их $7+10=17$. За каждый ход берут хотя бы один камень, значит после хода камней становится строго меньше. Эта величина целая и не опускается ниже $0$.

Целое неотрицательное число не может уменьшаться бесконечно: оно упадёт с $17$ до $0$ не более чем за $17$ шагов. А когда камней $0$, ходить нельзя: игра кончилась.

⚠️ Осторожно: Важно, что берут хотя бы один камень (строгое убывание) и что камней не бывает меньше нуля (граница снизу). Убери любое из условий, и доказательство рухнет. Всегда проверяй обе части полуинварианта.

Ответ: число камней — полуинвариант: целое, $\ge 0$, строго убывает. Значит игра закончится не позже чем за $17$ ходов.

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

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

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

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

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

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

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

• Думай про состояния и переходы между ними; задача — найти путь от старта к цели. Цепочку состояний называют процессом.
• Инвариант — величина, которая не меняется. Если у старта и цели инварианты разные, путь невозможен. Так доказывают, что чего-то сделать нельзя.
• Полуинвариант — величина, которая меняется только в одну сторону (только растёт или только убывает).
• Полуинвариант + граница (оценка снизу или сверху) = процесс обязательно закончится. Целое неотрицательное число не может убывать вечно.
• Одного «величина убывает» мало: нужна ещё граница. Проверяй обе части!
• В переливаниях записывай состояние как набор чисел; часто помогает идти от цели назад или возить «обратно» (как козу).
• На чашечных весах у каждого взвешивания три исхода: дели предметы на три группы. $k$ взвешиваний различают до $3^k$ случаев: 1 → 3, 2 → 9, 3 → 27. Это даёт оценку, сколько взвешиваний нужно (и почему меньшим не обойтись).
• В переправах найди «нарушителя» (того, кого нельзя оставить ни с кем) и оберегай его.

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

1. Как, пользуясь сосудами на 7 и 12 литров, набрать из озера ровно 1 литр воды? (Озеро — источник: сосуды можно наполнять из него и выливать обратно.)

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

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

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

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

6. Есть 27 монет, одна тяжелее. За сколько взвешиваний найти? Почему именно столько?

7. Имеется 10 мешков с монетами; в одном из них все монеты фальшивые. Настоящая монета весит 10 г, фальшивая — 9 г. Как одним взвешиванием на весах с делениями (показывают точный вес) определить мешок с фальшивыми монетами?

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

9. ⭐ Есть 12 монет, одна фальшивая, но неизвестно, легче она или тяжелее настоящих. Докажи, что за 3 взвешивания можно и найти фальшивую, и узнать, легче она или тяжелее.