ВсОШ 2023, 9 класс, задача 8
( баллов) У Пети есть гирь, среди них нет двух гирь равного веса. Также у него есть чудо-прибор: если положить в него гирь, он сообщит сумму весов каких-то двух из них (при этом неизвестно, каких именно). Докажите, что Петя может использовать чудо-прибор так, чтобы через некоторое время указать на одну из гирь и точно назвать её вес. (В чудо-прибор нельзя класть другое количество гирь.) (С. Берлов, Т. Коротченко)
Ответ
Решение. Покажем, что Петя сможет определить вес одной гири, даже если у него гирь. Положим .
Лемма. Для любых гирь Петя может найти две гири, для которых он знает их суммарный вес.
Доказательство. Пусть Петя положит в прибор по очереди все возможные наборы из гирь из наших . Заметим, что каждое показание прибора - это вес какой-то из пар гирь (будем говорить, что это показание использует эту пару). В то же время, Петя получит показаний. Значит, одна из пар будет использована хотя бы
раз.
Иначе говоря, найдутся измерений таких, что (1) в них прибор показывает один и тот же вес , и (2) во всех десятках, использованных в этих испытаниях, есть две общих гири и . Мы покажем, что при выполнении условий (1) и (2) суммарный вес и обязательно равен , то есть вес этой пары Петя и сможет определить по показаниям прибора. Назовём десятки гирь, участвовавшие в этих измерениях, нужными.
Предположим противное: сумма весов и не равна . Рассмотрим все пары из гирь, суммарные веса в которых равны (назовём эти пары хорошими). Поскольку веса всех гирь различны, хорошие пары не пересекаются; в частности, их не больше, чем . При этом в каждой нужной десятке есть не только гири и , но и хотя бы одна хорошая пара. Оценим теперь общее количество нужных десяток.
Пусть в нужной десятке хорошая пара не содержит ни , ни . Любую такую десятку можно получить, добавив к гирям и хорошую пару (не более чем способами), а затем дополнив шестью из оставшихся гирь. Итого, количество таких десяток не больше, чем .
Во всех остальных нужных десятках хорошая пара содержит либо , либо . Если есть хорошая пара, содержащая , то такая пара единственна. Для получения нужной десятки, содержащей эту пару, её надо дополнить гирей и ещё семью гирями из оставшихся ; итого, таких нужных десяток не больше . Аналогично, нужных десяток, содержащих хорошую пару с гирей , тоже не больше .
Итого, получаем
Противоречие.
Завершим решение задачи. Построим следующий граф. Сопоставим каждой гире вершину. Среди каждых гирь найдём одну пару с известной суммой; две соответствующих вершины соединим ребром. Если в этом графе нет нечётных циклов, то, как известно, его вершины можно раскрасить в два цвета так, чтобы каждое ребро соединяло вершины разных цветов. Но тогда вершин одного цвета не меньше , и потому среди них мы провели ребро; противоречие.
Значит, в полученном графе есть цикл , и Петя знает суммарные веса всех пар соседних гирь в этом цикле. Взяв полусумму всех этих весов, Петя узнаёт суммарный вес всех гирь цикла. Вычтя из него , он узнает вес гири .
Замечание. Оценивая чуть точнее, можно доказать лемму даже при .