Тапсырма № 15 · ОГЭ

Невозможность получения объёма

Как определить, можно ли получить нужный объём с помощью двух сосудов

2 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

Объём невозможно получить, если он не удовлетворяет ограничениям сосудов: прежде всего, не делится наибольший общий делитель их вместимостей или превышает вместимость большего сосуда. Это позволяет заранее проверить задачу исполнителя «Водолей», не перебирая все переливания.

Невозможность получения объёма — это ситуация, когда при заданных вместимостях сосудов и разрешённых переливаниях нельзя добиться того, чтобы в одном из сосудов оказалось ровно \(v\) единиц жидкости. Для двух сосудов без делений на стенках, при наличии неограниченного источника воды и возможности выливать воду, объём \(v\) достижим тогда и только тогда, когда \(v\leq\max(a,b)\) и \(v\) кратен \(\gcd(a,b)\).

Признак невозможности

Пусть вместимости сосудов равны \(a\) и \(b\). Любой получаемый объём образуется сложением и вычитанием полных вместимостей сосудов, поэтому он кратен \(d=\gcd(a,b)\). Если \(v\) не делится на \(d\), получить его нельзя. Также нельзя получить объём, который больше вместимости каждого сосуда, если требуется измерить его в одном сосуде.

\[v\text{ достижим }\Longleftrightarrow v\leq\max(a,b)\text{ и }\gcd(a,b)\mid v.\]

№

Пример

Сосуды имеют вместимости \(6\) и \(10\) литров. Их наибольший общий делитель равен \(2\). Объём \(8\) литров достижим: он не больше \(10\) и делится на \(2\). А получить ровно \(7\) литров невозможно, потому что \(7\) не делится на \(2\).

Не путайте с числом переливаний

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

Проверьте себя

Можно ли получить ровно \(5\) литров сосудами на \(8\) и \(12\) литров?

Главное за минуту

Главное

Для сосудов вместимостями \(a\) и \(b\) вычислите \(d=\gcd(a,b)\).
Если \(v\) не кратно \(d\) или больше вместимости большего сосуда, получить \(v\) невозможно.
Возможность объёма и минимальное число переливаний — разные вопросы.