Тайна фальшивых монеток

Константин Кноп

Придумать новую математическую задачу - дело не очень трудное.  Ежегодно проводится масса олимпиад, для которых придумываются (или перелицовываются на новый лад) куча новых задач. А вот придумать новый тип задач - штука намного более трудная. В III веке до н.э. Диофант Александрийский стал решать неопределённые уравнения, в которых неизвестных величин (переменных) было более одной - с тех пор эти уравнения получили название диофантовых. Еще раньше Пифагор исследовал прямоугольные треугольники с целыми сторонами (впрочем, тогда никаких других чисел, кроме целых и дробей, еще не знали) - с тех пор такие треугольники зовутся пифагоровыми. Задачи о взвешиваниях и нахождении "фальшивых" монет имеют, конечно, не такую давнюю историю, но и в них кажется невозможным придумать что-то принципиально новое. Однако ж...

В 2007 году А.В.Шаповалов предложил для Кубка памяти А.Н.Колмогорова задачу, в которой описывался принципиально новый тип взвешиваний - "взвешивания без разглашения". В данной статье я позволю себе называть их проще - шаповаловскими взвешиваниями. Ниже - формулировка исходной задачи

Суду предъявлены 100 одинаковых с виду монет. Суд уже установил, что среди них есть 2 или 3 фальшивые, все настоящие монеты весят одинаково, фальшивые -- тоже одинаково, но легче настоящих. Адвокат знает, какие монеты на самом деле фальшивые. Может ли он убедить суд, что фальшивых монет три, а не две, не разгласив ни про какую монету, фальшивая она или настоящая? (Адвокат должен делать взвешивания на чашечных весах без гирь. Число взвешиваний не ограничено. Запрещены взвешивания и группы взвешиваний, из которых логически выводится, что конкретная монета фальшивая или настоящая.)

Обратите внимание на необходимость неразглашения информации не только о фальшивых, но и о настоящих монетах. Это не традиционная "информационная" задача на определение фальшивой монетки за наименьшее возможное число операций, а совсем другая история... Слово "запрещены" в условии следует понимать так: вначале адвокат что-то делает на весах. После этого суд решает два независимых вопроса: 1) Доказал ли адвокат, что фальшивых монет три, а не две. 2) Стало ли при этом известным (разглашенным) хотя бы про одну монету, какая она - настоящая или фальшивая. Решение задачи признается верным, если ответ на вопрос 1) у суда положительный, а на вопрос 2) - отрицательный. Если что-то из этого не так - решение неверно.

Попытка первая.
Адвокату надо доказать, что фальшивых монет не две, а три? Поступим за него так: разложим все монеты на 6 кучек (кучки A,B,C,D по 20 монет и кучки E,F по 10), причем в  кучки A,C,E положим по одной фальшивой монете. Тремя взвешиваниями сравним A с B, C с D, E с F. В результате каждого взвешивания получим неравенство. Значит, в каждом из взвешиваний была одна фальшивая монета. Поскольку ни одну монету мы не клали на весы дважды, то  мы (действуя за адвоката) доказали, что число фальшивых монет не может быть равно 2. Значит, оно равно 3.

Разбор попытки. Да, действительно, такие взвешивания докажут суду, что фальшивых монет именно 3. Однако являются ли они шаповаловскими? Нет, потому что в результате суд выясняет не только то, сколько фальшивых монет, но и то, что они лежат в кучках A,C,E. А это значит, что все монеты из B+D+F - заведомо настоящие. Получается, что мы разгласили информацию сразу про 50 настоящих монет! Никуда не годится...

Попытка вторая.
Кладем по 50 монет на каждую чашу. Весы в неравновесии (например, левая чаша легче). Потом с обеих чаш изымаем равные количества монет - весы приходят в равновесие. Кладем назад изъятые монеты и изымаем какие-то другие - весы показывают неравновесие в другую сторону (правая чаша легче). Следовательно, в исходном взвешивании на правой чаше есть хотя бы одна фальшивая монета, а на левой их больше. Значит, всего фальшивых монет не менее чем 1+2=3.

Разбор попытки. Давайте и здесь введем обозначения. Вначале на весах было неравенство A+B < C+D. Во втором взвешивании мы сняли с весов группы A и C и получили равенство B=D.  Такой результат возможен в трех случаях: 1) все фальшивые монеты - в группе A; 2) две фальшивые монетки в A, а одна в C; 3) в группах A, B и D по одной фальшивой, а в C все настоящие. Пока что никакого разглашения не произошло: в каждой из четырех групп могут быть фальшивые монеты, значит, ни про одну монету мы не можем точно сказать, что она не фальшивая (а тем более мы не можем сказать, что она не настоящая). В случаях 2) и 3) фальшивых монет не две, а три, поэтому дальше адвокату достаточно исключить случай 1). Но как только он сделает описанное выше третье взвешивание, он должен будет снять с левой чаши весов все фальшивые монеты, а значит, все остающиеся там монеты будут заведомо настоящими. Увы, и здесь третье взвешивание оказалось не шаповаловским.

Попытка третья.
Разложим все 100 монет в 4 группы (A,B,C,D), содержащие 10,20,30 и 40 монет соответственно. Убедимся, что A+C весит больше, чем D и что B+C весит больше, чем A+D. Заметим, что распределение фальшивых монет по группам может быть и (1,0,0,2), и (0,1,0,2), и (0,0,1,2), поэтому в каждой из групп может быть фальшивая монета - никакого разглашения не произошло!

Разбор попытки. Да, разглашения действительно не произошло. Однако при указанных взвешиваниях не исключен и вариант (0,0,0,2) - а в нем всего две фальшивых монетки. То есть суду пока еще ничего не доказано...

Что же делать?
Задача выглядит неприступной. Либо адвокат каким-то образом ухитряется исключить случай двух фальшивых монеток (но тогда разглашаем информацию о настоящих), либо выясняется, что разглашения не произошло, но и ничего не доказано.
Вот если бы общее число монет было не 100, а, например, 90... Тогда можно было бы просто разбить их на три равные кучи A,B,C по 30 монет (в каждую кучу положив по одной фальшивке) и двумя взвешиваниями убедиться, что A=B=C. Тогда и доказательство налицо, и разглашения не случилось. Однако у нас не 90 монет, а 100 - и лишние 10 штук очень мешают.

Решение первое.
Берем три группы A,B,C из 32 монет и двумя взвешиваниями проверяем, что A=B=C. Следовательно, если 2 монеты фальшивые, ни в одной из групп этих монет нет. Оставшиеся  4 монеты (W, X, Y, Z) дополняем до таких трехмонетных кучек: D = W + X + одна монета из А, E = Y + две монеты из B, F = Z + две монеты из C. Взвешиваем D=E=F. Поскольку в группах D,E,F должны находиться все 2 фальшивые монеты, получаем противоречие. Следовательно, фальшивых монет три. При этом где именно находятся фальшивые монеты, неизвестно: они могут быть либо все в группе (W,X,Y,Z), либо все - в добавленных пяти монетах, либо все - в остальных 91 монетах.

Первое решение очень удачно: оно легко обобщается на любое исходное число монет. Однако  оно оставляет ощущение, что шаповаловские взвешивания должны в результате обязательно давать равновесие. Так ли это на самом деле? К счастью, нет.

Решение второе.
Разбиваем монеты на группы A, B, C, D, E. В группах А и В - по 48 монет, в С - 2 монеты, D и E - по одной монете. Проверяем, что A+D=B+E и D+E=C. В результате суду стало ясно, что либо 1)  в A и B по одной фальшивой монете, а в C,D,E фальшивых монет нет, либо
2) в A+D, B+E и C по одной фальшивой монете, причем одна из монет D и E - фальшивая.
Чтобы отсечь первый случай, проводим третье взвешивание: кладём на одну чашу весов C+D+E, а на другую - любые 4 монеты из оставшихся. Вторая чаша перевесила. Суд убедился, что первый случай невозможен.
Почему проведенные взвешивания являются шаповаловскими? Потому что возможно как распределение фальшивых монет по группам A-E (1,0,1,0,1), так и распределение (0,1,1,1,0), то есть в каждой из групп может быть фальшивая монета. При этом в группе C две монеты, так что какая из них фальшивая, а какая настоящая, суд так и не узнал.

Решение третье.
Разделим монеты на 4 группы A-D по 25 монет. Убедимся, что A+B < C+D, а A+D > B+C. Если бы фальшивых монет было две, то из этих взвешиваний следует, что они оба раза оказывались на легкой чаше весов, то есть обе они находятся во множестве B. Чтобы доказать, что это не так, вытащим из B одну монетку X, из A - одну монетку Y, а из C - две монетки Z и W. Убедимся, что Y+D = Z+W + остальные монеты из B (на языке множеств "остальные монетки" записываются с использованием операции разности множеств - B\X). Это равенство было бы невозможным, если бы в B были обе фальшивых монеты - тогда в B\X оставалась бы еще одна... Таким образом, адвокат доказал суду, что фальшивых монет три. Однако  любая монета по-прежнему может быть фальшивой: распределение фальшивых монет по семи множествам (A\Y, Y, B\X, X, C\(Z+W), Z+W, D) может быть любым из следующих: (1,0,0,1,1,0,0), (0,1,1,0,1,0,0), (0,0,1,1,0,0,1), (0,1,0,1,0,1,0). Иначе говоря, каждая из монет X, Y, Z, W быть как настоящей, так и фальшивой, и каждое из множеств A\Y, B\X, C\(Z+W), D может как содержать, так и не содержать фальшивую монету.

Решение четвертое (авторское).

Разделим все монеты на группы A, B, C, A', B', C', A", B", C" так, чтобы были равновесия A+B = A'+B' = A"+B" и A+С = A'+С' = A"+С". Из этих взвешиваний судья сделает вывод, что в каждой из групп A+B+C, A'+B'+С', A"+B"+C" есть фальшивка. Разглашения при этом нет: по монете может быть в тройке без штрихов, или в тройке с одним штрихом, или в тройке с двумя штрихами. Численности легко подбираются неравными, например A", B, B', C, C' по 12, остальные по 10 монет.

Развитие сюжета (задачи для самостоятельного решения)
1. Придумать обобщения решений 3 и 4 на другое количество монет.
2. Пусть у адвоката и суда не 100 монет, а N (N>3). Для каких значений N адвокат сможет проделать необходимые шаповаловские взвешивания?
3. Пусть в условии по-прежнему 100 монет, однако из них либо 2, либо 3, либо 4 монеты фальшивы (а адвокат знает, что на самом деле их 3 и должен это доказать). Убедитесь, что для этого варианта задачи не проходит ни одно из решений 1-4. Придумайте правильное решение.
4. Пусть адвокат знает, что фальшивых монет ровно 10 (из 100), и хочет доказать это суду  (а суд ничего не знает о числе фальшивых монет). Как ему действовать?
5. На какие еще количества фальшивых монет можно обобщить предыдущую задачу?
6. Как действовать адвокату, если суду известно, что фальшивых монет 6 или 7 (из 100), а на самом деле их 7?

29.08.2009 - PS после публикации Тани Ховановой.
Я показал эту статью Татьяне Ховановой. Таня поместила в своем блоге рассказ об этом сюжете, дополнив его важным и очень интересным вопросом о минимизации "коэффициента разглашения": http://blog.tanyakhovanova.com/?p=160
Коэффициентом разглашения Таня назвала отношение числа ИСКЛЮЧЕННЫХ случаев к общему числу случаев. Например, в четвертом решении для |A"|=|B|=|B'|=|C|=|C'|=12 и |A|=|A'|=|B"|=|C"|=10 число оставшихся случаев равно 22×22×22, общее число случаев равно числу сочетаний из 100 по 3, поэтому коэффициент разглашения равен (161700-10648)/161700=0,934. Разумеется, это не лучший возможный вариант. А какой лучший? Я пока не знаю.