Задача
В три сосуда налито по целому числу литров воды. В любой сосуд разрешено перелить столько воды, сколько в нём уже содержится, из любого другого сосуда. Докажите, что несколькими такими переливаниями можно освободить один из сосудов. (Сосуды достаточно велики: каждый может вместить всю воду.)
Решение
Пусть в первом сосуде 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''>... Поскольку, однако, все эти количества выражаются целым числом литров, мы через конечное число шагов получим пустой сосуд.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь