У Пети есть 10 000 гирь, среди них нет двух гирь равного веса. Также у него есть чудо-прибор: если положить в него 10 гирь, он сообщит сумму весов каких-то двух из них (при этом неизвестно, каких именно). Докажите, что Петя может использовать чудо-прибор так, чтобы через некоторое время указать на одну из гирь и точно назвать ещё вес. (В чудо-прибор нельзя класть другое количество гирь.)
1 Ответ
Решение.
Покажем, что Петя сможет определить вес одной гири, даже если у него 8 000 гирь. Положим n = 4 000.
Лемма. Для любых n гирь Петя может найти две гири, для которых он знает их суммарный вес.
Иначе говоря, найдутся D измерений таких, что (1) в них прибор показывает один и тот же вес S, и (2) во всех десятках, использованных в этих испытаниях, есть две общих гири a и b. Мы покажем, что при выполнении условий (1) и (2) суммарный вес a и b обязательно равен S, то есть вес этой пары Петя и сможет определить по показаниям прибора. Назовём десятки гирь, участвовавшие в этих D измерениях, нужными.
Предположим противное: сумма весов a и b не равна S. Рассмотрим все пары из n гирь, суммарные веса в которых равно S (назовём эти пары хорошими). Поскольку веса всех гирь различны, хорошие пары не пересекаются; в частности, их не больше, чем n/2. При этом в каждой нужной десятке есть не только гири a и b, но и хотя бы одна хорошая пара. Оценим теперь общее количество нужных десяток.
Пусть в нужной десятке хорошая пара не содержит ни a, ни b. Любую такую десятку можно получить, добавив к гирям a и b хорошую пару (не более чем (n − 2)/2 способами), а затем дополнив шестью из оставшихся n − 4 гирь. Итого, количество
