Первый этап. Пусть число монет m = ½(3n – 3)

Пусть число монет m = ½(3 ⁿ – 3).

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

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

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

Заметим, что число пар маркеров как раз равно общему числу монет m. Перенумеруем монеты номерами от 1 до m и произвольно сопоставим каждой монете одну пару маркеров. Например, 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,..., n) на левую чашку весов кладутся все монеты множества M (i,0), на правую чашку — все монеты множества M (i,2). Результат каждого взвешивания будем обозначать цифрой 0, если перевесила левая чашка весов, цифрой 1, если обе чашки имеют одинаковый вес, и цифрой 2, если перевесила правая чашка (см. рис.). Результат i -го взвешивания обозначим через l_i.

Из цифр l ₁, l ₂,..., l_n составим маркер ³

l = l ₁ l ₂... l_n.

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

Действительно, посмотрим, что происходит, когда производится i -e взвешивание. В результате этого взвешивания весы либо остались в равновесии, либо одна из чашек перевесила.

Если весы остались в равновесии, то фальшивой монеты на них нет, следовательно, она — в множестве 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 ₁ l ₂... l_n есть маркер фальшивой монеты, притом правый в случае более тяжёлой монеты и левый — в случае более лёгкой, что и требовалось доказать.

Интересно отметить, что тип монеты, как правило, определится раньше, чем произведены все взвешивания, — как только в процессе формирования маркера 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).