Меченые шарики

Убедитесь, что если проверять шары каждого цвета отдельно, то на обнаружение каждого радиоактивного шара придется затратить 3 проверки.

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

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

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

Прежде чем описывать конкретный алгоритм, сформулируем некоторые важные его свойства.

1) Назовём вариантом каждую пару (красный шар, белый шар), в которой оба шара могут быть радиоактивными. Вначале у нас есть 5 · 6 = 30 различных вариантов. Цель алгоритма — свести оставшиеся варианты к единственному.
2) Любая проверка даёт один из двух исходов: «+» — среди проверенных шаров есть радиоактивные, и «–» — среди проверенных шаров нет радиоактивных. Исход «–» означает, что оба радиоактивных шара остались среди тех, которые в этой проверке не участвовали.
3) Если до проверки имелось K возможных вариантов, то после неё хотя бы в одном из исходов останется не меньше чем ]K/2[. Здесь квадратные скобки наружу ]...[ обозначают функцию «потолок» (калька с английского “ceiling”; см.: ceiling function) — округление числа вверх до ближайшего целого.
4) Из предыдущего свойства сразу следует, что если число оставшихся вариантов больше, чем степень двойки 2^d, то не существует алгоритма, позволяющего решить задачу за d проверок.

На этом месте, пожалуй, стоит задержаться. Итак, вначале у нас есть 30 вариантов и возможность сделать 5 проверок на радиоактивность. Может быть, эта задача изначально неразрешима? К счастью, это не так: 2⁵ = 32 > 30. Но чтобы не оказаться в неразрешимой ситуации после первой же проверки, нам нужно делать ее так, чтобы после каждого из исходов, и «+», и «–», осталось не более 16 вариантов (а значит, и не менее 14). Проще сосчитать варианты для исхода «–»: если в проверке не участвовали r₁ (от слова “red”) красных и w₁ (от “white”) белых шаров, то исходу «–» соответствуют ровно r₁ ∙ w₁ вариантов. Чтобы правильно определить первый шаг алгоритма, мы должны рассмотреть три возможных случая:

А. r₁ ∙ w₁ = 16. Поскольку r₁ ≤ 5 и w₁ ≤ 6, то r₁ = 4 и w₁ = 4. То есть проверяться должны все остальные — один красный и два белых шара.
Б. r₁ ∙ w₁ = 15. Здесь возможны два варианта для пары (r₁, w₁): (3, 5) или (5, 3). Первый вариант означает проверку двух красных и одного белого, а второй — проверку только трех белых шаров.
В. r₁ ∙ w₁ = 14. Такое равенство невозможно, так как ни r₁, ни w₁ не могут быть равны 7.

Остановимся на каком-нибудь одном из трёх случаев. Например, на случае Б. Итак,

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

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

Что делать дальше? Продолжим анализ. Пусть во второй проверке не участвовали r₂ ≤ 5 красных и w₂ ≤ 3 белых шаров (здесь мы уже совсем забыли про те три шара, которые точно не радиоактивны, и исследуем только три оставшихся). После каждого исхода этой проверки должно остаться не больше 8 (а значит, и не меньше 15 – 8 = 7) вариантов. Поскольку равенство r₂ ∙ w₂ = 7 невыполнимо, то осталось рассмотреть только r₂ ∙ w₂ = 8, откуда r₂ = 4 и w₂ = 2 (не наоборот, потому что w₂ ≤ 3). Значит, на втором шаге должны быть проверены один красный и один белый шары, других вариантов быть просто не может. Итак,

Шаг 2. Проверим один красный шар R и один белый шар W.

Если исход этой проверки «–», то дальше всё просто: мы знаем, что один из r₂ = 4 красных и один из w₂ = 2 белых — радиоактивные. Их вполне можно определять по отдельности: на выявление белого шара достаточно одной (третьей) проверки, а на выявление красного — двух оставшихся.

А вот если исходом этой проверки оказался «+», то даже описать оставшиеся варианты не очень просто. Мы знаем, что хотя бы один из шаров R и W — радиоактивен. Но какой? Либо только R (а белым радиоактивным является один из w₂ = 2 остальных), либо только W (а красным радиоактивным является один из r₂ = 4 остальных), либо они оба вместе. Итого 2 + 4 + 1 = 7 вариантов. Как действовать дальше? Нужно снова пользоваться свойством 4): на третьем шаге нужно разбить 7 вариантов на 3 + 4. Для этого, например, можно делать шаг 3 таким:

Шаг 3. Проверим все r₂ = 4 красных шара, кроме R.

После исхода «+» мы будем знать, что W радиоактивен, а R — нет. Оставшимися двумя проверками найдём красный радиоактивный шар. А после исхода «–» мы узнаем, что либо оба шара R и W радиоактивны, либо радиоактивен R и один из w₂ = 2 белых шаров. Таким образом, R точно радиоактивен, а белый радиоактивный шар мы также легко найдём за две оставшихся проверки.

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

Несмотря на очевидную «игрушечность» постановки задачи, сама эта задача относится к сфере так называемой комбинаторной теории поиска, которая является вполне серьезной научной тематикой. В отличие от многих других математических задач, история которых уходит корнями в глубину веков, происхождение комбинаторной теории поиска (а если быть точным — методов группового тестирования) очень тесно связано с событиями Второй мировой войны, но при этом ни к какой атомно-радиоактивной проблематике отношения не имеет. Отцом метода можно считать единственного человека — Роберта Дорфмана. Вот как он сам описывает предысторию рождения метода группового тестирования:

Это было в 1942-м или в начале 1943-го. Дело было в Вашингтоне, в отделе статистики цен исследовательского департамента президентской администрации, где тогда работали Дэвид Розенблатт и я. Мы располагались во временном здании с длинными крыльями, заполненными столами безо всяких промежутков. Тяготы такой жизни компенсировались проходившими время от времени бурными дискуссиями. Групповое тестирование впервые было разработано в ходе одной из них. Будучи экономистами, мы все были поражены расточительством подвергания образцов крови миллионов призывников идентичным анализам в целях выявления нескольких тысяч зараженных сифилисом. Кто-то сказал, что было бы экономичнее смешать их кровь вместе, и эта идея была обсосана со всех сторон в ходе живого обмена мнениями, с шутками и прибаутками. Я не помню, как именно была тогда сформулирована задача. Но совершенно ясно, что я воспринял идею достаточно серьезно, так как в последующие несколько дней я сформулировал основную задачу как вероятностную и привлек для ее решения алгебру (впрочем, довольно элементарную). Вскоре после этого я написал доклад, представил его на заседании Вашингтонской статистической ассоциации, а четырехстраничная рукопись доклада была некоторое время спустя опубликована в журнале «Анналы математической статистики».

В статье Дорфмана было сказано буквально следующее:

Предлагаемый метод предназначен для использования службой здравоохранения Соединенных Штатов в целях недопущения призыва на воинскую службу всех мужчин, заболевших сифилисом. В рамках этой программы каждый будущий призывник сейчас подвергается тесту Вассермана. Это испытание может быть удобно разделено на две части: 1) взятие образца крови у человека, 2) лабораторный анализ крови, показывающий наличие или отсутствие «сифилитического антигена». Наличие такого антигена является признаком инфекции. Для этой процедуры необходимы n химических исследований для выявления всех инфицированных членов популяции размера n.

Ключевая особенность предлагаемой методики такова. Предположим, что после индивидуальных взятий крови образцы объединены в группы, например по 5, и именно эти группы, а не индивидуальные образцы, подвергаются химическому анализу. Если ни один из пяти исходных образцов не содержит сифилитический антиген, то и вся группа не будет содержать его, и это экономит четыре теста из пяти. Если же один или более из образцов содержат сифилитический антиген, то и группа будет также содержать его, и тогда групповое тестирование покажет его присутствие (диагностические средства для обнаружения сифилиса чрезвычайно чувствительны — дают положительные результаты даже при малом количестве антигена). Лица, чьи анализы вошли в такую группу, затем должны пройти повторное тестирование, чтобы определить, кто из них инфицирован. Для этого не надо брать у них нового образца крови. Химический анализ требует лишь небольшого количества крови, поэтому можно воспользоваться уже взятыми образцами…

Дальше в статье приводился рисунок, иллюстрирующий экономию, которая может быть достигнута благодаря использованию группового тестирования.

Как часто случается с новыми математическими теориями, применить их на практике по каким-либо причинам не удается. Причиной неудачи применения группового тестирования (group testing, GT) для скрининга сифилиса было то, что объединение в группу даже 8–9 индивидуальных анализов существенно снижало точность теста, то есть повышало долю ложных срабатываний. Тем не менее статья Дорфмана не прошла совсем незамеченной, и идея GT вошла в качестве задачи в популярный учебник Феллера по теории вероятностей, а затем именно из этого учебника была воспринята всем математическим сообществом. Нужно отметить, что с окончанием Второй мировой и отказом США от всеобщей воинской повинности необходимость группового тестирования проб крови исчезла, и научный мир похоронил этот метод как один из эпизодов ушедшей войны. И только много лет спустя (почти случайно) в поисках методик для проверки исправности электрических и электронных приборов методы GT были заново открыты и получили мощнейший толчок к развитию. Одной из активно развившихся ветвей является комбинаторное групповое тестирование (CGT), другой — вероятностное групповое тестирование (PGT).

Почему в качестве фабулы задачи нами были выбраны какие-то радиоактивные шары и детектор радиоактивности, а не что-то иное? Видимо, потому что именно в таких терминах была сформулирована самая первая CGT-задача, которая встретилась автору. Это была задача Московской математической олимпиады 1966 года (правда, автор познакомился с ней не тогда, а спустя много лет, после выхода сборника задач Московских олимпиад).

Общий случай для той задачи, которую мы решили, относится именно к CGT. Пусть заранее известно, что одним из искомых (зараженных, радиоактивных и т.д.) объектов является ровно один из объектов множества A, а другим — ровно один из объектов множества B. Если множество A состоит из N объектов, а множество B — из M и эти два множества не пересекаются, то в такой задаче имеется NM вариантов. Как мы выяснили, это означает, что для решения задачи необходимо использовать ]log₂ NM[ шагов (тестов, проверок). Но всегда ли такого количества окажется достаточно?

Ответ на этот вопрос для двух заражённых объектов был получен в 1981 году в статье A Group Testing Problem on Two Disjoint Sets. Её авторы Дж. Чанг и Ф. Хванг доказали, что этого количества тестов всегда достаточно. Однако обобщение того же вопроса на большее число заражённых объектов остаётся и по сей день нерешенной (открытой) проблемой. То же самое можно сказать и про те задачи CGT, в которых заражённые объекты исходно не разделены, то есть могут принадлежать к пересекающимся (или даже совпадающим) множествам.

Сейчас CGT изучается в таких университетских курсах, как сложность вычислений, теория графов, комбинаторика и теория информации (пример см. в ссылках ниже), причем зачастую специалисты по CGT формулируют свои задачи «на разных языках» и из-за этого не следят за результатами друг друга. Возможно, такая ситуация выправится после того, как Дональд Кнут закончит 4-й том «Комбинаторный поиск» своего фундаментального «Искусства программирования». Однако те главы четвёртого тома, в которых Кнут планирует рассказать про современное состояние методов группового тестирования, пока еще не написаны, поэтому очень хочется пожелать 75-летнему автору долголетия и крепкого здоровья.

См. также:
1) R. Dorfman. The Detection of Defective Members of Large Populations // Ann. Math. Statist. 1943. V. 14. No. 4. P. 436–440.
2) Г. А. Кабатянский. Курс Теория информации и комбинаторная теория поиска, факультет бизнес-информатики НИУ ВШЭ.
3) Задача о радиоактивных шарах, XXIX Московская математическая олимпиада (1966 г.).
4) Д. Э. Кнут. Искусство программирования. Том 4А. Комбинаторные алгоритмы.
5) G. J. Chang and F. K. Hwang. A Group Testing Problem on Two Disjoint Sets // SIAM J. Alg. Disc. Meth.. March 1981. V. 2. No. 1. P. 35–38.