Назад
Задача

  а) В ведро налили 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)  – см. задачу 169489.

  Обозначим через 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 рационально, причём числитель и знаменатель соответствующей несократимой дроби нечётны.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет