Мистер Фокс купил 40 банок различного варенья. Он все попробовал и обнаружил, что надписи...

0 голосов
40 просмотров

Мистер Фокс купил 40 банок различного варенья. Он все попробовал и обнаружил, что надписи на банках перепутаны, хотя набор надписей соответствует набору купленных вареньев. Дома у мистера Фокса есть пустая банка такого же объема. За одну операцию мистер Фокс переливает варенье из одной банки в другую (пустую). За какое наименьшее число операций мистер Фокс наверняка сможет правильно расположить варенье по банкам?


Математика (16 баллов) | 40 просмотров
Дан 1 ответ
0 голосов

Оценка сверху:

Докажем, что за 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 действий.

(7.3k баллов)