Как за два взвешивания найти фальшивую монету из 9
Перед нами логическая задача, чтобы решить которую нужно немного пораскинуть мозгами.
Итак условия задачи следующие:
На столе лежат 9 монет. Известно, что одна из монет фальшивая. Фальшивая монета весит меньше чем остальные. У нас имеются весы для взвешивания.
Вопрос:
Как при помощи двух взвешиваний найти фальшивую монету?
.jpg)
Внимание!
Ниже приведен правильный ответ!
Правильный ответ:
Вначале на каждую чашу весов нужно положить по три монеты.
Если после этого весы приходят в равновесие, значит среди этих монет нет фальшивой, берем две из трех оставшихся монет, кладем на разные чаши весов. Если фальшивая монета среди этих двух, то мы поймем на какой она чаше, эта чаша поднимется выше.
А если весы снова придут в равновесие, значит фальшивая монета осталась на столе.
Если же при первом взвешивании весы не пришли в состояние равновесия, значит фальшивая монета уже находится на весах, берем 2 монеты из тех трех, что оказались легче, кладем по 1 на каждую чашу, если одна чаша поднялась выше, значит фальшивая монета на ней, если чаши уравновесились, значит фальшивая — оставшаяся третья.
Как за два взвешивания найти фальшивую монету из 9
У Вас 9 одинаковых монет, одна монета фальшивая, чуть легче чем остальные, возьмите чашечные весы и двумя взвешиваниями выделите фальшивку! Удачи! удача весы фальшивка монета взвешивание
Взвесить четыре на одной чашке и четыре на другой. Если фальшивая монета будет участвовать во взвешивании (что скорей всего и произойдёт по теории вероятностей), вы сразу определите, на какой чашке она находится, разделите на ней монеты по две и снова взвесьте. После этого разделите монеты (две) на лёгкой чашке и опять разложите. Лёгкая и будет фальшивая. Если же с начала чаши будут весить одинаково, значит фальшивая — та, чт о не участвовала во взвешивании
Делим монеты на две равные кучки. Из каждой кучки берем по 3 монеты, кладем на весы и взвешиваем. Если вес одинаковый то взвешиваем оставшиеся 1и 1 монеты и выявляем фальшивую (более легкую). Если же одна группа из трех монет легче другой, значит там есть фальшивая монета. Оставляем более легкую группу из трех монет и кладем на весы 1и 1 и действуем по предыдущему алгоритму: если вес одинаков, значит фальшива третья, а если нет то та которая легче.
двумя — не знаю как , а тремя вот как можно :
Разделить монеты на 3 кучки: 4 + 4 + 1
Положить на чаши весов кучки по 4 монеты, если они одинаковые, значит фальшивая та, которая одна. Если не одинаковые , то искомая монета лежит там, где кучка легче. Берем легкую кучку и делим на 2 по 2+2. Повторяеи операцию. И выбираем фальшивку из той кучки, которая при взвешивании оказалась легче.
А как 2-мя то взвешиваниями определить ?
Делим монеты на 3 группы. Взвешиваем сначала две группы. Если весят одинаково, берем отложенную группу и взвешиваем любые две монеты. Фальшивую монету определить несложно — либо та, что легче, либо, при одинаковом весе, та. что на столе. То же делаем, если взвешенные первый раз две группы весят неодинаково. Это простая задача.
Решение задач на определение фальшивой монеты взвешиванием 2.0
Сегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата.
Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:
1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.
Или обратная задача: можно ли за определенное количество взвешиваний выявить фальшивую из заданного количества монет.
1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1.
Некоторое время назад, я на Хабре уже описывал решение такой задачи, но в одном из комментариев было замечание о немного странном первом разделении монет, по-этому предлагаю другой алгоритм решения. Хотя результат будет тот же и формула решения задачи остается та же:
N >= log3A,
где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
A — количество монет.
Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.)
Сам алгоритм решения простой, и я покажу его на примерах
1) Пусть у нас есть 26 монет. Нужно найти одну, которая легче/тяжелее
Первым действием буде разделение монет на три группы, в двух из которых число монет будет одинаковым, важно только что бы в третьей группе — остатке — было меньше монет, чем в каждой из двух других групп. То есть частое округляется к большему натуральному числу. То есть
A = 2 * B + C,
где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону;
C — остаток.
По условию задачи
При первом взвешивании будут сравниваться две группы: правая (ПГ) — 9 монет и левая (ЛГ) — 9 монет.
Далее у нас возможны два варианта:
1) фальшивая монета в левой/правой группе (9 монет)
2) фальшивая монета в остатке (8 монет)
для 1 варианта следующее деление на группы будет — 9 = 2 * 3 + 3;
для 2 варианта — 8 = 2 * 3 + 2
Ну и за одно взвешивание можно определить какая из 2 или 3 монет легче/тяжелее
Этот же результат я приведу в таблице
| № взвешивания | Число монет | ЛГ | ПГ | Остаток |
| 1 | 26 | 9 | 9 | 8 |
| 2 | 8 | 3 | 3 | 2 |
| 2 | 9 | 3 | 3 | 3 |
| 3 | 2 | 1 | 1 | 0 |
| 3 | 3 | 1 | 1 | 1 |
по формуле — log326 =2.9656 — соответственно количество взвешиваний — 3.
еще пример:
число монет- 71. По формуле log371 =3.8800 — количество взвешиваний — 4. Проверяем
| № взвешивания | Число монет | ЛГ | ПГ | Остаток |
| 1 | 71 | 24 | 24 | 23 |
| 2 | 23 | 8 | 8 | 7 |
| 2 | 24 | 8 | 8 | 8 |
| 3 | 7 | 3 | 3 | 1 |
| 3 | 8 | 3 | 3 | 2 |
| 4 | 2 | 1 | 1 | 0 |
| 4 | 3 | 1 | 1 | 1 |
Ну с алгоритм решения этих задач, я думаю, понятен.
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 >= log3B + 2,
где N — максимально необходимое количество взвешиваний, натуральное число;
B — количество монет в группе после второго взвешивания.
А если учесть, что B = A/3, где A — количество всех монет, тогда получим:
log3B = log3A — 1,
N >= log3A + 1
1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле:
N >= log3A
2) если не известно, какая фальшивая, тогда максимальное число взвешиваний определяется по формуле:
N >= log3A + 1
где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.