Время на прочтение
3 мин
Количество просмотров 204K
Сегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата.
Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:
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 — остаток.
По условию задачи
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 монет легче/тяжелее
Этот же результат я приведу в таблице
№ взвешивания | Число монет | ЛГ | ПГ | Остаток |
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 — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.
Давайте идти самым простым путём.
Взвесить монеты по две. Те что тяжелее в правую кучку,а те.что легче в левую. Таких взвешиваний 34. А монет в каждой куче тоже по 34.
Теперь в куче тяжёлых монет взвешиваем монеты по две.Те монеты,что тяжелей оставляем,а те,что легче откидываем в сторону-ведь самой тяжёлой среди них быть не может. На это ушло 17 взвешиваний,а монет осталось 17. Тоже самое делаем с кучей лёгких монет.
От оставшихся 17 тяжёлых отделяем одну любую и взвешиваем 16 оставшихся монет по тому же алгоритму.То есть взвешиваем за 8 взвешиваний затем за 4,затем за 2,затем с учётом откинутой семнадцатой опять за два. При этом всё время откидываем более лёгкие монеты. Находим самую тяжёлую,и ушло на это 16 взвешиваний.
По тому же пути из кучки лёгких монет находим самую лёгкую,только при этом откидываем более тяжёлые монеты.На это уходит 16 взвешиваний.
Теперь проверим общее количество взвешиваний: 34+17+17+16+16=100
Ответы
Ray Alex
разделим монеты на 3 кучи по 3 монеты в каждой
1взвешивание : Ввзвесим 1 и 2 кучу. Если они равны, то монета в 3-й куче.
Сразу переходим ко 2-му взвешиванию монет 3-й кучи.
Если они не равны, возмем ту кучу, которая весит меньше и переходим ко 2-му взвешиванию
2 взвешивание Возьмем 2 монеты из выбранной кучи( см 1 взвешивание) и взвесим.
Если монеты весят одинаково, то фальшивая монета — оставшаяся.
Если они весят не одинаково, то та монета, которая весит меньше будет фальшивой.
St
Stern
Если на чашечных весах, то делим на три кучки по три шара. Взвешиваем две из них. Если одна тяжелее другой, значит искомый шар в ней, выбираем из этой кучки два шара, взвешиваем — если один шар перевесил, значит это он, если оба шара одинаковые, значит тяжелее тот, что остался. Если первым взвешиванием обе кучки одинаковые, значит тяжелый шар в третьей кучке, применяем второй шаг взвешивания к ней.
ВМ
Виталий Майстренко
1 взвешивание: сравниваем 1 и 2 кучки,
если обе кучки равны, то монеты все настоящие, а фальшивая находится в 3 кучке
если одна кучка перевешивает, то там и находится фальшивая
2 взвешивание: сравниваем две монеты из 3-ей кучки по принципу первого взвешивания.
если обе монеты равны, то они настоящие,
если одна перевешивает, то она и есть фальшивая.
во первых даже мозг не напряг с ответом, во вторых ты захотел отличиться и полез в интернет. но даже там поленился со второго раза выделить текст с ответом… убедительно?
Ирина Кибус
Ни чего другого не придумала: сначала сравнить на весах любые 2 монеты ,если повезет, то и первого раза выявится тяжелая монета, если нет, то добавить по три монеты, чтоб весы оставались в равновесии, оставшаяся- тяжелая
Valentin Sibilev
разделить по три, и взвешать сначала 2 кучки монет и тем самым выявить в какой кучке та монета, что тяжелее а потом эту кучку разбить на отдельные монетки и взвесить две из них тем самым выявить какая тяжелее
Александр Макаров
разбиваем на 3 кучки по 3 монеты, взвешиваем произвольные две, определяем тяжелую кучку: равновесие — тяжелая не на весах, одна перевешивает — она и есть тяжелая. с тяжелой кучкой проводим ту же операцию….
Дмитрий Иванников
мужики почти все угадали. а бабы сидят какую то херь несут! такое чувство что все блондинки тупорылые
Тамара Андреева
Я не знаю правильного ответа.Но после войны мы делали битки для игры и пробовали на зуб.Та которая отличалась,была из другого металла.ЕЕ мы взвешивали с остальными и видели легче она или нет.
ЛЛ
Лана Лана
Взять по три монеты,взвесить 2 кучки,если ровно,то фальшивая в третьей,взвешиваем из той кучи по 1монете,если ровно,то третья фальшивая…..ну как то так
АШ
Алексей Шубин
Делим на три кучки, взвешиваем любые две… в вычлененной подозрительной взвешиваем две монеты. Результат найден!
RB
Rus Best
ВЗВЕШИВАЕМ ПО ТРИ МОНЕТЫ, ЕСЛИ ВЕСЫ РАВНЫЕ, ТО В ТРЕТЬЕЙ ТРОЙКЕ ВЗВЕШИВАЕМ 2 МОНЕТЫ…ВСЁ БУДЕТ ВИДНО
RB
Rus Best
из того же…..у вас 5 мешков с 5 копеечными монетами, в одном фальшивки, нормальные монеты весят 3 грамма, а фальшивка 5. как одним взвешиванием определить в каком мешке фальшивки????)))))
Kr
Kriz 0X
по три монеты с каждой стороны — 1е взвешивание. 2е — по монете из группы которая по массе не подходит.
Ирина Волкова
делим на тройки, взвешиваем две, если одинаковые, то взвешиваем монеты в третей тройке
Марина Грабарчук
сначала взвесить 4 и потом 4, сверить вес, если будет равный, то 9 монета точно тяжелее.
*N
* Nadiya
если они в каком-то сосуде, то можно потрясти и тяжелая будет в самом низу, я думаю
Грета
ну смотря какого достоинства))))))))))))) может и искать не надо))))))))))))))
M*
Marina *****
Я настолько давно изучала физику, что сразу и не сообразить….
Дмитрий Иванников
а физика тут не причем. тут из физики только весы мы взяли, остальное все логика
НВ
Ночь В Буре
я бы даже не парился над этим. хорошо что хоть монеты есть ))))))
Оля Просто
9 одинаковых? Так какие же они одинаковые, если одна тяжелее
Разминка для мозга: сможете решить задачу про фальшивую монету? Проверьте!
25 августа 2020
Отдых
Есть 12 монет, среди них одна поддельная. Помогите математику обнаружить её всего за три взвешивания.
Анастасия Сукманова
Избранное
За критику налоговой системы император заточил в темницу величайшего математика страны. Но однажды пленнику представился шанс вновь обрести свободу. Один из 12 наместников императора уплатил налог фальшивой монетой, которая уже попала в казну. Император пообещал освободить математика, если тот сумеет найти подделку.
Перед пленником поставили стол, на котором были чашечные весы, карандаш и 12 одинаковых на вид монет. А потом сказали, что фальшивка отличается от остальных денег по весу в большую или меньшую сторону. Взвесить монеты разрешили лишь трижды. Как математику вычислить подделку?
Показать ответ
Скрыть ответ
Читайте также ✅
- Сложная задачка про голубоглазых пленников, которые застряли на острове
- Задача про пленников и колпаки, цвет которых нужно определить
- Задача про тайник Леонардо да Винчи, в который не так-то легко пробраться
2000 монет |
||||||
|
||||||
|
||||||
|
||||||
|
||||||
|
||||||
|
||||||
|
||||||
|
||||||
|
||||||
|