Фальшивые евро

То, что у Васи есть пять монет каждой страны, вовсе не означает, что он обязан взвешивать все эти монеты. Например, он может в первом взвешивании брать 4 монеты Австрии, а во втором — 3 таких монеты. Самое главное, — чтобы ни для какой другой страны комбинацию «4 + 3» он больше не использовал, иначе, если именно одна из этих стран окажется отличающейся от прочих, то Вася не сможет однозначно установить, какая из них.

На первый взгляд, количество вариантов пар взвешиваемых монет у Васи намного больше, чем ему нужно различить. Ведь Вася может брать для каждого взвешивания от 0 до 5 монет, что даёт ему 6 возможностей, а 6·6 > 21. Однако на самом деле далеко не все возможности реализуемы. Например, если он возьмёт 0 + 1 монету Бельгии и 0 + 2 монеты Ватикана, то возможен расклад, при котором он не сможет различить эти ситуации. Ведь две монеты запросто могут отличаться от двух «настоящих», например, на 6 г, и одна монета тоже может отличаться на 6 г.

Это соображение заставляет Васю сразу отказаться от потенциально неразличимых ситуаций, например, из вариантов 1 + 2 и 2 + 4 он может использовать только один.

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

После этого соображения уже нетрудно привести полный список вариантов для Васи:

(Обратите внимание, что вариантов 1 + 1, 2 + 2, 3 + 3, 4 + 4 нет, потому что использован вариант 5 + 5, а вариантов 1 + 2 и 2 + 1 нет, потому что есть варианты 2 + 4 и 4 + 2. Причины этого объяснялись в подсказке).

Таким образом, Вася, в общем-то, не особо свободен в выборе. Всего есть 21 страна — и ровно столько же вариантов... Но ведь это еще далеко не всё, надо еще понимать, как решать задачу...

Нетрудно сосчитать, что Вася в каждом взвешивании должен взять 67 монет, поэтому в первом взвешивании он получает вес W = 67x + dn, где x — вес «настоящих» монет, d — отличие «настоящего» веса от веса монет интересующей Васю страны (мы вместе с Васей знаем, что оно не равно 0 и меньше 8, но даже не уверены, целое ли это число!), а n — количество монет этой страны, взвешенное Васей в первом взвешивании (во втором — вместо n будет какое-то другое число m). Если по паре значений (W₁, W₂) = (67x + dn, 67x + dm) Вася сможет определить значения x, d, n и m, то он успешно решит свою задачу: x — ответ на третий вопрос, x + d — ответ на второй вопрос, а пара (n, m) вместе с приведенной выше табличкой позволит Васе однозначно ответить на первый вопрос.

И действительно, Васе может так повезти. Для этого достаточно, чтобы было выполнено неравенство 67t − 27 ≤ W₁ ≤ 67t + 27 для некоторого целого значения t. В самом деле, так как |d| < 8 (масса отличается менее чем на 8, но неизвестно, в какую сторону) и n ≤ 5, то |nd| < 40, а значит, искомый вес x не может быть ни меньше, чем t (это слишком мало, W₁ = 67(t − 1) + nd < 67(t − 1) + 40 = 67t − 27, что противоречит выписанному выше двойному неравенству), ни больше чем t (симметрично, это слишком много: W₁ = 67(t + 1) + nd > 67(t + 1) + 40 = 67t + 27). Тогда сразу ясно, что x = t, то есть в этом случае Вася уже знает x. Затем он определяет (W₁ − 67x, W₂ − 67x) = (dn, dm), а поскольку все отношения n/m для разных стран различны, то он находит это отношение, а, следовательно, узнает и страну. Ну и, наконец, найти единственную невычисленную величину d — пустяшное дело для умницы Васи...

Но ведь не каждое возможное W₁ попадёт в такой промежуток: расстояние между соседними числами, кратными 67, равно 67, а Васе повезёт только в том случае, если расстояние до ближайшего такого числа окажется не больше 27. А если больше? Как ни крути, а выкручиваться как-то надо.

Итак, случай невезения: 67t + 27 < W₁ < 67(t + 1) − 27 = 67t + 40.

В этом случае после первого взвешивания Вася не знает точного значения x (оно может быть равно либо t, либо t + 1). Но зато этот случай хорош тем, что Вася точно знает, что он взвесил не менее 4 монет интересующей его страны! Действительно, так как вес монеты отличается меньше чем на 8, то тремя монетами Вася никак бы не мог получить отличие от величины, кратной 67, на 27 в ту или иную сторону. А ведь получил! Таким образом, Вася сразу же может сузить список «подозреваемых» стран, вычеркнув из него все страны с номерами (см. таблицу) от 11 до 21. Это еще не победа, но уже заявка на успех.

И решающим слагаемым этого успеха является возможность поменять второе взвешивание! Действительно, теперь Вася может (и должен!) брать по 5 монет от каждой страны с номерами от 11 до 21. Это увеличит общее число монет во втором взвешивании с 67 до 81. Таким образом, во втором взвешивании Вася узнает величину W₂ = 81x + md, при этом он точно знает, что m не больше 5, а d по модулю меньше 8. Но тогда эта величина отличается от числа, кратного 81, не более чем на 40, а для каждого значения W₂ есть только одно число, кратное 81, с таким свойством — это ближайшее к нему кратное 81! Тем самым, после второго взвешивания Вася точно знает x, а значит, знает и пару (W₁ − 67x, W₂ − 81x) = (dn, dm), поэтому находит нужную ему страну и, конечно же, моментально определяет значение d.

Мы начали решение с того, что порекомендовали Васе использовать самый «нагруженный» вариант из возможных. Теперь, после окончания решения, этот рецепт становится понятным: если бы Вася использовал меньше монет, то вместо 67 у него бы было меньшее значение общего количества монет, а это не позволило бы столь же хорошо отсечь большое количество вариантов в самом сложном «невезучем» случае.

Задача составлена автором по мотивам вот этой. В исходной версии было не более 4 монет каждого вида, и всего 13 различных видов. По-видимому, ранее 2010 года она не встречалась. Наша версия с 21 видами и 5 монетами (с отличием веса на 8) позволяет избежать скучных переборных решений.

Разумеется, это исторически не первая задача, в которой предлагалось определить одновременно и вес настоящей монеты, и вес фальшивой монеты, и сами фальшивые монеты. Одна из первых задач такого рода была опубликована в American Mathematical Monthly еще в 1960 году и впоследствии привела к появлению целого класса задач комбинаторного группового тестирования (combinatorial group testing, CGT). К ним же относится и задача «Меченые шарики», в которой требовалось за пять проверок найти два радиоактивных шарика разных цветов среди данных 11 шариков, из которых 5 — красные, а 6 — белые.

В послесловии к задаче про меченые шарики описывалась интересная история возникновения CGT. Ниже мы воспроизводим ее с небольшими изменениями.

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

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

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

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

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

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

Литература для погружения в тему:
1) N. J. Fine. Solution E1399 // American Mathematical Monthly. 1960. V. 67. P. 697–698.
2) S. Soderberg and H. S. Shapiro. A combinatory detection problem // American Mathematical Monthly. 1963. V. 70. P. 1066-1070.
3) L. Gargano, V. Montuori, G. Setaro and U. Vaccaro. An improved algorithm for quantitative group testing // Discrete Applied Mathematics. 1992. V. 36 P. 299–306.
4) К. А. Кноп, Л. Э. Медников. «Тест Клепцына: с компьютером и без него» // Математическое просвещение. 2010. Серия 3. 14. С. 204–213.