Question

Шрек купил 30 бутылок: по одной каждого вида. Придя домой, он попробовал весь купленный лимонад и понял, что на бутылках перепутаны этикетки. У него есть ровно одна пустая бутылка. За одно действие он может перелить весь лимонад из полной бутылки в пустую (после этого бутылка, которая была полной, становится пустой). Шрек хочет за наименьшее число действий (переливаний) добиться, чтобы на всех бутылках этикетки соответствовали содержимому. А какого количества действий (переливаний) заведомо хватит, какие бы виды лимонада в каких бутылках ни оказались изначально? Укажите в ответе наименьшее такое число действий?

Answer 1

Ответ:

45 переливаний

Пошаговое объяснение:

уже решала я такую задачу здесь.

еще раз напишу.

будем переливать лимонад из бутылки в бутылку  в несколько этапов

этап 1

• переливаем в пустую бутылку какой-либо лимонад

• переливаем в образовавшуюся новую пустую бутылку еще из какой-нибудь бутылки
• наконец и из рабочей перелили лимонад. в этот момент какие-то бутылки   станут «правильными» и будет сделана (ПР + 1) действие и при этом ПР ≤ 2

этап 2

• исключим из процесса все ПР бутылки
• выберем любую из "неправильных" бутылок и будем снова переливать, как на первом этапе

рано или поздно во всех бутылках лимонад совпадет с этикеткой. и это произойдет за не менее чем 30 переливаний - в каждую бутылку нужный лимонад и не больше чем еще  за 15 переливаний - в пустую бутылку из "неправильной".

и тогда  за (30+15)=45 переливаний Шреку всегда  удастся  заполнить все бутылки лимонадом, соответствующим этикетке.

ответ

45 переливаний