|
|
 |
Условие
В три сосуда налито по целому числу литров воды. В любой сосуд разрешено перелить столько воды, сколько в нём уже содержится, из любого другого сосуда. Докажите, что несколькими такими переливаниями можно освободить один из сосудов. (Сосуды достаточно велики: каждый может вместить всю воду.)Решение
Пусть в первом сосуде a литров воды, во втором – b литров, в третьем – c литров, и a ≤ b ≤ c .Разберем сначала случай, когда a = 1. Если доливать воду только в первый сосуд, то при первом переливании в него нужно будет долить 1 литр воды, при втором – два литра, при третьем – четыре литра, вообще при i-м переливании 2i-1 литров.
Разделим теперь, разумеется, чисто условно, воду во втором сосуде на порции:
2i0, 2i1, ... , 2ik, где i0 < i1 < ... < ik-1 < ik.
(Для этого найдем такое ik , что 2ik ≤ b, а 2ik+1 > b ,
тогда b=2ik+b1, где b1<2ik ; для него, в свою очередь, найдем
2ik-1 и т.д.)
Если i0=0 , i1=1 , i2=2 , ... , ik=k , то третий сосуд нам не
понадобится. Начнем переливать из второго сосуда в первый. После первого
переливания в первом сосуде станет два литра, а во втором 2+22+23+...+2k
литров, после второго соответственно 22 и 22+23+...+2k , после
третьего – 23 и 23+...+2k , после k-го – 2k и 2k и после
(k+1)-го – 2k+1 и 0 .
Если же некоторые степени двойки, меньшие 2ik , среди "порций"
отсутствуют, то недостающие порции выделим в третьем сосуде (воды в нем для
этого хватит; действительно, нам заведомо хватит 1+2+22+23+...+2ik-1=
2ik-1 литров воды, это меньше b литров, а b , в свою очередь, меньше c ).
Переливать теперь будем так: каждый раз будем брать тот сосуд, в котором выделена
соответствующая порция. После (ik+1)-го переливания второй сосуд опустеет.
Общий случай (a ≠ 1) фактически ничуть несложнее. Представим b и c так:
b=b1 a+b2 , c=c1 a+c2 , где b1, b2, c1, c2 – натуральные числа,
a b2<a , c2<a (такое представление единственно). Если мы забудем теперь
про "лишние" b2 и c2 литров, и объявим a литров новой единицей объема,
то поскольку b1 ≤ c1 , мы сможем устроить переливание так, чтобы вылить
из второго сосуда b1 a литров. После этого в нем останется b2 литров,
причем целое число b2 меньше a. Итак, нам удалось от сосудов с a ≤
b ≤ c литрами воды перейти к сосудам с a' ≤ b' ≤ c' литрами воды,
причем a > a' . Повторяя нашу процедуру, мы будем последовательно получать
сосуды со все меньшим и меньшим количеством воды: a>a'>a''>... Поскольку,
однако, все эти количества выражаются целым числом литров, мы через конечное
число шагов получим пустой сосуд.
