У царя Гиерона есть 11 металлических слитков, неразличимых на вид; царь знает, что их веса (в некотором порядке) равны 1, 2, ..., 11 кг. Ещё у него есть мешок, который порвётся, если в него положить больше 11 кг. Архимед узнал веса всех слитков и хочет доказать Гиерону, что первый слиток имеет вес 1 кг. За один шаг он может загрузить несколько слитков в мешок и продемонстрировать Гиерону, что мешок не порвался (рвать мешок нельзя!). За какое наименьшее число загрузок мешка Архимед может добиться требуемого?
Это задача 9.4 с Всероссийской олимпиады по математике 2016 года. Авторы задачи - И.И. Богданов, К.А. Кноп.
Прежде чем мы докажем, что за две загрузки Архимед справится, исторический комментарий.
Гиерон II - царь Сиракуз, живший в III веке до нашей эры. По легенде он поручил Архимеду выяснить, сделана ли его корона из чистого золота или ювелир подмешал много количество серебра. Решение этой задачи и позволило учёному, которого Плутарх называет дальним родственником царя, открыть один из основных законов гидростатики.
Сначала Архимед положит в мешок слитки с весами 1, 2, 3 и 5 кг, а потом – слитки с весами 1, 4 и 6 кг. В обоих случаях мешок не порвётся, так как сумма весов будет ровно 11 кг.
Докажем, что это могло произойти только в том случае, если дважды был использован слиток веса 1 кг.
Положить четыре слитка так, чтобы мешок не порвался, можно только двумя способами: 1+2+3+4 и 1+2+3+5. Царь видит, что убрали три слитка и добавили два из оставшихся. В первом случае минимальная масса двух из оставшихся слитков равна 5+6=11. И, если в мешке будет ещё и третий слиток, он порвётся. Значит, этот случай невозможен. Минимальная сумма двух из оставшихся слитков во втором случае - 4+6=10. Но чтобы мешок не порвался, масса третьего слитка должна быть равна 1 кг!
Осталось объяснить, почему не хватит одной загрузки. Понятно, что если положить в мешок один слиток, то ничего сказать нельзя.
Если слитков в мешке хотя бы два и среди них есть 1-килограммовый, то царь не может понять какой слиток сколько весит.
Если же в мешке хотя бы два слитка и среди них нет слитка в 1 кг, то для царя ничего не поменяется, если какой-то из слитков в мешке заменить на слиток в 1 кг.
