Question

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

Answer 1

Ответ:

30

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

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

этап 1

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

этап 2

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

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

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

ответ

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

Answer 2

Для решения этой задачи нужно определить, какие виды лимонада оказались в каждой из бутылок. После этого мы сможем определить, сколько действий потребуется Шреку для того, чтобы расставить этикетки правильно.

Предположим, что Шрек пронумеровал каждую бутылку от 1 до 20. Затем он может начать процесс переливания лимонада следующим образом:

1. Шрек переливает содержимое бутылки № 1 в пустую бутылку. 2. Шрек переливает содержимое бутылки № 2 в пустую бутылку. 3. Шрек переливает содержимое бутылки № 3 в пустую бутылку. 4. И так далее, пока он не доберется до бутылки № 20.

После этого Шрек должен проверить содержимое каждой бутылки и поменять этикетки на правильные. Если бутылка пустая, то на нее нужно поставить этикетку "Нет лимонада". Если бутылка содержит лимонад, то на нее нужно поставить соответствующую этикетку.

Таким образом, для того чтобы правильно расставить этикетки на всех бутылках, Шреку потребуется 20 действий (переливаний). Это наименьшее возможное количество действий, так как каждая бутылка должна быть перелита минимум один раз.

Ответ: наименьшее количество действий, достаточное для правильного распределения этикеток на всех бутылках, равно 20.