Существует тип задач, которые встречаются на олимпиадах, а иногда — на экзаменах. Вот одна из задач такого рода.
Дано 3 сосуда. Первый, обозначим его А, объемом 8 литров вначале полностью заполнен водой. Другие два, пятилитровый (Б) и трехлитровый (В),— пустые. Требуется последовательными переливаниями воды из одного сосуда в другой добиться, чтобы в 5-литровом остался 1 литр воды, а в 3-литровом — 3 литра.
Подобную задачу мне пришлось однажды решать при поступлении в математическую школу. Найденное решение показано в таблице:



Каждая строчка показывает, сколько литров воды находится в каждом из сосудов А, Б, В на данном шаге. Переход от одной строчки к другой соответствует одному переливанию. Например, от начального состояния 0 к состоянию 1 переход получается переливом воды из сосуда А в сосуд В до полного его заполнения. Следующий шаг состоит в переливании воды из В в Б и т. д. до искомого состояния 7.

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



Диаграмму широко используют для отображения сплавов, состоящих из трех компонентов. С каждой из высот отождествляется весовой процент данного компонента, а большая высота соответственно принимается равной 100%. Тогда любому составу сплава соответствует ровно одна точка внутри треугольника. Каждой вершине и противолежащему основанию соответствует один из компонентов, причем отсчет ведется от основания к вершине, а для удобства отсчета треугольник разбивают прямыми, параллельными основаниям.



Точке К соответствует такой состав: меди — 60%, никеля — 20%, железа — 20%. Это так называемый сплав кунифе — материал, используемый для изготовления постоянных магнитов.
Когда можно использовать диаграмму Гиббса—Розебума? Очевидно, тогда, когда сохраняется сумма каких-либо 3 величин. Но ведь и в нашей задаче, как бы мы ни переливали воду, ее общее количество не меняется. Значит, каждому конкретному моменту после переливания соответствует точка на диаграмме. Например, в нашей задаче начальному состоянию сосудов на диаграмме, которую здесь нужно разбить на восемь частей, отвечает вершина А (не забывайте, что отсчет необходимо вести от оснований), а конечному состоянию — точка, обозначенная 0.



Точки на диаграмме можно характеризовать их координатами, которые мы будем записывать в виде (а, б, в), где а, б и в — расстояния от соответствующих оснований, лежащих против вершин А, Б, В. С другой стороны, а, б, в есть просто количество воды в литрах в каждом из сосудов А, Б, В в данный момент. Согласно такой записи, начальная точка А имеет координаты (8, 0, 0), а конечная О — (4, I, 3). Что нужно сделать дальше? Прежде всего учесть, что объемы сосудов Б и В меньше 8 литров. Так как объем сосуда Б — 5 л, то попасть в область диаграммы, лежащую справа от отрезка А'В', невозможно. Запрещена для нас и область диаграммы выше отрезка Б'А', поскольку в сосуд В больше 3 литров воды не налить.



Теперь определилась та часть диаграммы, где мы можем находиться. Это параллелограмм со сторонами в 5 и 3 л. В дальнейшем необходимо найти путь, соединяющий начальную точку А с конечной точкой О. Для этого остается только определить, как можно «ходить» по нашей диаграмме. Во-первых, двигаться можно только по тем прямым, которыми она разбита, так как при переливании используются только два сосуда, а объем воды в третьем при этом не меняется. Значит, каждому переливанию соответствует движение, параллельное одному из оснований. Во-вторых, ясно, что перемещения по диаграмме следует делать только от одного ограничения к другому ограничению. Это означает, что на каждом шаге необходимо переливать воду до тех пор, пока либо один из сосудов не опорожнится, либо другой не наполнится доверху.

Таблица показывает, что правило «от ограничения к ограничению» неукоснительно выполняется в нашем решении задачи: в каждой строчке таблицы обязательно фигурирует по крайней мере один пустой или заполненный доверху сосуд.
Теперь, когда все приготовления закончены, можно пускаться в путь. Из начальной точки А с координатами (8, 0, 0) мы можем двигаться либо по отрезку АБ до точки Б', либо по отрезку АВ до точки В'. Рассмотрим пока первый путь.
Итак, из точки А мы перешли в точку Б'. Это соответствует переливанию воды из сосуда А в сосуд В до полного заполнения последнего. Запишем координаты этой точки— (5, 0, 3). Дальше мы можем двигаться по отрезку Б'А' до точки А' или по прямой, ведущей внутрь параллелограмма. Если мы выберем первую возможность, то из А' мы можем далее двинуться только до точки В'. Но В' достигается сразу из начальной точки А, при движении вторым путем, который мы пока не рассматриваем. Значит,.наиболее целесообразно из Б' двигаться внутрь параллелограмма до отрезка АВ'. Запишем координаты достигнутой при этом точки — (5, 3, 0). Из нее, в свою очередь, мы можем попасть либо в А, либо в В', что не имеет смысла, или вновь двигаться внутрь параллелограмма до линии Б'А'. Из достигнутой точки — (2, 3, 3) опять же целесообразно двигаться только внутрь, чтобы избежать повторения.



Легко заметить, что после того, как мы попали внутрь параллелограмма, наш путь напоминает путь луча света между зеркалами или путь бильярдного шара. Его легко проследить дальше, не забывайте при этом только записывать координаты каждого нового достигнутого состояния. После еще нескольких отражений луч упрется в искомую точку О—(4, 1, 3). Если мы теперь сравним наши записи координат точек с таблицей 1, то отметим полное их совпадение.
Таким образом, задача о переливании воды оказалась эквивалентной задаче о движении луча в области диаграммы, определяемой ограничениями на объемы сосудов. И из задачи на сообразительность она сразу стала совершенно тривиальной. Нам даже не нужно строить исходный треугольник, достаточно сразу построить параллелограмм со сторонами, равными объемам сосудов Б и В, разбить его сеткой прямых с делением в 1 л, несколько раз отразить луч, и решение готово.
Этим, однако, не исчерпываются достоинства такого подхода. Найдя удобную, наглядную схему, можно подробно ее изучить. Помните второй путь из точки А в В'; из В' ведь тоже можно попасть внутрь параллелограмма. Проследив этот путь, вы быстро найдете второе решение. Оно хуже первого: здесь требуется на одно переливание больше. А то, что решений может быть два, видно, в частности, из того, что в искомую точку О ведут два отрезка.
Кроме этого, интересно выяснить и другой вопрос: какие точки могут быть выбраны конечными? Очевидно, что в качестве конечных точек не имеет смысла брать вершины параллелограмма: они достигаются максимум двумя переливаниями. Не годятся для этого и все точки, лежащие внутри параллелограмма. Они в принципе недостижимы, так как мы можем двигаться от ограничения к ограничению. Остаются 12 точек, лежащих на сторонах параллелограмма. Но все ли они достижимы? Чтобы проверить это, продолжим наше решение дольше точки О, отражая луч от сторон параллелограмма.
В результате получим картину, приведенную на рисунке. Она является, по существу, объединением первого и второго решений, поэтому, выйдя из точки А, мы после 15 переливаний снова вернемся в эту же точку. Причем попутно мы побываем во всех точках, лежащих на сторонах параллелограмма. Следовательно, любая из них может быть выбрана в качестве конечной. Становится ясно также, что каждая из них достижима ровно двумя путями. Причем, если в одном из решений требуется N переливаний, то в другом необходимо (15—N). Например, конечное состояние — (3, 2, 3) достигается одним путем за 2 переливания, а другим — за 13.



Для большей полноты картины рассмотрим еще одну задачу с объемами сосудов А, Б и В соответственно 9, 6 и 3 литров. Проследив путь луча из начальной точки А в любом из направлений (Б' или В'), мы обнаружим очень простой замкнутый цикл, включающий только две точки, которые лежат на ограничениях: (6, 3, 0) и (3, 3, 3,). Очевидно, что в новой задаче только эти два состояния можно выбрать в качестве конечных.



Но почему в качестве начальной точки мы всякий раз выбираем точку А? Простая логика подсказывает, что начальной точкой может быть любой узел параллелограмма, в том числе и лежащие внутри его. Можно проверить, например, что из начальной точки (3, 5, 1) (она обведена кружком на рис. 8) теперь вновь достижимы все без исключения точки на ограничениях.
Итак, в задаче о переливании воды с помощью 3 сосудов для нас не осталось почти никаких тайн. Мы легко решим теперь любую даже очень сложную задачу подобного рода и, более того, сможем сами придумать такую задачу. А если сосудов четыре? Логично идти тем же путем, что и прежде. И действительно, существует фигура, сумма 4 высот, которой, опущенных из любой внутренней точки на ее основания, сохраняется — это тетраэдр. Вместо параллелограмма теперь придется построить параллелепипед. И вряд ли можно в этом случае рекомендовать геометрическое решение как более простое.

Автор: преподаватель Томского политехнического института В.Бир.
Опубликовано: «Наука и жизнь» №12, 1990 г.