Есть 30 шаров, среди которых 5 радиоактивны. Имеется тестер, в который за один тест можно положить любое число шаров, после чего тестер сообщит, сколько среди положенных шаров радиоактивны. Как не более чем за 3 теста найти 5 нерадиоактивных шаров?
Задача была предложена на командной олимпиаде 6 классов на 45 Уральском турнире юных математиков.
Авторы задачи - Сергей Геннадьевич Волчёнков и Сергей Львович Берлов.
Как решать такую задачу? Надо попытаться её упростить. Сколько шаров должно быть, чтобы за один тест найти пять "хороших" шаров, если есть один радиоактивный? Точно подходит ситуация, когда 10 шаров.
А если два теста и 3 радиоактивных шара, то в условии может быть 20 шаров.
Надо и здесь взять 20 произвольных шаров и узнать, сколько среди них радиоактивных.
Если радиоактивных нет, то мы найдём даже не пять, а целых двадцать "хороших" шаров.
Если радиоактивный шар один, то возьмём любые десять из этих двадцати шаров. В какой-то десятке "плохих" шаров не будет.
Если радиоактивных шаров два или три, то опять возьмём какую-то десятку шаров. Или в ней, или в той десятке, что мы не взяли, радиоактивных шаров не больше одного. Поделим ту десятку на две равные части и возьмём одну из них для теста. Если там нет "плохих" шаров, то возьмём эту пятёрку. Если есть, то возьмём другую пятёрку.
Если радиоактивных шаров четыре, то возьмём оставшуюся десятку шаров. Там один "плохой". Возьмём из той десятки пять шаров и поймём, в какой пятёрки "плохих" шаров нет.
Ну, а если радиоактивных шаров пять, то в оставшейся десятке нет радиоактивных.
Задача решена!