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

Эта задача связана с перестановками. У нас есть 30 бутылок, и одна из них пустая. Наша цель - расставить этикетки на бутылках так, чтобы они соответствовали содержимому, используя только переливания в пустую бутылку.

Представим, что у нас есть бутылки с номерами от 1 до 30, где 30-я бутылка пустая. Мы можем перелить лимонад из любой бутылки в пустую. В худшем случае, нам потребуется перелить содержимое каждой неправильно маркированной бутылки.

Для начала, мы должны найти бутылку, содержимое которой должно быть в пустой бутылке (то есть, бутылку с номером 30). Если такой бутылки нет, значит, все бутылки уже на своих местах, кроме, возможно, содержимого пустой бутылки.

Рассмотрим худший случай: все 29 бутылок заполнены неправильно. Чтобы расставить все по местам, нам потребуется выполнить 29 переливаний.

Например, если у нас три бутылки (A, B, C), где C - пустая:

• Допустим, A содержит содержимое B, B содержит содержимое C, C должна содержать содержимое A.
• Переливаем B в C (C становится B, B пустой).
• Переливаем A в B (B становится A, A пустой).
• Переливаем C (которое B) в A (A становится B, C пустой).

Таким образом, нам понадобилось бы 3 переливания, чтобы все расставить по местам.

В нашем случае с 30 бутылками и одной пустой, нам понадобится максимум 29 переливаний.