11 шаров. 5 красн 6белых
1 кр и бел радиоакт. Можно проверить любую группу и детектор покажет есть ли там хоть 1 радиоакт шар. Но не пркажет сколько их. Как за 5 проверок найти оба шара
1 кр и бел радиоакт. Можно проверить любую группу и детектор покажет есть ли там хоть 1 радиоакт шар. Но не пркажет сколько их. Как за 5 проверок найти оба шара
Answers & Comments
Как и многие задачи о поиске фальшивой монеты, об угадывании задуманного числа и т.п., эта задача решается не «методом тыка», а с помощью заранее продуманного алгоритма действий. Этот алгоритм должен быть таким, чтобы при каждом исходе очередного действия можно было достичь цели (обнаружить оба радиоактивных шара) за оставшееся количество действий.
Прежде чем описывать конкретный алгоритм, сформулируем некоторые важные его свойства.
1) Назовём вариантом каждую пару (красный шар, белый шар), в которой оба шара могут быть радиоактивными. Вначале у нас есть 5 · 6 = 30 различных вариантов. Цель алгоритма — свести оставшиеся варианты к единственному.
2) Любая проверка даёт один из двух исходов: «+» — среди проверенных шаров есть радиоактивные, и «–» — среди проверенных шаров нет радиоактивных. Исход «–» означает, что оба радиоактивных шара остались среди тех, которые в этой проверке не участвовали.
3) Если до проверки имелось K возможных вариантов, то после неё хотя бы в одном из исходов останется не меньше чем ]K/2[. Здесь квадратные скобки наружу ]...[ обозначают функцию «потолок» (калька с английского “ceiling”; см.: ceiling function) — округление числа вверх до ближайшего целого.
4) Из предыдущего свойства сразу следует, что если число оставшихся вариантов больше, чем степень двойки 2d, то не существует алгоритма, позволяющего решить задачу за d проверок.
На этом месте, пожалуй, стоит задержаться. Итак, вначале у нас есть 30 вариантов и возможность сделать 5 проверок на радиоактивность. Может быть, эта задача изначально неразрешима? К счастью, это не так: 25 = 32 > 30. Но чтобы не оказаться в неразрешимой ситуации после первой же проверки, нам нужно делать ее так, чтобы после каждого из исходов, и «+», и «–», осталось не более 16 вариантов (а значит, и не менее 14). Проще сосчитать варианты для исхода «–»: если в проверке не участвовали r1 (от слова “red”) красных и w1 (от “white”) белых шаров, то исходу «–» соответствуют ровно r1 ∙ w1 вариантов. Чтобы правильно определить первый шаг алгоритма, мы должны рассмотреть три возможных случая:
А. r1 ∙ w1 = 16. Поскольку r1 ≤ 5 и w1 ≤ 6, то r1 = 4 и w1 = 4. То есть проверяться должны все остальные — один красный и два белых шара.
Б. r1 ∙ w1 = 15. Здесь возможны два варианта для пары (r1, w1): (3, 5) или (5, 3). Первый вариант означает проверку двух красных и одного белого, а второй — проверку только трех белых шаров.
В. r1 ∙ w1 = 14. Такое равенство невозможно, так как ни r1, ни w1 не могут быть равны 7.
Остановимся на каком-нибудь одном из трёх случаев. Например, на случае Б. Итак,
Шаг 1. Проверим три (любых) белых шара.
Если детектор покажет, что среди них есть радиоактивный, то остальные три белых шара можно «исключить из числа подозреваемых», а если детектор покажет, что радиоактивности нет, то мы поймём, что среди этих трёх шаров точно нет радиоактивных. В любом из двух случаев у нас останется ровно 15 исходов: 5 (красных) × 3 (белых).
Что делать дальше? Продолжим анализ. Пусть во второй проверке не участвовали r2 ≤ 5 красных и w2 ≤ 3 белых шаров (здесь мы уже совсем забыли про те три шара, которые точно не радиоактивны, и исследуем только три оставшихся). После каждого исхода этой проверки должно остаться не больше 8 (а значит, и не меньше 15 – 8 = 7) вариантов. Поскольку равенство r2 ∙ w2 = 7 невыполнимо, то осталось рассмотреть только r2 ∙ w2 = 8, откуда r2 = 4 и w2 = 2 (не наоборот, потому что w2 ≤ 3). Значит, на втором шаге должны быть проверены один красный и один белый шары, других вариантов быть просто не может. Итак,
Шаг 2. Проверим один красный шар R и один белый шар W.
Если исход этой проверки «–», то дальше всё просто: мы знаем, что один из r2 = 4 красных и один из w2 = 2 белых — радиоактивные. Их вполне можно определять по отдельности: на выявление белого шара достаточно одной (третьей) проверки, а на выявление красного — двух оставшихся.
А вот если исходом этой проверки оказался «+», то даже описать оставшиеся варианты не очень просто. Мы знаем, что хотя бы один из шаров R и W — радиоактивен. Но какой? Либо только R (а белым радиоактивным является один из w2 = 2 остальных), либо только W (а красным радиоактивным является один из r2 = 4 остальных), либо они оба вместе. Итого 2 + 4 + 1 = 7 вариантов. Как действовать дальше? Нужно снова пользоваться свойством 4): на третьем шаге нужно разбить 7 вариантов на 3 + 4. Для этого, например, можно делать шаг 3 таким:
Шаг 3. Проверим все r2 = 4 красных шара, кроме R.
После исхода «+» мы будем знать, что W радиоактивен, а R — нет. Оставшимися двумя проверками найдём красный радиоактивный шар. А после исхода «–» мы узнаем, что либо оба шара R и W радиоактивны, либо радиоактивен R и один из w2 = 2 белых шаров. Таким образом, R точно радиоактивен, а белый радиоактивный шар мы также легко найдём за две оставшихся проверки.
Значит, во всех случаях пяти проверок будет достаточно.