ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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.
  Обозначим через dk "остаток" от деления ka на b  (k = 1, 2, 3, ...):  dk = ka – lkb,  0 ≤ dk < b.
  Нам достаточно доказать, что можно получить dm литров. Действительно, поскольку  dm = ma – lmb  – наименьшее неотрицательное число вида  ma + lb,  где l – целое, то, добавляя к dm еще  l + lm  порций по b литров, мы сможем получить нужное количество с  ma + lb  литров. Как получить dm литров, ясно из таблиц 2 (для m > 0)  и 3 (для  m < 0).

  Докажем теперь, что v литров можно получить только тогда, когда v = ma + lb.  Действительно, пусть после нескольких переливаний в первом сосуде оказалось  v1 = m1a + l1b  литров, а во втором – v2 = m2a + l2b  литров. (На самом деле один из сосудов либо пуст, либо полон, но мы этим не воспользуемся.) Тогда, как бы мы ни организовывали следующее переливание, число литров в каждом из сосудов будет равно  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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .