Как найти 100 фальшивых монет

Может использовать метод половинного деления. Это так сказать решение в лоб. Конечно, можно найти более оригинальное и красивое. Но тем не менее.Разделить эти 100 монет на две кучки. И положить на весы. Если кучки одинаковые по массе, то получается, что монет фальшивых точно две. И они попали по одной в каждую кучку. Тогда взять первую, например, кучку, и опять ее разделить на две равные кучки. И снова взвесить. Взять ту кучку,которая легче. Из нее убрать одну монету. Оставшиеся 24 монеты снова разделить на две кучки и снова взвесить. Если кучки равные по массе, то получится, что та монета, которую мы убрали и есть фальшивая. Итак одну нашли. Осталось те же манипуляции провести с другой кучкой, в которой 50 других монет.

Если же кучка одна получилась меньше по массе чем вторая, то ее берем и снова делим. Получится по шесть монет. Снова взвешиваем. Выбираем снова ту, которая меньше весит. Теперь шесть монет делим на две кучки. Снова взвешиваем и выбираем ту, которая меньше весит. Осталось три монеты. Убираем одну. Оставшиеся две взвешиваем. Если они равны, то та, которую убрали и есть фальшивая. Если же одна весит меньше, чем другая, то она фальшивая.

Потом берем вторые 5 монет и делаем тоже самое. И найдем вторую фальшивую монету.

Если же изначально одна из кучек из 50 монет меньше другой, то фальшивые монеты в ней. Её выбираем и проводим все те же действия. Единственное, что в конце, когда останется две монеты, то может оказаться, что мы сравниваем между собой две фальшивые монеты, то для контроля надо еще провести одну взвешивание с какой-нибудь монетой, которую мы уже отбросили.

Тут получается, сто достаточно за 13 взвешиваний точно определить фальшивые монеты.

Вот у меня такое решение получилось.

Для случая с сотней монет доказательство того, что меньше чем за 70 взвешиваний гарантированно определить настоящую не получится, аналогично разобранному в решении случаю (и для любого другого числа монет все тоже аналогично), но немного сложнее. Точно так же выбирается специальный набор монет, с которым любой алгоритм взвешивания не справится быстрее, чем написано в решении. Таких наборов много. Подойдет, например, такой: все настоящие монеты весят по 2¹⁰⁰, а i-я фальшивая весит m_i = 2¹⁰⁰ + 2ⁱ. Аналогично решению показывается, что имеет смысл класть только одинаковое число монет на чашки весов и что перевешивать будет чашка с самой тяжелой (и имеющей наибольший номер) монетой. Пусть нумизмату это все даже известно. Допустим, что у него все-таки есть алгоритм, который позволит за 69 действий определить настоящую монету.

Итак, пусть нумизмат действует по своему алгоритму. Рассмотрим Соперника, который сообщает нумизмату результаты взвешиваний и одновременно присваивает некоторым монетам массы m_i, начиная с m₇₀ и последовательно уменьшая индекс i. При этом Соперник действует по собственному алгоритму:
1) если на весах уже есть монета с присвоенной массой, то из всех таких монет Соперник выбирает массу с наибольшим номером и сообщает, что чаша с этой массой перевесила;
2) если на весах нет монет с присвоенной массой, то Соперник выбирает любую монету, присваивает ей очередную массу и сообщает, что чаша с этой массой перевесила.

Так как этот алгоритм полностью согласуется с доказанным выше свойством «чаша с наибольшим номером монеты всегда тяжелее», то он не приведет ни к каким противоречиям.

После 69 проведенных взвешиваний присвоенными окажутся не более 69 масс. В частности, масса m₁ точно не присвоена, и такую массу может иметь любая из монет, которой еще не присвоена масса. Иначе говоря, любая из остальных монет может оказаться фальшивой. Следовательно, после 69 взвешиваний нумизмат не сможет указать гарантированно настоящую монету, что и требовалось доказать

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

Пример 1
За какое наименьшее число взвешиваний можно найти самую легкую и самую тяжелую из 100 монет различной массы?

Ответ в этой задаче равен 148, и алгоритм действий хорошо известен:
1) 100 монет разбиваются на пары и сравниваются монеты в каждой паре друг с другом — это 50 взвешиваний;
2) Среди 50 более тяжелых монет ищется самая тяжелая — это еще 49 взвешиваний;
3) Среди 50 более легких монет ищется самая легкая — это еще 49 взвешиваний.

Итого 50 + 49 + 49 = 148.

Докажем, что быстрее невозможно. Рассмотрим Соперника, который действует против любого Алгоритма взвешиваний следующим образом. Соперник помечает знаком «+» каждую монетку, которая может оказаться самой тяжелой, и знаком «−» каждую монетку, которая может быть самой легкой. Вначале каждая монетка помечена дважды, то есть всего есть 200 пометок. В конце пометка «+» должна остаться всего у одной монеты, и пометка «−» тоже должна остаться только одна. Значит, по ходу действия алгоритма должны быть стерты 198 пометок. Осталось разобраться, как именно Соперник их стирает. Для этого опишем действия Соперника:
(1) Если Алгоритм пробует сравнить две дважды помеченные монетки, то Соперник произвольно назначает одну из них более тяжелой и стирает у нее «−», а другую назначает более легкой и стирает у нее «+».
(2) Во всех остальных случаях Соперник действует так, чтобы стирать не более одной пометки. Например, если Алгоритм сравнивает монету с двумя пометками и монету с одной пометкой «−», то Соперник сохраняет пометку «−» у второй монеты и стирает ее у первой, то есть объявляет, что первая монета оказалась тяжелее второй.

Действий типа (1) не может быть более 50, так как каждое из них уменьшает число дважды помеченных монет на 2, а всего таких монет было 100. Действия типа (2) стирают не более одной пометки. Поскольку нам нужно стереть всего 198 пометок, а действиями типа (1) можно стереть не более 100, то требуется не менее 98 действий типа (2), а всего — не менее 148 взвешиваний.

Пример 2
Некоторые из шести людей знакомы друг с другом. Сведения о знакомствах хранятся в компьютере. За один запрос к компьютеру мы можем узнать, знакомы ли между собой два конкретных человека. Мы хотим узнать, найдутся ли среди этих людей трое попарно знакомых. Требуется доказать, что не существует алгоритма, делающего это быстрее чем за 10 запросов.

Доказательство такое. Рассмотрим за Компьютер (в данном случае он выступает в роли Соперника) такой граф знакомств: один человек — назовем его A — знаком со всеми остальными, а все остальные пары людей Соперник пока считает незнакомыми. Если Алгоритм спрашивает про знакомство А с кем-либо, Соперник отвечает «да», а если Алгоритм спрашивает про знакомство двух других людей, то Соперник отвечает «нет».

Если Алгоритм не задавал вопроса о знакомстве между B и С, а в итоге сообщил, что тройки попарно знакомых нет, то Соперник тут же объявит B и C знакомыми и предъявит контрпример, в котором такая тройка (A, B, C) есть. Если же Алгоритм не задавал такого вопроса и в итоге сообщил, что тройка попарно знакомых есть, то Соперник тут же объявит все пары, не содержащие А, незнакомыми, и тоже предъявит эту ситуацию как контрпример. Итак, чтобы контрпримера не было, Алгоритм должен запросить знакомство для всех пар (B, C), которых ровно 10, — то есть сделать не менее 10 запросов. (В данном случае мы не обещаем, что и 10 запросов хватит, поскольку не предъявляем никакого подходящего алгоритма.)

Время на прочтение
3 мин

Количество просмотров 204K

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

Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:

1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.

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

1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1.

Некоторое время назад, я на Хабре уже описывал решение такой задачи, но в одном из комментариев было замечание о немного странном первом разделении монет, по-этому предлагаю другой алгоритм решения. Хотя результат будет тот же и формула решения задачи остается та же:

N >= log₃A,

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
A — количество монет.
Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.)

Сам алгоритм решения простой, и я покажу его на примерах

1) Пусть у нас есть 26 монет. Нужно найти одну, которая легче/тяжелее

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

A = 2 * B + C,

где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону;
C — остаток.

По условию задачи

26/3 = 8.666(6),

26 = 2 * 9 + 8,

При первом взвешивании будут сравниваться две группы: правая (ПГ) — 9 монет и левая (ЛГ) — 9 монет.

Далее у нас возможны два варианта:

1) фальшивая монета в левой/правой группе (9 монет)
2) фальшивая монета в остатке (8 монет)

для 1 варианта следующее деление на группы будет — 9 = 2 * 3 + 3;
для 2 варианта — 8 = 2 * 3 + 2

Ну и за одно взвешивание можно определить какая из 2 или 3 монет легче/тяжелее

Этот же результат я приведу в таблице

по формуле — log₃26 =2.9656 — соответственно количество взвешиваний — 3.

еще пример:
число монет- 71. По формуле log₃71 =3.8800 — количество взвешиваний — 4. Проверяем

Ну с алгоритм решения этих задач, я думаю, понятен.

2. Теперь перейдем к задачам, в которых не известно легче монета или тяжелее.

В данном случае я предлагаю такое первое действие: разделить монеты на четыре группы, три — с максимально одинаковым количеством монет, а в четвертой группе — остаток. Причем в остатке должны быть 1 или 2 монеты. То есть при делении на 3 частное округляется до меньшего натурального числа.

A = 3 * B + C,

где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в меньшую сторону;
C — остаток.

Например, для 58-ми монет — это будет 58 = 3 * 19 + 1, для 23 = 3 * 7 + 2, для 15 = 3 * 5 + 0 и т. д.

Далее выполняем два взвешивания:
1) первая и вторая группы;
2) первая и третья группы;
и анализируем результат.
Здесь возможны четыре варианта:1, 2, 3 — это первая, вторая или третья группа отличаются по весу от двух остальных, или они равны, тогда нам повезло, так как фальшивая — в остатке. Так же два взвешивания помогают определить определить тяжелее фальшивая монета или легче. Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.

Теперь у нас есть задача: определить одну фальшивую монету из группы, которая легче/тяжелее.
Что касается формулы, то она примет следующий вид

N >= log₃B + 2,

где N — максимально необходимое количество взвешиваний, натуральное число;
B — количество монет в группе после второго взвешивания.
А если учесть, что B = A/3, где A — количество всех монет, тогда получим:

log3B = log₃A — 1,

N >= log₃A + 1

Итог:

1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле:

N >= log₃A

2) если не известно, какая фальшивая, тогда максимальное число взвешиваний определяется по формуле:

N >= log₃A + 1

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.