Ох уж этот лимонад
В лавке можно купить 30 видов лимонада. Шрек купил 30 бутылок: по одной каждого
вида. Придя домой, он попробовал весь купленный лимонад и понял, что на бутылках
перепутаны этикетки. У него есть ровно одна пустая бутылка. За одно действие он может
была
перелить весь лимонад из полной бутылки в пустую (после этого бутылка, которая
полной, становится пустой).
Шрек хочет за наименьшее число действий (переливаний) добиться, чтобы на всех
бутылках этикетки соответствовали содержимому. А какого количества действий
(переливаний) заведомо хватит, какие бы виды Лимонада в каких бутылках ни оказались
Изначально? Укажите в ответе наименьшее такое число действий (переливаний).
(Переклеивать этикетки запрещено, а также нельзя что-либо на них писать.)
Ответы
Ответ:
чтобы лимонад совпал с этикетками, Шреку заведомо хватит 45 переливаний
Пошаговое объяснение:
будем переливать лимонад из бутылки в бутылку в несколько этапов
этап 1
ПР - это правильные бутылки
Переливаем в пустую бутылку какой-либо лимонад.
Переливаем в образовавшуюся новую пустую бутылку лимонад из еще какой-нибудь неизвестной бутылки.
Наконец и из рабочей перелили лимонад. В этот момент какие-то бутылки станут «правильными» и будет сделано (ПР + 1) действие и при этом ПР ≤ 2
этап 2
Уберем все ПР бутылки в сторону.
Выберем любую из "неправильных" бутылок и будем снова переливать, как на первом этапе
Рано или поздно во всех бутылках лимонад совпадет с этикеткой.
И это случится за не менее чем 30 переливаний - в каждую бутылку нужный лимонад и не больше чем еще за 15 переливаний - в пустую бутылку из "неправильной".
Таким образом, за (30+15)=45 переливаний Шреку всегда удастся заполнить все бутылки лимонадом, соответствующим этикетке.