Как обнаружить фальшивую монету

Квант 1979, №10 с. 21-25 Тег KGYW

Г. Шестомал

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

Многие из вас, наверное, уже решали эту задачу для 12 монет. На рисунке приведено одно из решений этой задачи. Тем возможным исходом первого взвешивания соответствует три различных варианта выбора монет для второго взвешивания. (На рисунке монеты переумерованы, буквы л и т ознакомятся соответственно, легкая и тяжелая.)

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

Поставим теперь задачу в общем виде.

Имеется $m \geq 3$ одинаковых по виду монет. Все монеты, кроме одной, имеют одинаковый вес, а одна отличается от них по весу, но неизвестно, в какую сторону. Каким наименьшим числом взвешивания на часовых весах безzip можно найти эту монету и выяснить ее мин? *)

Эта задача более трудится лет назад прилекла к себе внимание многих математков, главным образом:

*) Очевидно, для значений $m < 3$ задачу не имеет смысла решать: при $m = 1$ монета будет фальшивой, но неизвестного типа; при $m = 2$ монеты будет иметь разный вес, и выбрать из них фальшивую невозможно.

зом в Англии и США. В 1945 году в английском журнале «The Mathematical Gazette», пожемем по своему направлению на «Квант», появилось решение этой задачи. Его автор Р. Л. Гудстейн впоследствии стал известным специалистом в области математической логики.

Гудстейн указывает метод определения фальшивой монеты и ее типа за $n \geq 3$ взвешиваний, если число монет

$m \leq \frac{1}{2} \left( 3^n - 2n + 3 \right)$

(заметьте, что для $n = 3$ $m \leq 12$ ).

Однако оказалось, что для $n > 3$ его решение не является лучшим: за $n$ взвешиваний можно выделить фальшивую монету и определить ее тип из большого числа монеты:

$m \leq \frac{1}{2} \left( 3^n - 3 \right).$

Это обнаружили незначимую друг от друга сразу несколько математических, и в следующем 1946 году тот же журнал опубликовал довольно длинный перечень их имен и разных ступеней успеха, доступных на поршше розыска фальшивой монеты. В этом же номере журнал напечатано самое лучшее решение – решение Ф. Дж. Дайсона, будущего известного физика-теоретика.

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

В последующие годы были напечатаны другие решения этой задачи *), а метод Дайсона был незаслушен забыт.

Позному интересно расссказать о нем подробно.

Все решения Дайсона можно разбить на два этапа.

*) Налример, в книге А. Яглома, II. Яглома «Вероятность и информация» (M., «Наука», 1973).

А. Если

$m = \frac{1}{2} \left( 3^n - 3 \right), n = 2, 3, \dots,$

то для выделения одной фальшивой монеты из общего числа $m$ монет и определения ее типа достаточно произвести $n$ взвешиваний.

B. Если число монет

$m < \frac{1}{2} \left( 3^n - 3 \right), m \geq 3,$

то для достижения той же цели $n$ взвешиваний также будет достаточно.

Рассмотрим каждый этап в отдельности.

Первый этап

Пусть число монет $m = \frac{1}{2} \left( 3^n - 3 \right)$ .

Рассмотрим все $n$ -значные числа (наборы из цифр 0, 1, 2) 00 … 00, 00 … 01, …, 22 … 22. Их $3^n$ . Используем их для маркировки монет следующим образом: в качестве маркеров возьмем все числа, за исключением трех, состоящих из одинаковых цифр: 0 … 0, 1 … 1, 2 … 2.

《Построим》 все маркеры в пары: в одну пару «поставим» два дополнительных маркера – таких, у которых цифры соответствуют 2 (другими словами, дополнительными будет те маркеры, сумма которых равна 22… 22).

Назовем маркер правим, если в нем первая слава пара неравных цифр — 01, 12 или 20. В противном случае маркер будет назвать левым. Очевидно, в каждой паре дополнительных маркеров один пару маркеров. Например, 12 монет можно «замаркировать» так, как показано в таблице.

Обозначим соответствующее через $M(i, 0), M(i, 1)$ и $M(i, 2)$ множество монет, для которых $i$ -й разряд соответствующего им правого маркера равен 0, 1 или 2.

Легко видеть, что число монет в каждой из множества $M(i, 0)$ , $M(i, 1)$ и $M(i, 2)$ одинаково и что эти множества не имеют общих элементов (см., например, таблицу).

Метод взвешивания монет, придуманный Дайсоном, состоит в следующем:

Производится последовательно $n$ взвешивания монет.

При $i$ -м взвешивания ( $i = 1, 2, \dots, n$ ) на левую чашку весов кладутся все монеты множества $M(i, 0)$ , на правую чашку — все монеты множества $M(i, 2)$ . Результат каждого взвешивания будем обозначать цифрой 0, если перевесила левая чашка весов, цифрой 1, если обе чашки имеют одинаковый вес, и цифрой 2, если перевесила правая чашка (см. рис.). Результат $i$ -го взвешивания обозначим через $l_i$ .

Из цифр $l_1, l_2, \dots, l_n$ составим маркер

$l = l_1 l_2 \dots l_n^*).$

Оказывается, $l$ — маркер фальшивой монеты $F$ и если $l$ — правый маркер, то $F$ тяжелее остальных монеты, а если $l$ — левый маркер, то $F$ легче остальных монеты.

Действительно, посмотрим, что производит, когда производится $i$ -е

*) Докажите, что это действительно маркер, т. е. что цифры $l_1, l_2, \dots, l_n$ не могут быть одинаковыми.

$l_i = 0$

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

Если весы остались в равновесии, то фальшивой монеты на них нет, следовательно, она — в множестве $M(i, 1)$ . Но это означает, что $i$ -й разряд ее правого (и левого) маркера равен 1, на что и указывает результат взвешивания $l_i = 1$ .

Если одна из чашек весов пересечена, то фальшивая монета лежит на весах. Пусть, например, пересечена правая чашка, т. е. $l_i = 2$ . Этот результат возможно в двух случаях:

— фальшивая монета лежит на правой чашке (тогда она тяжелее остальных монет), значит, она находится во множестве $M(i, 2)$ , $i$ -й разряд ее правого маркера равен 2, следовательно, результат взвешивания совпадает с $i$ -м разрядом ее правого маркера;

— фальшивая монета лежит на левой чашке (тогда она легче остальных монет), значит, она находится во множестве $M(i, 0)$ , следовательно, $i$ -й разряд ее правого маркера равен 0 и результат взвешивания совпадает с $i$ -м разрядом ее левого маркера.

Совершенно аналогичен «симметричный» случай, когда пересечит левая чашка весов ( $l_i = 0$ ).

Позному, действительно, сформированный в результате последовательных взвешивания маркер $l = l_1 l_2 \dots l_n$ есть маркер фальшивой монеты, при этом правый в случае более тяжелой монеты и левый — в случае более легкой, что и требовалась dokазать.

Интересно отмечать, что тип монеты, как правило, определяется равnisse, чем произведены все взвешивания,— как только в процессе формирования маркера $l$ появятся две различных цифры.

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

Например, для 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).

Второй этап

Коротко наметим метод Дайсона для случая $m < \frac{1}{2} (3^n - 3)$ . Если в этом случае монетам сопоставлять маркеры произвольно, то в множествах $M(i, 0)$ и $M(i, 2)$ может оказаться разное число монет. Поступим поэтом следующим образом. Разобъем все маркеры на группы по шесть: в одну группу отнесем правые маркеры, получающей друг из другa циклической заменой цифр $0 \rightarrow 1$ , $1 \rightarrow 2$ , $2 \rightarrow 0$ и соответствующим им левые маркеры.

В каждой группе оказывается по три правых маркера и три левых маркера. Группу, содержащую правые маркеры $00 \ldots 01, 11 \ldots 12, 22 \ldots 20$ , выделим особо. Разобъем монеты на группы по три, пока это возможно, и замаркируем их следующим образом. Monetam из одной группы сопоставим пары маркеров из одной группы, а для остатка, если он есть, используем пары маркеров из выделенной группы. Если остается одна монета, не вошедшая в тройки, то сопоставим ей правый маркер $11 \ldots 12$ , а если две, — то правые маркеры $00 \ldots 01$ и $22 \ldots 20$ (и соответствующие левые маркеры).

При такой маркировке первые $n — 1$ взвешивания произвольется по стартим правым. Как производить последнее взвешивание, сообщите самостояльно.

Метод Дайсона описан. Убедимся теперь, что он в определенном смысле является наличием. А именно, показем, что если из $m$ монет можно выделить $n$ взвешиваниями фальшивую монету и определить ее тип, то $2m \leq 3^n — 3$ . Разумеется, мы не будем учитывать возможность «везення»: при нем для определения фальшивой монеты из любого числа монет может хватить и двух взвешивания.

Итак, предположим, что $n$ взвешивание достаточно.

Занumerем монеты чисlamи $1,2, \ldots, m$ и приготовим $2m$ бумажек. Напишем на них все возможные варианты: первый монета легче, первый монета тяжелее, второй монета легче и т. д. Ясно, что при этом все $2m$ бумажек оказывается использованным и ни один из возможных вариантов не будет упущен. Будем обозначать, как мы условиясь выше, результат взвешивания цифрами $0, 1$ или $2$ . Каждый взвешивание показывает, что часть возможных ответов не подходит, а часть — остается под подозрением. Отберем монеты для первого взвешивания. Не производя его фактически, напишем на каждой из бумажек тот результат первого взвешивания, который оставляет ее под подозрением. Ясно, что на каждой бумажке будет написана одна из цифр $0, 1$ или $2$ . Таким образом, все бумажки будут разбыты на три группы. Поэтому в наиболее многочисленной группе оказывается не меньше $2m/3$ бумажек. Значит, как бы мы ни организовывали первый взвешивание, может оказаться, что после него под подозрением останется не меньше $2m/3$ бумажек.

Аналогично, второе взвешивание рассортирует эту подозрительность группу на три подгруппы. Поэтому в наиболее многочисленной из них оказется не меньше $2m/9$ бумажек. Точно так же после $n$ взвешивания мы можем получить $2m/3^n$ подозрительные бумажки в одной группе. Следовательно, если $2m/3^n > 1$ , то фальшивая монета и ее тип, вообще говоря, за $n$ взвешивание определены быть не могут. Поэтому $n$ взвешивание достаточно, то $2m \leq 3^n$ .

Но это еще не все! Мы не разобрались еще со случайем $2m = 3^n — 1$ (четное число $2m$ не может равнять ни $3^n — 2$ , ни $3^n$ ). Для него изложенных выше сообщений недостаточно.

Рассмотрим более внимательное первое взвешивание. Ясно, что число бумажек, на которых написана цифра 0, равно числу бумажек, на которых написана цифра 2. Пусть тех и других — по $p$ штук, тогда на $2m - 2p$ бумажках будет написана 1.

Заметим, что $p$ — четное число. Действительно, если на левой и правой части весов лежит по $k$ монет, то $p = 2k$ . Если $p$ или $2m - 2p$ больше $3^{n-1}$ , то по рассмотрению для определения нужной бумажки может не хватить оставшихся $n - 1$ взвешивания. Если же $p = 2k \leq 3^{n-1}$ и $2m - 2p \leq 3^{n-1} - 1$ , то, поскольку $3^{n-1} - 1$ число нечетное, $p \leq 3^{n-1} - 1$ , $2m - 2p \leq 3^{n-1} - 1$ . Но тогда $2m = (2m - 2p) + 2p \leq 3^{n-1} - 1 + 2(3^{n-1} - 1) = 3^n - 3$ . Итак, если $n$ взвешивания достаточно, то $2m \leq 3^n - 3$ .

В заключение — несколько задач, которые могут быть решены методом Дайсона.

Список читателей, приславших правила решения задач из Задачника «Кванта»

(Начало см. на с. 7, 14)

А. Петросли (Ереван) 6а; Л. Петрусевич (дер. Козлы Минской обл.) 6; И. Пиковский (Киев) 3; А. Подвязников (Мосальск) 7; В. Подстрицан (Львов) 6, 8, 1; А. Попелохин (Киев) 6, 7; А. Попов (Москва) 7; В. Поманов (Новосибирск) 3; С. Пошехонов (Энгельс) 7; Г. Пуричамишили (Тбинис) 6а; Б. Рабинович (Тула) 6, 7, 1, 3, 4; В. Радченko (Киев) 6а, 2—4; М. Рейтман (Москва) 6а, 7, 2; С. Рехвашили (Павлодар) 6; И. Ройзман (п. г. т. Калиновка Винницкой обл.) 6—8; Н. Рубинмешин (Ленинград) 6а; Б. Рублев (Киев) 2, 3; И. Савенков (р. п. Львые горы Саратовской обл.) 6, 7; Г. Самельсон (Ленинград) 3; М. Севрюк (Москва) 6—9, 1—3; П. Селиванов (Семипалатинск) 6а, 7, 2; А. Сивацкий (Ленинград) 6а, 7, 9, 0, 2, 3; А. Смирнов (Курган) 6, 7; А. Смыслов (Коньково) 6; А. Сромин (Ленинград) 6, 7; С. Смадиниценко (Москва) 6—8, 3; Ф. Сукоев (Ташкент) 6—9; Н. Сумовский (Львов) 7, 8; О. Тавень (Минск) 6а, 7; К. Таталян (Ереван) 6; Л. Тенер (с. Ялтушков Винницкой обл.) 6, 7; К. Терехов (Рязань) 6а; В. Титенко (дер. Блужа Минской обл.) 7; А. Уливанов (Горький) 9; В. Уманский (Баку) 6, 7; Р. Ушаков (Киев) 3; Д. Файнгауз (Ленинград) 6, 7, 0; В. Фарбер (Баку) 3; А. Фамуллаев (Баку) 3; Н. Федин (Омск) 2; А. Федоров (Москва) 7, 3; О. Хоружский (Черновцы) 7; С. Хосид (Алма-Ата) 6а, 7; З. Цихистави (Телави) 3; И. Черная (Ленинград) 3; О. Чечель (Москва) 6—8, 1, 4; А. Шациян (Ереван) 7; П. Шаприн (Киев) 7; Н. Шаромет (Москва) 6, 7, 2, 4; Ю. Ширман (Харьков) 6; Г. Штерен (Орск) 6а; М. Яковлев (Кемерово) 2; А. Ялыцев (Тула) 6, 7; Л. Яновская (Харьков) 7; А. Яценко (Тбилиси) 7.

Ф и зика

Почи все читатели справились с задачими Ф 539 и Ф 542. Остальные задачи правильно решили:

В. Абиджаев (Львов) 33; Е. Александрова (Глазов) 35, 40, 41; Ю. Анисимов (Торопецкий р-н Калининской обл.) 35; А. Арбамский (Благовещенск-на-Aмуре) 40, 41; А. Базиров (с. Кировка АзССР) 40; Л. Бараз (Свердловск) 38—41; И. Баранец (п. Дзержинский Московской обл.) 38—41; А. Барзикин (п. Черноголовка Московской обл.) 33, 35—41; А. Белоусов (Калининград) 36; А. Васильев (Выру) 40, 41; Д. Виноградов (Дзержинск) 35; М. Гаврилов (п. Черноголовка Московской обл.) 35, 38—44, 47; М. Гольцман (Днепропетровск) 43, 44, 47; И. Гопчи (Новосибирск) 38, 41; В. Горпиненко (Кольчугино) 40; И. Даниловский (Горький) 33, 38; В. Дидух (Львов) 35, 37, 38, 40—44, 47; С. Довбищ (Москва) 33, 35, 38—41, 47; С. Довженко (Донецк) 34—36, 38—41; Е. Емельянов (Москва) 43, 47; А. Ермолин (Петрозаводск) 36, 38; В. Жордочки (Орск) 38; А. Журавлев (Ленинград) 38—41; Э. Зерныш (п. Кузьмовка Ленинградской обл.) 40, 41; Е. Зудин (Александров) 34, 35, 37, 40, 41—44, 46; С. Зуев (п. Черноголовка Московской обл.) 40; А. Иоваша (Окончание см. на с. 38)