Связность и связные подграфы (клики)

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

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

(b) Для того, чтобы гиря была одной из двух самых лёгких, необходимо и достаточно, чтобы она была легче каких-то восьми других гирь. Из оценки прошлого пункта следует, что для того, чтобы доказать, что какая-то гиря легче восьми других, потребуется хотя бы взвешиваний.

Теперь приведём пример. Будем реализовывать алгоритм из примера в первом пункте до тех пор, пока на весах не побывают девять гирь. Нетрудно понять, что в этом алгоритме после -го взвешивания мы знаем, какая гиря самая лёгкая из гирь, побывавших на весах. Тогда через восемь взвешиваний мы получим гирю, которая легче каких-то восьми других, что и требовалось.