Задача 6.
В пять 15-литровых вёдер налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается утроить количество воды в любом сосуде, налив в него воду из какого-нибудь одного другого (если воды не хватает, чтобы утроить количество, то выливать из этого ведра нельзя). Какое наибольшее количество воды можно такими действиями собрать в одном ведре?
Комментарий: необязательно выливать всё содержимое ведра, то есть мы можем отмерять нужное число литров, и ведро необязательно должно стать пустым после перелива воды.
Ответ на Задачу 6.
Ответ: 12 литров.
Решение:
Покажем, как собрать в одном из вёдер 12 литров:
1, 2, 3, 4, 5 => 1, 6, 3, 4, 1 => 1, 0, 9, 4, 1 => 1, 0, 1, 12, 1
Требуется доказать, что это максимальное число (что нельзя получить больше).
Пусть максимальное число литров равно $n$ ≥ 12. Рассмотрим последнюю операцию с этим ведром (хотя бы одна операция была — иначе $n$ ≤ 5). Т.к. $n$ — максимальное число литров, то последней операцией не могли отливать из этого ведра (т.к. иначе до этого там было ещё больше), т.е. в него наливали, поэтому $n$ кратно 3. Во всех ведрах в сумме 15 литров, потому $n$ может быть 12 или 15.
Заметим, что после каждого шага есть непустое ведро, количество литров в котором кратно трём (это то ведро, в котором мы предыдущим шагом утроили количество воды). (*)
Предположим, что $n$ = 15. Тогда на предыдущем шаге было ровно два непустых ведра, в одном из которых 5, а в другом 10 литров. Но ни одно из этих чисел не кратно 3. Противоречие с (*)
Тем самым $n$ = 12, пример как получить 12 литров приведён выше.
