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

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

Задача имеет решение, но оно будет актуально только для весов с достаточно вместительной чашей для взвешивания.

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

• из первого мешочка одна монета
• из второго мешочка две монеты
• из третьего мешочка три монеты
• из четвертого мешочка четыре монеты
• из пятого 5 монет
• из шестого 6 монет
• из седьмого 7 монет
• из восьмого 8 монет
• из девятого 9 монет
• из десятого десять монет

Итого у нас будет: 1+2+3+4+5+6+7+8+9=45 монет

Выкладываем их, не смешивая между собой, на чашу весов. Полученный вес в граммах сообщит нам в каком мешочке лежали фальшивые монеты. Если бы все монеты являлись настоящими, то на весах у нас должно было быть 45*10=450 грамм, любое отклонение в граммах укажет нам номер мешочка с фальшивками.

• 449 грамм — фальшивые монеты в первом мешочке
• 448 грамм — фальшивые монеты во втором мешочке
• 447 грамм -фальшивые монеты в третьем мешочке
• 446 грамм — фальшивые монеты в четвертом мешочке
• 445 грамм — фальшивые монеты в пятом мешочке
• 444 грамм — фальшивые монеты в шестом мешочке
• 443 грамма — фальшивые монеты в седьмом мешочке
• 442 грамма — фальшивые монеты в восьмом мешочке
• 441 грамм — фальшивые монеты в девятом мешочке
• 440 грамм — фальшивки в десятом мешочке

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

Решение
Для удобства пронумеруем монеты от 1 до 12.

Первым взвешиванием сравним две группы по четыре монеты: 1, 2, 3, 4 и 5, 6, 7, 8.

Случай I: первое взвешивание показало равенство
Если весы покажут равенство, то фальшивая монета находится среди оставшихся четырёх монет. Тогда вторым взвешиванием мы сравним три монеты 9, 10, 11 с заведомо настоящими 1, 2, 3.

Если и в этот раз весы покажут равенство, то фальшивка — монета номер 12, и третьим взвешиванием мы сравним её с настоящей и узнаем, легче она или тяжелее.

Если же три монеты 9, 10, 11 оказались легче (тяжелее), то третьим взвешиванием сравним друг с другом монеты 9 и 10. Если они равны, то монета 11 — фальшивая, и она легче (тяжелее) настоящей. Иначе заключаем, что из монет 9 и 10 фальшивая та, которая легче (тяжелее) другой.

Случай II: первое взвешивание показало неравенство
Теперь предположим, что первое взвешивание показало, что монеты 1, 2, 3, 4 тяжелее, чем 5, 6, 7, 8. Случай, когда первые монеты оказались легче, симметричен.

Во втором взвешивании на одну чашу поместим монеты 1, 2, 5, а на другую — монеты 3, 4, 9 (монета 9 — заведомо настоящая).

Если второе взвешивание показало равенство, то у нас остаются три монеты 6, 7, 8, одна и которых легче остальных. Третьим взвешиванием сравниваем монеты 6 и 7. Если они равны, то монета 8 легче остальных. Иначе фальшивой является та, которая легче другой.

Теперь предположим, что во втором взвешивании монеты 1, 2, 5 оказались тяжелее, чем 3, 4, 9. Это означает, что фальшивка находится среди монет 1 и 2, причём она тяжелее остальных. Сравнив в третьем взвешивании эти две монеты друг с другом, мы определим фальшивую.

Предположим, что во втором взвешивании монеты 1, 2, 5 оказались легче, чем 3, 4, 9. Это означает, что либо монета 5 легче остальных, либо одна из монет 3 и 4 тяжелее остальных. Третьим взвешиванием мы сравним друг с другом монеты 3 и 4 и найдём ответ.

Категория: Логические задачи с ответами и решением