Взвешивания и количество информации

Покажем, что Петя сможет определить вес одной гири, даже если у него 8000 гирь. Положим

______________________________________________________________________________________________________________________________________________________

Лемма. Для любых гирь Петя может найти две гири, для которых он знает их суммарный вес.

Доказательство. Пусть Петя положит в прибор по очереди все возможные наборы из 10 гирь из наших Заметим, что каждое показание прибора — это вес какой-то из пар гирь (будем говорить, что это показание использует эту пару). В то же время, Петя получит показаний. Значит, одна из пар будет использована хотя бы

раз.

Иначе говоря, найдутся измерений таких, что (1) в них прибор показывает один и тот же вес и (2) во всех десятках, использованных в этих испытаниях, есть две общих гири и Мы покажем, что при выполнении условий (1) и (2) суммарный вес и обязательно равен то есть вес этой пары Петя и сможет определить по показаниям прибора. Назовём десятки, использованные в этих измерениях, нужными.

Предположим противное: сумма весов и не равна Рассмотрим все пары из гирь, суммы весов в которых равны (назовём эти пары хорошими). Поскольку веса всех гирь различны, хорошие пары не пересекаются; в частности, их не больше, чем При этом в каждой нужной десятке есть не только гири и но и хотя бы одна хорошая пара. Оценим теперь общее количество нужных десяток.

Пусть в нужной десятке хорошая пара не содержит ни ни Любую такую десятку можно получить, добавив к гирей и хорошую пару (не более чем способами), а затем дополнив шестью из оставшихся гирь. Итого, количество таких десятков не больше, чем

Во всех остальных нужных десятках хорошая пара содержит либо либо Если есть хорошая пара, содержащая то для получения нужной десятки, содержащей эту пару, её надо дополнить гирей и ещё семью гирами из оставшихся Итого, таких нужных десяток не больше Аналогично, нужных десяток, содержащих хорошую пару с гирей тоже не больше

Итого, получаем

Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Завершим решение задачи. Построим следующий граф. Сопоставим каждой гире вершину. Среди каждых гирь найдём одну пару с известной суммой; две соответствующих вершины соединим ребром. Если в этом графе нет нечётных циклов, то, как известно, его вершины можно раскрасить в два цвета так, чтобы каждое ребро соединяло вершины разных цветов. Но тогда вершины одного цвета не меньше и потому среди них мы провели ребро; противоречие.

Значит, в полученном графе есть цикл …, и Петя знает суммарные веса всех пар соседних гирь в этом цикле. Взяв полусумму всех этих весов, Петя узнает суммарный вес всех гирь цикла. Вычтя из него

он узнает вес гири