Достижимость объёма в задаче Водолей
Достижимость объёма означает, что существует последовательность команд исполнителя Водолей, после которой в одном из сосудов окажется ровно заданный объём жидкости. Для сосудов вместимостью \(a\) и \(b\) это определяется их наибольшим общим делителем.
Критерий достижимости
Если сосуды имеют вместимости \(a\) и \(b\), то объём \(v\) достижим тогда и только тогда, когда выполнены два условия: \(v\) не больше большей вместимости сосудов и \(v\) делится на \(\operatorname{НОД}(a,b)\). Это и есть признак достижимости объёма.
Первое условие очевидно: в одном сосуде нельзя получить больше его вместимости. Второе означает, что все возможные объёмы образуются шагами, кратными \(\operatorname{НОД}(a,b)\). Если хотя бы одно условие нарушено, объём получить нельзя; подробнее это рассматривается на странице «Невозможность получения объёма».
Для сосудов на \(6\) и \(9\) единиц \(\operatorname{НОД}(6,9)=3\). Поэтому объёмы \(3\), \(6\) и \(9\) достижимы, а объём \(4\) — нет: он не делится на \(3\). Например, чтобы получить \(3\), наполните сосуд на 9 единиц и перелейте жидкость в сосуд на 6 единиц: после его заполнения останется \(3\) единицы.
Критерий отвечает только на вопрос, можно ли получить объём. Он не показывает, сколько переливаний потребуется. Для поиска наименьшего числа команд используется отдельное понятие минимального числа переливаний.
Сосуды имеют вместимости 8 и 12 единиц. Достижим ли объём 6?
Главное
- Объём \(v\) достижим, если его можно получить в одном сосуде последовательностью разрешённых команд.
- Условия: \(v\le\max(a,b)\) и \(\operatorname{НОД}(a,b)\) делит \(v\).
- Достижимость не означает минимальное число переливаний.