Как найти фальшивую монету за два взвешивания

Время на прочтение
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 — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.

В каждом из 60 мешков лежит по 20 монет: в одном мешке фальшивые, весом по 9 г, а в остальных – настоящие, весом по 10 г. В нашем распоряжении весы, показывающие вес груза в граммах. Класть на весы можно не более 100 монет. Как за два взвешивания на этих весах определить, в каком мешке фальшивые монеты?

Задача была предложена на аргентинском отборе на олимпиаду Cono Sur 2014 года и потом на 45 Уральском турнире юных математиков.

Разделим 60 мешков на четыре группы 14 мешков и оставшуюся группу из четырёх мешков.

Из первой группы из 14 мешков монет для взвешивания брать не будем. Из второй группы возьмём по одной монете. Из третьей группы возьмём по две монеты. Из четвёртой группы возьмём по три монеты. Из маленькой группы возьмём по четыре монеты.

Таким образом, для взвешивания возьмём 14*0+14*1+14*2+14*3+4*4=100 монет. Если общий вес будет ровно 100*10 г, то фальшивые монеты будут в мешке из первой группы. Если до этого веса не будет хватить 1 г, то фальшивые монеты будут в мешке из второй группы и т.д.

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

Если эта группа состояла из 14 мешков, то для второго взвешивания из первого мешка этой группы возьмём 0 монет, из второго мешка – 1 монету, из третьего мешка – 2 монеты, …, из 14-го мешка возьмём 13 монет.

Всего получится, что мы возьмём 0+1+2+…+13=91 монету.

Опять же, до веса 91*10 г не будет хватать столько, сколько монет из мешка с фальшивыми монетами мы взяли. Это и определит мешок.

Как найти фальшивую монету двумя взвешиваниями – логическая задача

Загадки на логику

Похожие новости