В лавке можно купить 40видов лимонада. Шрек купил 40 бутылок: по одной каждого вида. Придя домой, он попробовал весь купленный лимонад и понял, что на бутылках
перепутаны этикетки. У него есть ровно одна пустая бутылка. За одно действие он может
перелить весь лимонад из полной бутылки в пустую (после этого бутылка, которая была
полной, становится пустой).
Шрек хочет за наименьшее число действий (переливаний) добиться, чтобы на всех
бутылках этикетки соответствовали содержимому. А какого количества действий
(переливаний) заведомо хватит, какие бы виды лимонада в каких бутылках ни оказались
изначально? Укажите в ответе наименьшее такое число действий (переливаний).
(Переклеивать этикетки запрещено, а также нельзя что-либо на них писать.)
У нас есть 40 видов лимонада, поэтому у нас есть 40 шаров. Мы должны разместить эти шары в 40 ящиках (бутылках) таким образом, чтобы на ящиках были правильные этикетки. Однако, на данный момент этикетки на бутылках перепутаны.
У нас есть одна пустая бутылка, поэтому мы можем использовать эту бутылку как "промежуточный" ящик для переливания лимонада.
Для начала, Шрек переливает содержимое первой бутылки в пустую бутылку. Затем он переливает содержимое второй бутылки в первую пустую бутылку, и так далее. Он будет продолжать этот процесс до тех пор, пока не закончится лимонад в последней бутылке.
Теперь давайте посмотрим, что происходит с этикетками. Изначально, мы имеем 40 перепутанных этикеток на бутылках. Каждый раз, когда Шрек переливает лимонад, этикетка переходит с бутылки, из которой он переливает, на пустую бутылку.
Таким образом, после первого переливания у нас остается 39 бутылок с этикетками и одна пустая бутылка с этикеткой, которая изначально была на первой бутылке. При следующем переливании этикетка с пустой бутылки переходит на следующую бутылку и так далее.
В конце концов, после 39 переливаний мы получим, что этикетки на бутылках совпадают с содержимым.
Таким образом, наименьшее количество переливаний, необходимых Шреку, чтобы убедиться, что все этикетки соответствуют содержимому, равно 39.