11 шаров. 5 красн 6белых1 кр и бел радиоакт. Можно проверить

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

Как и многие задачки о поиске липовой монеты, об угадывании загаданного числа и т.п., эта задача решается не способом тыка, а с помощью заблаговременно продуманного метода деяний. Этот метод должен быть таким, чтобы при каждом исходе еще одного действия можно было достигнуть цели (найти оба радиоактивных шара) за оставшееся количество деяний.

До этого чем обрисовывать определенный метод, сформулируем некоторые главные его характеристики.

1) Назовём вариантом каждую пару (красноватый шар, белоснежный шар), в которой оба шара могут быть радиоактивными. Сначала у нас есть 5 6 = 30 разных вариантов. Цель метода свести оставшиеся варианты к единственному.
2) Неважно какая проверка даёт один из двух исходов: + посреди испытанных шаров есть радиоактивные, и посреди испытанных шаров нет радиоактивных. Исход значит, что оба радиоактивных шара остались посреди тех, которые в этой проверке не участвовали.
3) Если до проверки имелось K вероятных вариантов, то после неё желая бы в одном из исходов остается не меньше чем ]K/2[. Тут квадратные скобки наружу ]...[ обозначают функцию потолок (калька с британского ceiling; см.: ceiling function) округление числа ввысь до наиблежайшего целого.
4) Из предшествующего характеристики сразу следует, что если число оставшихся вариантов больше, чем ступень двойки 2d, то не существует алгоритма, дозволяющего решить задачу за d проверок.
На этом месте, пожалуй, стоит задержаться. Итак, сначала у нас есть 30 вариантов и возможность сделать 5 проверок на радиоактивность. Может быть, эта задачка вначале неразрешима? К счастью, это не так: 25 = 32 gt; 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). 1-ый вариант значит проверку 2-ух красных и 1-го белоснежного, а 2-ой проверку только трех белых шаров.
В. r1 w1 = 14. Такое равенство невероятно, так как ни r1, ни w1 не могут быть одинаковы 7.
Остановимся на каком-нибудь одном из трёх случаев. Например, на случае Б. Итак,

Шаг 1. Проверим три (всех) белоснежных шара.

Если сенсор покажет, что посреди них есть радиоактивный, то другие три белых шара можно исключить из числа подозреваемых, а если сенсор покажет, что радиоактивности нет, то мы поймём, что посреди этих трёх шаров точно нет радиоактивных. В любом из 2-ух случаев у нас остается ровно 15 исходов: 5 (бардовых) 3 (белых).

Что делать далее? Продолжим анализ. Пусть во 2-ой проверке не участвовали 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 нет. Оставшимися 2-мя проверками найдём красный радиоактивный шар. А после финала мы узнаем, что либо оба шара R и W радиоактивны, или радиоактивен R и один из w2 = 2 белоснежных шаров. Таким образом, R точно радиоактивен, а белоснежный радиоактивный шар мы также просто найдём за две оставшихся проверки.

Значит, во всех случаях 5 проверок будет достаточно.