|
|
 |
Условие
У царя Гиерона есть 11 металлических слитков, неразличимых на вид; царь знает, что их веса (в некотором порядке) равны 1, 2, ..., 11 кг. Ещё у него есть мешок, который порвётся, если в него положить больше 11 кг. Архимед узнал веса всех слитков и хочет доказать Гиерону, что первый слиток имеет
вес 1 кг. За один шаг он может загрузить несколько слитков в мешок и продемонстрировать Гиерону, что мешок не порвался (рвать мешок нельзя!). За какое наименьшее число загрузок мешка Архимед может добиться требуемого?
Решение
Пусть Архимед сначала положит в мешок слитки с весами 1, 2, 3 и 5 кг, а потом – слитки с весами 1, 4 и 6 кг. В обоих случаях мешок не порвётся.
Докажем, что это могло произойти только в том случае, если дважды был использован слиток веса 1 кг. Действительно, если бы Архимед в эти два раза
вместо слитков с весами 1, ..., 6 кг использовал соответственно слитки с весами w1, ..., w6 кг, то эти веса удовлетворяли
бы системе неравенств
w1 + w2 + w3 + w5 ≤ 11, w1 + w4 + w6 ≤ 11. Складывая, получаем w1 + (w1 + w2 + ... + w6) ≤ 22. В скобках стоит сумма шести различных натуральных чисел, она не меньше 1 + 2 + ... + 6 = 21. Отсюда следует, что w1 ≤ 22 – 21 = 1. Значит, w1 = 1, то есть слиток веса 1 кг однозначно определён.
Осталось показать, что одной загрузки недостаточно. Если Архимед загрузит один слиток, то мешок не порвётся в любом случае, то есть никакой
слиток идентифицировать не удастся. Пусть Архимед загрузит больше одного слитка, и мешок не порвётся. Если слиток в 1 кг не загружен в мешок, то при замене им любого слитка из мешка результат не изменится; значит, в этом случае Гиерон даже не сможет понять, находится ли этот слиток в мешке.
Если же искомый слиток в мешке, то Гиерон не сможет понять, какой из (хотя бы двух) загруженных слитков – требуемый.
Ответ
За две загрузки.
