Задача 115712
|
|
 |
Условие
Было 8 грузиков массами 1 , 2 , .. , 8 г. Один из них потерялся, а остальные выложили в ряд по возрастанию массы. Есть весы с лампочкой, при помощи которых можно проверить, имеют ли две группы грузиков одинаковую массу. Как за 3 проверки определить, какой именно грузик потерялся?Решение
Одна из возможных последовательностей взвешиваний приведена на схеме. В прямоугольниках указаны оставшиеся к данному моменту варианты для массы потеряной гирьки, в ромбах — взвешивания. В описании взвешиваний используются номера оставшихся грузиков — от 1 до 7.Заметим, что если потерян грузик массой n г, то гирьки c номерами, меньшими n , весят столько грамм, каков их номер, а грузики с номером n и больше весят на 1 г больше, чем их номер.
Теперь нетрудно проверить приведенную схему. Ограничимся такой проверкой для первого взвешивания. Имеется 4 случая: если потерянный грузик был тяжелее 5 г, то весы останутся в равновесии ( 2+3=5 ); если был потерян грузик массой 4 г или 5 г, то равновесия не будет ( 2+3
Комментарии:
1. Придумать правильную последовательность взвешиваний может помочь следующее соображение. Изначально для потерянного грузика имеется 8 вариантов, и 3 взвешивания могут иметь как раз 23=8 исходов. Значит, каждое взвешивание должно сужать количество вариантов для потерянной гирьки вдвое. (В самом деле, пусть, например, один из исходов первого взвешивания возможен не в 4 , а в 5 случаях. Тогда за оставшиеся 2 взвешивания нужно выбрать один грузик из 5 , а эти взвешивания могут иметь только 22=4 различных исхода.)
2. Существуют и ``неинтерактивные'' решения — в которых следующие взвешивания не зависят от результатов предыдущих, а определены заранее. Например, 2+4?=6 , 1+2+4+7?=3+5+6 , 1+5+6?=2+3+7 .
