[sweet_peach_lover]

Есть 13 монет, из них 12 подлинных и 1 фальшивая. Фальшивая монета отличается от подлинных по весу, но неизвество тяжелее или лечге она.

Определить за 3 взвешивания фальшивую монету, используя медицинские весы. (Т.е. весы показывают больше-меньше-равно).

[lozi17]

Двенадцать монет
Автор: Константин Кноп
Опубликовано в журнале "Компьютерра" №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

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

[sweet_peach_lover]

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

Есть более красивый и простой алгоритм решения для 13 монет.

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

У него есть только весы и 13 монет. Т.е. никаких чернил нет, и если вздумает еще каким-то образом испортить золотые монеты, получит люлей.

Это задача в свое время была задана моей подруге преподом на лекции.
Решивший до конца пары получал зачет автоматом.
Зачет автоматом никто не получил.

Тогда потратил вечер на задачу и утром добил.
После принимал ставки 2-1, что в течении 2 часов никто не решит.

Попробуйте решить сами. Это задача на логику, а не кто быстрее найдет решение в интернете

[Plato]

spl:
Ээ... вообщем я I-net не мучал, но мне кажется что это можно сделать за три взвешивания. первое определяет стремную монетку в приближении. второе и третье призваны определить сторону отклонения веса стремной монетки.
я в правильную сторону думаю?

[sweet_peach_lover]

2 Plato
Абсолютно верно, что можно определить за 3 взвешивания.
Нужно стремиться получить максимальное кол-во информации за счет вариантов со взвешивания.
Может получаться так, что фальшивую монету даже не трогали.
Если твои рассуждения приводят к фальшивой монете, то однозначно в правильную

Сколько монет кладешь на весы при первом взвешивании?

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

Алгоритм пока сохраню, т.к. во многом основан на идеях решения для задачи с 13 монетами.

Задачи 3,4,5 не очень понравились, так как не хочется возиться с радиоактивными монетами.

[LeGenDarY]

Хм. За 4 взешивания вообще изи. А за 3 надо думать...

[Warawiy]

1-ое взвешивание-1,2,3,4 и 5,6,7,8.Далее возможны 2 варианта.

1 вариант-1,2,3,4=5,6,7,8(1-8монеты не фальшивые).
Тогда фальшивая монета в оставшихся 5.
2-ое взвешивание-1,2,3 и 9,10,11.Если 1,2,3=9,10,11,то 3-е взвешивание-1 и 12(не равны фальшивка 12,равны-13).Если не равны,то 9,10,11 тяжелее(легче),чем 1,2,3, а следовательно фальшивка тяжелее(легче) настоящей.Тогда 3-е взвешивание 9 и 10.Если 9 тяжелее(легче) 10,то 9 фальшика.Если 10 тяжелее(легче) 9,то 10 фальшика.Если равны,то 11.

2 вариант-пусть для простоты 1,2,3,4>5,6,7,8.(9-11-не фальшивки)
Тогда 2-ое взвешивание 1,2,3,5,6 и 9,10,11,12,13
Если 1,2,3,5,6 = 9,10,11,12,13,тогда 3-е взвешивание-4,7 и 9,10(если 4,7>9,10-фальшивка 4,если 4,7<9,10-фальшивка 7,если равны-фальшивка 8).
Если 1,2,3,5,6>9,10,11,12,13(аналогично рассматривается вариант,когда 1,2,3,5,6<9,10,11,12,13),тогда фальшивка 1,2,3,причем фальшивка тяжелее.3-е взвешивание будет 1 и 2(1>2-фальшивка1,1<2-фальшика 2,1=2-фальшика 3).

Вроде ничего не напутал.

[again]

Старая хорошая задачка. Очень элегантное решение представлено здесь: [Зарегистрироваться?]

Я его запомнил по фразе "Ma do like me to find fake coin" =)

[Roses]

ну так это же бинарный поиск обычный

[sweet_peach_lover]

Warawiy, все верно.
Хотя у меня другое решение было.

Решение для шестой задачи:
Обозначим монеты 1,2,3,4,5
Взвешиваем монеты 1,2 и 3,4

1-ый случай.
1,2=3,4, тогда второе взвешивание 1 и 2.
Если 1=2, тогда фальшивые монеты 3,4, на третьем взвещивании берем подлинную 1 и 3, если 1>3, тогда 4 тяжелее 3.
Если 1>2, тогда фальшивые монеты 1,2, на третьем взвещивании берем 1 и подлинную 4, если 1>4, тогда 1 тяжелее 2.

2-ой случай.
1,2<3,4 (аналогично будет, если 1,2>3,4), тогда второе взвещивание 1,3 и 2,4

а)
1,3<2,4 => монеты 3,2 - подлинные.
Третье взвешивание 1,4 и 3,5
Если 1,4=3,5, тогда 1,4 фальшивые, 4>1.
Если 1,4<3,5, тогда 1,5 фальшивые, 5>1.
Если 1,4>3,5, тогда 4,5 фальшивые, 4>5.

б)
Для 1,3>2,4 подлинные монеты будут 1,4, и далее аналогично.
Третье взвешивание 3,2 и 1,5
Если 3,2=1,5, тогда 3,2 фальшивые, 3>2.
Если 3,2<1,5, тогда 2,5 фальшивые, 5>2.
Если 3,2>1,5, тогда 3,5 фальшивые, 3>5.

[Plato]

Вот сразу видно, что здесь только один монах 17-го века - я.
Остальные развращены элементарной математикой и прочей комбинаторикой.
А задача на самом деле из разряда детских несчетных блинов)))