Олимпиада имени Леонарда Эйлера2016-2017 учебный год, II тур дистанционного этапа

Известно, что среди 100 шаров ровно 51 радиоактивный. Имеется прибор, в который можно положить два шара, и если оба радиоактивны, то загорится лампочка (а если хотя бы один из двух шаров не радиоактивен, то не загорится). Можно ли найти все радиоактивные шары, использовав прибор не более 145 раз?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Можно.
Разобьём шары на 50 пар и испытаем их. Рассмотрим два возможных случая.
1) Ровно одно из этих испытаний выявило два радиоактивных шара. Тогда в каждой из остальных 49 пар ровно по одному радиоактивному шару. Испытав с одним из найденных радиоактивных по одному шару из каждой оставшейся пары, мы распознаем все 98 оставшихся шаров. Всего мы провели $50+49 = 99$ испытаний.
2) По два радиоактивных шара выявилось хотя бы в двух испытаниях. Тогда 4 радиоактивных шара мы уже нашли. Испытаем с одним из найденных радиоактивных шаров 95 шаров из 48 оставшихся пар. После этого мы про 99 шаров будем знать, какие из них радиоактивны. Если таких шаров 50, оставшийся шар радиоактивен, а если 51, то нет. Мы нашли все радиоактивные шары за $50+95 = 145$ испытаний.
Замечание. Более тонкими рассуждениями оценку 145 можно улучшить.