Есть 4 шарика один из которых радиоактивный

а) Из 19 шаров 2 радиоактивны. Про любую кучку шаров за одну проверку можно узнать, имеется ли в ней хотя бы один радиоактивный шар (но нельзя узнать, сколько их). Доказать, что за 8 проверок всегда можно выделить оба радиоактивных шара.

б) Из 11 шаров два радиоактивны. Доказать, что менее чем за 7 проверок нельзя гарантировать нахождение обоих радиоактивных шаров,
а за 7 проверок их всегда можно обнаружить.

Решение

а) Заметим, что за n проверок можно выделить один радиоактивный шар из 2 n (или меньшего числа) шаров (см. задачу 60907 а).
1) Среди n шаров можно найти два радиоактивных за n – 1 проверку (проверив по очереди n – 1 шар, мы без проверки будем знать, каков n-й).
2) Покажем, как выделить два радиоактивных шара из семи за пять проверок. Сначала проверим группу из двух шаров. Если результат отрицательный (среди них нет радиоактивных), то отсталось выделить два шара из оставшихся пяти за четыре проверки, что возможно.
Если результат положительный, проверим группу из четырёх шаров. Если этот результат отрицательный, то осталось выделить два шара из трёх подозрительных (2 проверки). Если положительный, осталось выделить один шар из двух (одна проверка) и еще один шар из четырёх (еще две проверки).
3) Покажем, как выделить два радиоактивных шара из девяти за шесть проверок. Сначала проверим группу из двух шаров. Если результат отрицательный, то отсталось выделить два шара из оставшихся семи за пять проверок (см. п. 2).
Если результат положительный, проверим группу из четырёх шаров. Если этот результат отрицательный, осталось выделить два шара из пяти подозрительных (четыре проверки). Если положительный, осталось выделить один шар из двух (одна проверка) и еще один шар из четырёх (еще две проверки).
4) Покажем, как выделить два радиоактивных шара из 13 за семь проверок. Сначала проверим группу из четырёх шаров. Если результат отрицательный, то отсталось выделить два шара из оставшихся девяти шаров за шесть проверок (см. п. 3).
Если результат положительный, проверим группу из восьми шаров. Если этот результат отрицательный, осталось выделить два шара из пяти подозрительных (четыре проверки). Если положительный, осталось выделить один шар из четырёх (две проверки) и еще один шар из восьми (еще три проверки).
5) Вернёмся к решению задачи. Проверим группу из шести шаров. Если результат отрицательный, то отсталось выделить два шара из оставшихся 13 за семь проверок (см. п. 4).
Если результат положительный, проверим группу из восьми шаров. Если этот результат отрицательный, проверим четыре шара из оставшихся пяти. Если и этот результат отрицательный, то осталось выделить два шара из семи подозрительных за пяти проверок (см. п. 2). Если положительный, осталось выделить один шар из шести (три проверки) и еще один шар из четырёх (еще две проверки).
Если результат проверки восьми шаров положительный осталось выделить один шар из шести (три проверки) и еще один шар из восьми (еще три проверки).

б) В а) показано, что за семь проверок можно выделить два радиоактивных шара даже из 13, тем более из 11 шаров. (Более простой способ для 11 шаров см. в решении задачи 35794.) Докажем, что шести проверок недостаточно.
Заметим, что n проверок не позволяют гарантировать выбор из более чем 2 n возможных вариантов (каждая проверка при «неудачном» исходе позволяет отсечь не более половины вариантов; см. задачу 60907 а).
Пусть в первый раз мы проверяем не более двух шаров и получен отрицательный результат. За оставшиеся пять проверок не удастся выделить два шара из девяти (число оставшихся вариантов равно числу пар ). Пусть в первый раз мы проверяем не менее четырёх шаров и получен положительный результат. Осталось вариантов, и снова их не удастся «разделить».
Пусть в первый раз мы проверяем группу из трёх шаров и получен отрицательный результат. Теперь мы должны выделить два шара из восьми за пять проверок. Аналогичные оценки показывают, что проверять один или три шара «невыгодно» Итак, во второй проверке должны участвовать два шара, и при отрицательном результате придётся выделять два шара из шести за четыре проверки.
Но это невозможно: проверив один шар, мы можем оставить вариантов, а проверив два шара, – вариантов; оба эти числа больше 2³.

Замечания

В 8 кл. предлагался только п. а), а в 9-11 кл. – только п. б)

2. Более подробное решение и обобщение этой задачи см. в решениях Задачника «Кванта».

3. Мы не стремились дать оптимальные алгоритмы. Так за шесть проверок можно выделить два радиоактивных шара из 10, за семь – из 14, а за восемь – из 21 (см. там же).

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	29
Год	1966
вариант
1
Класс	9,10,11
Тур	2
задача
Номер	3
журнал
Название	«Квант»
год
Год	1970
выпуск
Номер	6
Задача
Номер	М28
олимпиада
Название	Московская математическая олимпиада
год
Номер	29
Год	1966
вариант
1
Класс	8
Тур	2
задача
Номер	3

Задача о поиске радиоактивных шаров

Строим алгоритм, используя принципы теории информации

IV Интернет-олимпиада по математике/XIV тур Математического Марафона (12)→
XV тур математического марафона (12)→
Вторая открытая Интернет-олимпиада по математике (9)→
Третья Интернет-олимпиада по математике/XIII тур Математического Марафона (12)→
Задачи конкурса Ponder This компании IBM (7)→
Задачи областной олимпиады по математике 2010 (5)→
Первая открытая Интернет-олимпиада по математике (9)→
Задачи областной олимпиады по математике 2009 (5)→
Как доказывать олимпиадные неравенства
Задачи международного турнира
XXI тур Математического Марафона
Отбор на XVI Всеукраинский турнир — Часть 2
Отбор на XVI Всеукраинский турнир — Часть 1
Далеко, далеко, на лугу пасутся ко.
Людоед и гномики
Поиск фальшивой монеты
Два парома
Как вычислять бесконечные суммы: часть 1
Вариации на тему игры Баше
Мотоциклист, велосипедист и пешеход
Утроение числа после перестановки цифр
Как вычислять бесконечные суммы: часть 2
Задача о поиске радиоактивных шаров
Нестандартное решение задачи по теории вероятности
Математические маневры
Задача о двух мудрецах
Ранжирование грузов по весу

Задача
Имеется 15 шаров. Среди них 2 радиоактивных. Имеется счётчик Гейгера. Его можно поднести к группе шаров и узнать, есть ли в ней радиоактивные (но неизвестно — сколько их). За сколько замеров можно найти оба радиоактивных шара в группе из 15 шаров?

Задачи подобного рода, в которых нужно, пользуясь прибором с конечным числом состояний, выделить искомые предметы из многих или упорядочить предметы, регулярно появляются на математических форумах. Они традиционно вызывают серьёзные затруднения при решении и споры в ходе его обсуждения.

Однако если знать общий подход, решение их достаточно легко.

Метод решения таких задач состоит из четырёх шагов, которые мы и рассмотрим.

Шаг 1: Определить количество вариантов ответа на задачу.
Перенумеруем шары числами от 1 до 15. Сколькими способами среди них могут располагаться два радиоактивных?
Первый радиоактивный шар может быть одним из пятнадцати. Второй – одним из четырнадцати. Всего 15*14=210 вариантов. Но т.к. каждая пара таким способом была подсчитана дважды (например, пары (1,2) и (2,1) – одна и та же пара шаров), то результат следует разделить на 2. Получим 210/2=105 вариантов.

Шаг 2: В какое наибольшее количество раз можно уменьшить количество возможностей, получив один результат измерения?
Т.к. счётчик может или запищать, или не запищать, то каждое измерение уменьшает количество возможностей не более чем вдвое.
В задачах о фальшивых монетах прибором выступают чаще всего весы, у которых может перевесить левая чаша, правая чаша или сохраниться равновесие – здесь неопределённость одним измерением снижается втрое.

Шаг 3. За какое количество измерений заведомо нельзя решить задачу?
Из 105 вариантов ответа, после первого измерения их останется не менее 53.
После второго – не менее 27.
После третьего – не менее 14.
После четвёртого – не менее 7.
После пятого – не менее 4.
После шестого – не менее 2.

Значит, за 6 измерений решить задачу невозможно. Попробуем это сделать за 7.

Шаг 4. Выберите предметы для измерения так, чтобы при любом его исходе ответ гарантированно находился за оставшиеся.

Поясним на примере.
Перед нами 15 шаров. Существует 105 возможных пар радиоактивных среди них.

Стоит ли для первого измерения выбирать один шар?
Если счётчик запищит, количество вариантов сократится до 14: это пары (1, 2), (1, 3), …, (1, 14). Один вариант из 14 можно найти за 4 измерения.
Н дозиметр не запищит в 105-14=91 случае, и если он не запищит, нам оставшихся шести замеров не хватит, чтобы найти радиоактивный.

Стоит ли для первого измерения брать два шара?
Счётчик запищит, если они оба радиоактивны (это 1 случай) или если радиоактивный только первый (это 13 случаев) или – только второй (ещё 13 случаев). Итого 27 случаев.

Не запищит же он в 105-27=78 случаях. Это всё равно больше, чем 64 – предельно возможное число вариантов, из которого можно выделить один за 6 измерений прибором, дающим один из двух вариантов ответа.

Рассуждая аналогично получим, что если сначала замерить три шара, 105 вариантов разделятся как 39+66, и мы опять не уложимся в оставшиеся 6 замеров.

Вот вариант с замером четырёх шаров выглядит перспективно:
Если прибор запищит, нужно будет за 6 измерений выбрать один вариант из 50, а если не запищит – из 55 (иначе говоря, во втором случае задача сведётся к поиску двух радиоактивных шаров из 11 за 6 измерений)

Но для задачи 2 из 11 за 6 нельзя подобрать такое измерение, которое бы 55 вариантов ответа разделило бы на две группы, каждая из которых содержит меньше 32 вариантов.

Итак, для первого замера надо брать 5 шаров.
Если не запищит, имеем задачу 2 из 10 за 6, которая решается легко.
Если же прибор запищит, то имеется 60 вариантов для пары радиоактивных шаров, которые можно представить в виде таблицы: