Г. Шестопал Как обнаружить фальшивую монету |
Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?
Многие из вас, наверное, уже решали эту задачу для 12 монет. На рисунке приведено одно из решений этой задачи. Трём возможным исходам первого взвешивания соответствуют три различных варианта выбора монет для второго взвешивания: на рисунке левая стрелка соответствует случаю, когда перетянула левая чашка, средняя стрелка равновесию, правая случаю, когда перетянула правая чашка. Аналогичным образом изображены девять вариантов выбора монет для третьего взвешивания. (На рисунке монеты перенумерованы, буквы Л и Т означают соответственно, лёгкая и тяжёлая.)
Характерной особенностью этого решения является зависимость выбора монет для очередного взвешивания от результата предыдущего.
Поставим теперь задачу в общем виде.
Имеется m≥3 одинаковых по виду монет. Все монеты, кроме одной, имеют одинаковый вес, а одна отличается от них по весу, но неизвестно, в какую сторону. Каким наименьшим числом взвешиваний на чашечных весах без гирь можно найти эту монету и выяснить её тип? 1
Эта задача более тридцати лет назад привлекла к себе внимание многих математиков, главным образом в Англии и США. В 1945 году в английском журнале «The Mathematical Gazette», похожем по своему направлению на «Квант», появилось решение этой задачи. Его автор Р. Л. Гудстейн впоследствии стал известным специалистом в области математической логики.
Гудстейн указал метод определения фальшивой монеты и её типа за n взвешиваний, n≥3, если число монет
(заметьте, что для трёх взвешиваний число монет не превышает двенадцати). Однако оказалось, что для n>3 его решение не является лучшим: за n взвешиваний можно выделить фальшивую монету и определить её тип из большего числа монет:
Это обнаружили независимо друг от друга сразу несколько математиков, и в следующем 1946 году тот же журнал опубликовал довольно длинный перечень их имён и разных ступеней успеха, достигнутых на поприще розыска фальшивой монеты. В этом же номере журнала напечатано самое лучшее решение решение Ф. Дж. Дайсона, будущего известного физика-теоретика.
Идея Дайсона основана на использовании троичной системы счисления: все монеты маркируются специально выбранными троичными числами маркерами, позволяющими удобно отражать ход последовательных взвешиваний. Особенно привлекательным при этом методе решения оказывается независимость выбора монет для последующего взвешивания от результата предыдущих.
В последующие годы были напечатаны другие решения этой задачи 2, а метод Дайсона был незаслуженно забыт.
Поэтому интересно рассказать о нём подробно.
Всё решение Дайсона можно разбить на два этапа.
А | Если то для выделения одной фальшивой монеты из общего числа m монет и определения её типа достаточно произвести n взвешиваний. |
Б | Если то для достижения той же цели n взвешиваний также будет достаточно. |
Рассмотрим каждый этап в отдельности.
Первый этап
Пусть число монет
Рассмотрим все
«Построим» все маркеры в пары: в одну пару «поставим» два дополнительных маркера таких, у которых цифры соответствующих разрядов в сумме составляют 2 (другими словами, дополнительными будут те маркеры, сумма которых равна
Назовём маркер правым, если в нём первая слева пара неравных цифр 01, 12 или 20. В противном случае маркер будем называть левым. Очевидно, в каждой паре дополнительных маркеров один всегда будет правым, другой левым.
Заметим, что число пар маркеров как раз равно общему числу монет m. Перенумеруем монеты номерами от 1 до m и произвольно сопоставим каждой монете одну пару маркеров. Например, 12 монет можно «замаркировать» так, как показано в таблице.
Номер монеты |
Левый маркер |
Правый маркер |
1 | 211 | 011 |
2 | 100 | 122 |
3 | 022 | 200 |
4 | 212 | 010 |
5 | 101 | 121 |
6 | 020 | 202 |
7 | 210 | 012 |
8 | 102 | 120 |
9 | 021 | 201 |
10 | 221 | 001 |
11 | 110 | 112 |
12 | 002 | 220 |
Обозначим соответственно через
Легко видеть, что число монет в каждом из множеств
Метод взвешивания монет, придуманный Дайсоном, состоит в следующем:
Производится последовательно n взвешиваний монет.
При
Из цифр l1, l2, ..., ln составим маркер 3
Оказывается, l маркер фальшивой монеты F и если l правый маркер, то F тяжелее остальных монет, а если l левый маркер, то F легче остальных монет.
Действительно, посмотрим, что происходит, когда производится
Если весы остались в равновесии, то фальшивой монеты на них нет, следовательно, она в множестве
Если одна из чашек весов перевесила, то фальшивая монета лежит на весах. Пусть, например, перевесила правая чашка, т.е.
фальшивая монета лежит на правой чашке (тогда она тяжелее остальных монет), значит, она находится во множестве
фальшивая монета лежит на левой чашке (тогда она легче остальных монет), значит, она находится во множестве
Совершенно аналогичен «симметричный» случай, когда перевесит левая чашка весов
Поэтому, действительно, сформированный в результате последовательных взвешиваний маркер
Интересно отметить, что тип монеты, как правило, определится раньше, чем произведены все взвешивания, как только в процессе формирования маркера l появятся две различные цифры.
Существенной особенностью описанного метода, как уже было отмечено раньше, является то обстоятельство, что выбор монет для каждого взвешивания не зависит от результатов предыдущих взвешиваний.
Например, для 12 монет, замаркированных так, как показано в таблице, нужно проделать такие три взвешивания: (1,4,7,10) (3,6,9,12), (3,6,9,10) (2,5,8,12), (3,4,8,12) (2,6,7,11).
Второй этап
Коротко наметим метод Дайсона для случая
Если в этом случае монетам сопоставлять маркеры произвольно, то в множествах
В каждой группе окажется по три правых маркера и три левых маркера. Группу, содержащую правые маркеры
При такой маркировке первые n1 взвешиваний производятся по старым правилам. Как производить последнее взвешивание, сообразите самостоятельно.
Метод Дайсона описан. Убедимся теперь, что он в определённом смысле является наилучшим. А именно, покажем, что если из m монет можно выделить n взвешиваниями фальшивую монету и определить её тип, то
Итак, предположим, что n взвешиваний достаточно.
Занумеруем монеты числами 1,
Аналогично, второе взвешивание рассортирует эту подозрительную группу на три подгруппы. Поэтому в наиболее многочисленной из них окажется не меньше
Но это ещё не всё! Мы не разобрались ещё со случаем
Рассмотрим более внимательно первое взвешивание. Ясно, что число бумажек, на которых написана цифра 0, равно числу бумажек, на которых написана цифра 2. Пусть тех и других по p штук, тогда на
Заметим, что p чётное число. Действительно, если на левой и правой чашке весов лежит по k монет, то
В заключение несколько задач, которые могут быть решены методом Дайсона.
1. | Очевидно, для значений m<3 задачу не имеет смысла решать: при m=1 монета будет фальшивой, но неизвестного типа; при m=2 монеты будут иметь разный вес, и выбрать из них фальшивую невозможно. назад к тексту |
2. | Например, в книге А. Яглома, И. Яглома «Вероятность и информация» (М., «Наука», 1973). назад к тексту |
3. | Докажите, что это действительно маркер, т.е. что цифры l1, |