|
|
 |
Условие
а) Из 19 шаров 2 радиоактивны. Про любую кучку шаров за одну проверку можно узнать, имеется ли в ней хотя бы один радиоактивный шар (но нельзя узнать, сколько их). Доказать, что за 8 проверок всегда можно выделить оба радиоактивных шара.
б) Из 11 шаров два радиоактивны. Доказать, что менее чем за 7 проверок нельзя гарантировать нахождение обоих радиоактивных шаров,
а за 7 проверок их всегда можно обнаружить.
Решение
а) Заметим, что за n проверок можно выделить один радиоактивный шар из 2n (или меньшего числа) шаров (см. задачу 60907 а).
1) Среди n шаров можно найти два радиоактивных за n – 1 проверку (проверив по очереди n – 1 шар, мы без проверки будем знать, каков n-й).
2) Покажем, как выделить два радиоактивных шара из семи за пять проверок. Сначала проверим группу из двух шаров. Если результат отрицательный (среди них нет радиоактивных), то отсталось выделить два шара из оставшихся пяти за четыре проверки, что возможно.
Если результат положительный, проверим группу из четырёх шаров. Если этот результат отрицательный, то осталось выделить два шара из трёх подозрительных (2 проверки). Если положительный, осталось выделить один шар из двух (одна проверка) и еще один шар из четырёх (еще две проверки).
3) Покажем, как выделить два радиоактивных шара из девяти за шесть проверок. Сначала проверим группу из двух шаров. Если результат отрицательный, то отсталось выделить два шара из оставшихся семи за пять проверок (см. п. 2).
Если результат положительный, проверим группу из четырёх шаров. Если этот результат отрицательный, осталось выделить два шара из пяти подозрительных (четыре проверки). Если положительный, осталось выделить один шар из двух (одна проверка) и еще один шар из четырёх (еще две проверки).
4) Покажем, как выделить два радиоактивных шара из 13 за семь проверок. Сначала проверим группу из четырёх шаров. Если результат отрицательный, то отсталось выделить два шара из оставшихся девяти шаров за шесть проверок (см. п. 3).
Если результат положительный, проверим группу из восьми шаров. Если этот результат отрицательный, осталось выделить два шара из пяти подозрительных (четыре проверки). Если положительный, осталось выделить один шар из четырёх (две проверки) и еще один шар из восьми (еще три проверки).
5) Вернёмся к решению задачи. Проверим группу из шести шаров. Если результат отрицательный, то отсталось выделить два шара из оставшихся 13 за семь проверок (см. п. 4).
Если результат положительный, проверим группу из восьми шаров. Если этот результат отрицательный, проверим четыре шара из оставшихся пяти. Если и этот результат отрицательный, то осталось выделить два шара из семи подозрительных за пяти проверок (см. п. 2). Если положительный, осталось выделить один шар из шести (три проверки) и еще один шар из четырёх (еще две проверки).
Если результат проверки восьми шаров положительный осталось выделить один шар из шести (три проверки) и еще один шар из восьми (еще три проверки).
б) В а) показано, что за семь проверок можно выделить два радиоактивных шара даже из 13, тем более из 11 шаров. (Более простой способ для 11 шаров см. в решении задачи 35794.) Докажем, что шести проверок недостаточно.
Заметим, что n проверок не позволяют гарантировать выбор из более чем 2n возможных вариантов (каждая проверка при "неудачном" исходе позволяет отсечь не более половины вариантов; см. задачу 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 |
