Задача
В корзине лежат 13 яблок. Весы позволяют узнать суммарный вес любых двух яблок. Какое наименьшее число взвешиваний требуется, чтобы узнать общий вес всех яблок?
Решение. Покажем сначала, что 8 взвешиваний достаточно.
Возьмём три яблока массами a, b и c и взвесим их попарно:
a + b, b + c, a + c.
Сумма трёх результатов равна 2(a + b + c), поэтому общий вес этих трёх яблок известен.
Оставшиеся 10 яблок разобьём на 5 пар и взвесим каждую пару. Получаем ещё 5 взвешиваний.
Всего: 3 + 5 = 8.
Теперь докажем, что 7 взвешиваний недостаточно.
За 7 взвешиваний на весах побывают яблоки всего 14 раз. При этом каждое из 13 яблок должно быть взвешено хотя бы один раз: иначе его вес вообще никак не повлияет на результаты.
Значит, при 7 взвешиваниях одно яблоко будет взвешено дважды, а остальные 12 — по одному разу. Пусть два взвешивания с этим яблоком дали a + b и b + c.
По этим двум числам нельзя узнать сумму a + b + c. Действительно, если заменить веса на a − t, b + t, c − t, результаты обоих взвешиваний не изменятся, а сумма трёх яблок изменится.
Следовательно, 7 взвешиваний недостаточно.
Ответ: 8.