Двенадцать монет

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

Для начала напомню саму задачу.

Задача 1

Из двенадцати монет одиннадцать настоящих, а одна фальшивая (она отличается по весу от настоящей, но не известно, в какую сторону). Требуется за три взвешивания на двухчашечных весах без гирь найти фальшивую монету и выяснить, легче она или тяжелее настоящей.

Я расскажу о способе взвешивания, восходящем, по-моему, к Мартину Гарднеру (я пишу "по-моему", потому что не смог разыскать точную ссылку). Во-первых, специальным образом пронумеруем монеты: присвоим им трехзначные номера 001, 010, 011, 012, 112, 120, 121, 122, 200, 201, 202, 220.

Для первого взвешивания положим на одну чашу весов те монеты, у которых старший разряд равен 0 (то есть 001, 010, 011, 012), а на другую - те монеты, у которых он равен 2 (200, 201, 202, 220). Если перетянет чашка с "0", запишем на бумажке цифру 0. Если перетянет "2" - запишем 2. Если чаши весов останутся в равновесии - запишем 1.

Для второго взвешивания на одну чашу выложим монеты 001, 200, 201, 202 (то есть все те монеты, у которых второй разряд равен 0), а на другую - 120, 121, 122, 220 (то есть те монеты, у которых средний разряд равен 2). Запишем результат взвешивания таким же образом, что и при первом взвешивании.

Третьим взвешиванием сравниваем 010, 020, 200, 220 с 012, 112, 122, 202 (соответственно, нули и двойки в младшем разряде) и записываем третью цифру.

Мы получили три цифры - иначе говоря, трехзначное число. Далее определяем фальшивую монету по следующему рецепту:

1. Если это число совпадает с номером какой-то монеты, то эта монета фальшивая и тяжелее остальных.
2. Если нет, то заменим в этом числе все нули на двойки, а все двойки на нули. После этого оно должно совпасть с номером какой-то монеты. Эта монета фальшивая и легче остальных.

Для доказательства того, что этот рецепт верен, рассмотрим две таблицы.

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

Например, если фальшивой является монета 112, то в первом взвешивании будет записана 1, поскольку эта монета во взвешивании не участвовала, поэтому чашки весов будут в равновесии. Легко видеть, что в этой табличке цифры в каждом столбце совпадают с тем числом, которое записано в верху столбца.

Во второй табличке исследуем случаи, когда фальшивая монета легче настоящих:

Если к столбцам этой таблицы применить наш рецепт (замену нулей на двойки и наоборот), то снова получим число, записанное в верху столбца. Это и означает, что наш рецепт верен и годится для определения фальшивой монеты во всех возможных случаях.

Задача 2

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

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

Тот же алгоритм взвешиваний применим и в общем случае, а именно: за N взвешиваний удается определить фальшивую монету и узнать про нее, легче она или тяжелее, среди (3N-3)/2 монет. А если требуется только обнаружить фальшивку, то можно взять и на одну монету больше, то есть (3N-1)/2. Самое сложное - понять, как нужно нумеровать монеты.

Оказывается, номерами монет должны быть числа вида 0…01* (любое количество нулей, затем единица и далее любая комбинация цифр 0, 1, 2), числа вида 1…12* и числа вида 2…20*. Соответственно, не используются числа 0…02*, 1…10* и 2…21*, а также три числа 0…0, 1…1 и 2…2, состоящие из одинаковых цифр. Поскольку всего троичных чисел 3N, а используемых номеров на три меньше, чем неиспользуемых, то отсюда несложно подсчитать общее число номеров, которые можно использовать - их ровно (3N-3)/2.

Постскриптум

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

Ну и напоследок - несколько серьезных задач на эту же тему.

Задача 3

У вас имеется куча монет и счетчик Гейгера. Две монеты в куче являются радиоактивными. Вы можете выбрать любое подмножество монет и поднести к ним счетчик (назовем такую процедуру замером). Если среди них есть хотя бы одна радиоактивная монета, счетчик обнаружит это. Требуется определить обе радиоактивных монеты за N замеров. Для какого наибольшего числа монет в куче это всегда можно сделать? Как именно нужно отбирать замеряемые подмножества монет?

Задача 4

Та же задача, но нужно за N замеров обнаружить хотя бы одну из радиоактивных монет. Как это сделать?

Задача 5

Рассмотрите две предыдущие задачи, если радиоактивных монет не две, а три, четыре, …

Задача 6

Из пяти монет три настоящие, одна фальшивая легкая и одна фальшивая тяжелая. Фальшивые монеты вместе весят столько же, сколько две настоящие. Можно ли за три взвешивания на двухчашечных весах определить обе фальшивых монеты? Если да, то как это сделать?