Задача о наполнении сосудов и диофантовы уравнения

Каждый с пелёнок помнит эту задачу. И в "Крепком орешке - 3" её решали, и в незавбенных "Космических рейнджерах" и не упомню где ещё. Есть два сосуда, на 3 и 5 литров, и нужно организовать в одном из них ровно 4 литра. И алгоритм решения тоже тайны не составляет.

Например, такой.

Алгоритм - это вещь, конечно, хорошая, но не отвечающая на некоторые вопросы. В частности, всегда ли задача имеет решение? Скажем, если взять ёмкости 6 и 4 литра, можно ли этим способом получить 3 литра?

Чтобы разобраться в вопросе, немного изменим алгоритм. Будем не выливать воду, чтобы освободить сосуд, а добавлять новый пустой того же объёма. Тогда процедуру решения задачи можно проиллюстрировать следующим образом:

Решение задачи при вспомогательных 5 и 3-литровых сосудах и целевом объёме 4 литра

Как видим, ничего принципиально не поменялось. Но зато появилась возможность построить математическую модель задачи:

Всё то же, но с числами.

У нас получилось, что три наполнения меньшего сосуда и одно наполнение большего удовлетворяют уравнению очень знакомого вида:

Ax - By = C

Это, как не трудно убедиться, самое обычное линейное диофантово уравнение (с точностью до замены y' = -y). А существование решения этого уравнения в целых числах зависит от того, является ли наибольший общий делитель коэффициентов A и B заодно и делителем числа С из правой части уравнения.

Таким образом, с ёмкостями 6 и 4 литра получить 3 литра не удастся (НОД(4, 6) = 2 - не является делителем тройки). А вот, например, при помощи 7 и 3 литра получить 4 литра - вполне, пусть и не самым коротким путём:

Да-да, я знаю, что тут гораздо проще сначала наполнить большую ёмкость, а затем перелить излишек в меньшую.

Вышеприведенная иллюстрация показывает, что алгоритм, в котором наполняется сначала меньший сосуд, не всегда оказывается оптимальным. Можно рассмотреть ситуацию, когда всегда наполняется только больший сосуд, а потом переливается в меньший. Этот случай тоже приводит к линейному диофантову уравнению с точностью до перемены знаков:

Результат алгоритма с переливанием воды из большего сосуда в меньший.

Очевидно, количество усилий, необходимых для получения результата с помощью того или иного алгоритма, пропорционально суммарному количеству наполнений/выливаний сосудов, так что если требуется найти оптимальный порядок действий, придется рассмотреть решения обоих уравнений:

Ax - By = C и By - Ax = C

и выбрать вариант с минимальной суммой x + y.