Вставить иллюстрации
Для решения задачи а) достаточно привести табличку (см. таблицу 1). Для того чтобы решить задачу б), поступим следующим образом. Пусть $a\ge b$. Назовём сосуд ёмкостью в $a+b$ литров резервуаром, сосуд ёмкостью в $a$ литров — первым сосудом, а сосуд ёмкостью $b$ литров — вторым сосудом. Докажем, что $c$ литров можно получить тогда и только тогда, когда $c=ma+lb$, где $m$ и $l$ — целые числа, $0\le c\le a$. Если $a$ и $b$ — целые числа, то это можно сформулировать так: $c$ литров можно получить тогда и только тогда, когда $0\le c\le a$ и $c$ делится на наибольший общий делитель $a$ и $b$ (см. статью Вагутен В. Н. Алгоритм Евклида и основная теорема арифметики, Квант, № 6, 1972). Мы решаем задачу, не предполагая, что $a$ и $b$ — целые числа; если это заранее известно, то решение можно упростить; например, не нужно отдельно рассматривать случаи $m\gt 0$ и $m\lt 0$.
Обозначим через $d_k$ остаток от деления $ka$ на $b$ ($k=1, 2, 3, \ldots$): $d_k = ka-l_kb$, $0\le d_k\lt b$.
Нам достаточно доказать, что можно получить $d_m$ литров. Действительно, поскольку $d_m=ma-l_mb$ — наименьшее неотрицательное число вида $ma+lb$, где $l$ — целое, то, добавляя к $d_m$ ещё $l+l_m$ порций по $b$ литров, мы сможем получить нужное количество $c=ma+lb$ литров. Как получить $d_m$, литров, ясно из таблицы 2 (для $m\gt 0$) и таблицы 3 (для $m\lt 0$).
Докажем теперь, что $v$ литров можно получить только тогда, когда $v=ma+lb$. Действительно, пусть после нескольких переливаний в первом сосуде оказалось $v_1=m_1a+l_1b$ литров, а во втором — $v_2=m_2a+l_2b$ литров. (На самом деле один из сосудов либо пуст, либо полон, но мы этим не воспользуемся.) Тогда, как бы мы ни организовывали следующее переливание, число литров в каждом из сосудов будет равно $m_i'a+l_i'b$. В случае, когда используется резервуар, это очевидно, остальные случаи собраны в таблице 4.
Теперь уже можно решить задачу. Из доказанного следует, что с помощью переливаний можно получить $\dfrac{a+b}{2}$ литров тогда и только тогда, когда $\dfrac{a+b}{2}=ma+lb$, откуда $(2m-1)a+(2l-1)b=0$ или $\dfrac{a}{b}=\dfrac{2l-1}{1-2m}$. Т. е. можно отыскать такое число $c$, что $a/c$ и $b/c$ — нечётные целые числа.
Оказывается, наши таблицы, указывающие порядок переливаний, удобно интерпретировать геометрически (рис. 1, 2).
Рис. 1. Ситуации, когда в первом сосуде $x$ литров, а во втором — $y$ литров, сопоставляется точка с координатами $(x,y)$, а последовательность переливаний изображена красными и голубыми стрелочками — красные означают переливания из одного сосуда в другой, а голубые — переливания с использованием резервуара. Рисунок а соответствует таблицам 1 и 2, рисунок б — таблице 3.
Рис. 2. Заметьте, что если разрезать изображенную здесь плоскость на прямоугольнике $a\times b$ (по чёрным линиям) и сложить стопкой все прямоугольники, содержащие отрезки красного луча, идущего вправо вниз (или влево вверх), то получится рисунок 1б (соответственно 1а) (голубые отрезки возникают в местах разрезов).
