Мистер фокс купил 40 банок различного варенья. он все попробовал и обнаружил, что надписи на банках перепутаны, хотя набор надписей соответствует набору купленных вареньев. дома у мистера фокса есть пустая банка такого же объема. за одну операцию мистер фокс переливает варенье из одной банки в другую (пустую). за какое наименьшее число операций мистер фокс наверняка сможет правильно расположить варенье по банкам?
Оценка сверху:
Докажем, что за 60 действий можно разлить варенье правильным образом. Возьмём любую банку a₁. Если в ней уже находится правильное варенье, уберём её в шкаф. В противном случае возьмём банку a₂, в которой находится правильное варенье из банки a₁, банку a₃, в которой находится правильное варенье из банки a₂ и так далее до банки aₙ, в которой содержится правильное варенье из банки a₁. Перельём варенье a₁ в пустую банку (одно действие), перельём варенье "по циклу" (n-1 действие), перельём варенье из изначально пустой банки в банку a₁. Всего на n банок требуется n+1 действие, причём n > 1, следовательно, потребуется не более 60 действий.
Оценка снизу:
Пусть для любой пары банок 2k - 1 и 2k варенье из банки 2k налито в банку 2k - 1, а варенье из банки 2k - 1 налито в банку 2k. Все банки можно разбить на 20 пар, в каждой из которых нужно поменять варения местами. Пусть сделано не более 59 действий, тогда найдётся пара банок, с вареньями из которой было проведено не более 2 действий. Значит, эти два действия - обмен вареньями из банок. Рассмотрим первое совершённое из них. Оно переливает варение из одной банки пары в другую, но так как там уже есть варенье, данное действие невозможно. Противоречие. Значит, 59 действий не хватит.
ответ: 60 действий.