Второй этап. Коротко наметим метод Дайсона для случая m < ½(3n – 3)

Коротко наметим метод Дайсона для случая m < ½(3 ⁿ – 3).

Если в этом случае монетам сопоставлять маркеры произвольно, то в множествах M (i,0) и M (i,2) может оказаться разное число монет. Поступим поэтому следующим образом. Разобьём все маркеры на группы по шесть: в одну группу отнесём правые маркеры, получающиеся друг из друга циклической заменой цифр 0 → 1, 1 → 2, 2 → 0 и соответствующие им левые маркеры.

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

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

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

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

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

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

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

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

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

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