| Re: Задача про 13 монет ID:32728 ответ на 32727 |
Вт, 7 апреля 2009 16:09 [#] |
|
|
Двенадцать монет
Автор: Константин Кноп
Опубликовано в журнале "Компьютерра" №51 от 22 декабря 1997 года
Увы, мне так и не дали "спрятаться" за книги, в которых решена эта задача: около десятка читателей попросили сообщить решение, а некоторые даже отказались верить, что это решение существует.
Для начала напомню саму задачу.
Задача 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 (соответственно, нули и двойки в младшем разряде) и записываем третью цифру.
Мы получили три цифры - иначе говоря, трехзначное число. Далее определяем фальшивую монету по следующему рецепту:
Если это число совпадает с номером какой-то монеты, то эта монета фальшивая и тяжелее остальных.
Если нет, то заменим в этом числе все нули на двойки, а все двойки на нули. После этого оно должно совпасть с номером какой-то монеты. Эта монета фальшивая и легче остальных.
Для доказательства того, что этот рецепт верен, рассмотрим две таблицы.
В первой из них исследуем случай, когда фальшивая монета тяжелее настоящих. На пересечении строки "номер взвешивания" и столбца "номер монеты" запишем ту цифру, которая окажется выписанной на бумажке при этом взвешивании, при условии, что фальшивой окажется именно эта монета. 001 010 011 012 112 120 121 122 200 201 202 220
1-е взве-
шивание 0 0 0 0 1 1 1 1 2 2 2 2
2-е взве-
шивание 0 1 1 1 1 2 2 2 0 0 0 2
3-е взве-
шивание 1 0 1 2 2 0 1 2 0 1 2 0
Например, если фальшивой является монета 112, то в первом взвешивании будет записана 1, поскольку эта монета во взвешивании не участвовала, поэтому чашки весов будут в равновесии. Легко видеть, что в этой табличке цифры в каждом столбце совпадают с тем числом, которое записано в верху столбца.
Во второй табличке исследуем случаи, когда фальшивая монета легче настоящих: 001 010 011 012 112 120 121 122 200 201 202 220
1-е взве-
шивание 2 2 2 2 1 1 1 1 0 0 0 0
2-е взве-
шивание 2 1 1 1 1 0 0 0 2 2 2 0
3-е взве-
шивание 1 2 1 0 0 2 1 0 2 1 0 2
Если к столбцам этой таблицы применить наш рецепт (замену нулей на двойки и наоборот), то снова получим число, записанное в верху столбца. Это и означает, что наш рецепт верен и годится для определения фальшивой монеты во всех возможных случаях.
Задача 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
Из пяти монет три настоящие, одна фальшивая легкая и одна фальшивая тяжелая. Фальшивые монеты вместе весят столько же, сколько две настоящие. Можно ли за три взвешивания на двухчашечных весах определить обе фальшивых монеты? Если да, то как это сделать?
|
|
|