Задача 73664

Темы:    [ Уравнения в целых числах ] [ Алгоритм Евклида ] [ Принцип крайнего ]

Сложность: 4+ Классы: 8,9,10

Условие

Автор: Ушаков В. Г.

  а) В ведро налили 12 литров молока. Пользуясь лишь сосудами в 5 и 7 л, разделите молоко на две равные части.
  б) Решите общую задачу: при каких a и b можно разделить пополам  a + b  литров молока, пользуясь лишь сосудами в a литров, b литров и  a + b  литров?
За одно переливание из одного сосуда в другой можно вылить всё, что там есть, или долить второй сосуд до верха.

Решение

  а) См. таблицу:

  б) Пусть  a ≥ b.  Назовём сосуд ёмкостью в  a + b  литров резервуаром, сосуд ёмкостью в a литров – первым сосудом, а сосуд ёмкостью в b литров – вторым сосудом. Докажем, что c литров можно получить тогда и только тогда, когда  c = ma + lb,  где m и l – целые числа,  0 ≤ c ≤ a .  (Если a и b – целые числа, то c литров можно получить тогда и только тогда, когда  0 ≤ c ≤ a  и c делится на  НОД(a, b)  – см. задачу 69489.
  Обозначим через d_k "остаток" от деления ka на b  (k = 1, 2, 3, ...):  d_k = ka – l_kb,  0 ≤ d_k < b.
  Нам достаточно доказать, что можно получить d_m литров. Действительно, поскольку  d_m = ma – l_mb  – наименьшее неотрицательное число вида  ma + lb,  где l – целое, то, добавляя к d_m еще  l + l_m  порций по b литров, мы сможем получить нужное количество с  ma + lb  литров. Как получить d_m литров, ясно из таблиц 2 (для m > 0)  и 3 (для  m < 0).

  Докажем теперь, что v литров можно получить только тогда, когда v = ma + lb.  Действительно, пусть после нескольких переливаний в первом сосуде оказалось  v₁ = m₁a + l₁b  литров, а во втором – v₂ = m₂a + l₂b  литров. (На самом деле один из сосудов либо пуст, либо полон, но мы этим не воспользуемся.) Тогда, как бы мы ни организовывали следующее переливание, число литров в каждом из сосудов будет равно  ma + lb.  В случае, когда используется резервуар, это очевидно, остальные случаи собраны в таблице 4.

  Из доказанного следует, что с помощью переливаний можно получить  ½ (a + b)  литров тогда и только тогда, когда  ½ (a + b) = ma + lb,  откуда
(2m – 1)a + (2l – 1)b = 0,  или  

Ответ

Если ^a/_b рационально, причём числитель и знаменатель соответствующей несократимой дроби нечётны.

Замечания

  1. Если a и b – целые числа, то решение можно упростить; например, не нужно отдельно рассматривать случаи  m > 0  и  m < 0.

  2. Таблицы, указывающие порядок переливаний, удобно интерпретировать геометрически.

  Рис. 1. Ситуации, когда в первом сосуде x литров, а во втором – y литров, сопоставляется точка с координатами  (x, y),  а последовательность переливаний изображена красными и голубыми стрелочками – красные означают переливания из одного сосуда в другой, а голубые – переливания с использованием резервуара. Рис. слева соответствует табл. 1 и 2, рис. справа – табл. 3.

  Рис. 2. Если разрезать изображенную здесь плоскость на прямоугольники a×b (по чёрным линиям) и сложить стопкой все прямоугольники, содержащие отрезки красного луча, идущего вправо вниз (или влево вверх), то получится правый (левый) рис. 1 (голубые отрезки возникают в местах разрезов).

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1972
выпуск
Номер	2
Задача
Номер	М129