Задача 110113
|
|
 |
Условие
Среди 18 деталей, выставленных в ряд, какие-то три подряд стоящие весят
по 99 г, а все остальные – по 100 г. Двумя взвешиваниями на
весах со стрелкой определите все 99-граммовые детали.
Решение
Первое решение.
Пронумеровав детали слева направо числами 1,2,..,18 , взвесим детали
с номерами 4, 5, 6, 7, 12, 13, 14, 15. Возможны четыре случая.
- Масса всех взвешенных деталей равна 800 г, т.е. среди них нет ни
одной 99-граммовой. Для второго взвешивания берем детали с номерами 1, 2,
3, 8, 9. Их масса может быть равна 497 г (и тогда по 99 г весят детали 1,
2, 3), 498 г (если по 99 г весят 8, 9, 10), 499 г (9, 10, 11) и 500 г
(16, 17, 18).
- Масса всех взвешенных деталей – 799 г, т.е. среди них ровно одна
99-граммовая. Взвесим детали 2, 3, 4, 7, 8, 12. Здесь масса может равняться
597 г, 598 г, 599 г и 600 г, а соответствующими тройками 99-граммовых
деталей будут (2, 3, 4), (7, 8, 9), (10, 11, 12) и (15, 16, 17).
- Масса всех взвешенных деталей – 798 г, т.е. среди них ровно две
99-граммовые. Тогда взвесим детали 3, 4, 5, 6, 7, 12, и в случаях, когда
весы покажут 597 г, 598 г, 599 г и 600 г, искомыми тройками будут
(3, 4, 5), (6, 7, 8), (11, 12, 13) и (14, 15, 16) соответственно.
- Масса всех взвешенных деталей – 797 г, т.е. все 99-граммовые
детали находятся среди них. Вторым взвешиванием узнаем массу деталей 4, 5,
6, 12. В зависимости от того, равна она 397 г, 398 г, 399 г или 400 г,
искомой тройкой деталей будет (4, 5, 6), (5, 6, 7), (12, 13, 14) или (13,
14, 15) соответственно.
Второе решение. Назовем детали, весящие по 99 г, фальшивыми. Взвешивание на весах со стрелкой позволяет определить, сколько фальшивых деталей было среди взвешенных. У отрезка из трех деталей есть 16 возможных положений – самая левая из фальшивых может иметь номер от 1 до 16.
Предположим, что у нас есть два конкретных взвешивания. Тогда мы можем нарисовать таблицу результатов, показывающую для каждого положения левого конца фальшивого отрезка, сколько фальшивых деталей было бы взвешено. Если в таблице каждая пара чисел от 0 до 3 (их всего 16 ) встречается ровно 1 раз, то по результату взвешиваний можно однозначно определить положение фальшивого отрезка. Приведем такую таблицу.
Покажем, как найти взвешивания, дающие данную таблицу.
Первое взвешивание: из первого отрезка должно попасть ноль деталей, значит, с 1 по 3 – не берем, из второго (со 2 по 4) – тоже ноль, значит, 4 не берем, и так до 5 отрезка (с 5 по 7), из него должна быть взята одна деталь, значит это деталь 7, ибо все до 7 уже не взяты. Из отрезка 6 должна быть взята одна деталь, но уже взята деталь 7, значит 8 не берем. И так далее: каждый следующий отрезок содержит одну новую деталь, поэтому мы можем однозначно определить, брать ее или нет.
Проведя указанный алгоритм, получаем, что требуемые взвешивания существуют: 7, 10, 11, 13, 14, 15, 16, 17, 18 и 4, 5, 6, 7, 12, 13, 14, 15.
