Есть 101 монета. Все они одинаковы на вид. Но при этом известно, что ровно одна монета является фальшивой, чуть-чуть отличаясь по массе от настоящей. Но изначально мы не знаем, легче фальшивка или тяжелее. Все оставшиеся 100 подлинных монет весят одинаково. Также у нас есть чашечные весы без гирь, которые показывают только больше/меньше/равно. Как за минимальное количество взвешиваний определить, тяжелее фальшивая монета настоящей или же легче?
В принципе я знаю ответ. При этом я посмотрел решение этой головоломки на многих сайтах, и все они дают абсолютно один и тот же способ. Предлагаю вам посмотреть три ссылочки. Но уверяю вас, что и на всех остальных сайтах алгоритм будет такой же.
ссылка 1
ссылка 2
ссылка 3
А затруднение у меня такое. Я люблю обобщать задачи и выводить общие алгоритмы решения.
Что, если у нас будет 99 монет?
Допустим, мы попытаемся действовать согласно тому алгоритму, который вы видите, если перейдёте по ссылочкам.
1) Первым действием поделим нашу кучку из 99 монет на 49, 49 и 1. Допустим, это кучки A, B, C соответственно.
2) Положим A на левую чашку весов, B — на правую, C оставим в стороне. Выполним первое взвешивание.
3) Если будет равновесие, то всё понятно. Фальшивой является монета C. Тут вопросов нет и быть не может. В принципе второе взвешивание можно сделать по-разному, но понятно, что C — это подделка.
4) Но что, если у нас при первом взвешивании нет равновесия?
Получается, согласно алгоритму, нужно разбить одну из кучек для второго взвешивания. Но у нас в данном случае обе кучки нечётные.
Выходит, алгоритм дал сбой. Или я чего-то недопонял.
Итак, вопрос. Можно ли решить эту задачу для любого количества монет? Естественно, для натурального числа. Если да, можно, то как нужно действовать?
Как обычно, не жаль бонуса, ибо задача лично для меня важна.
подробнее о бонусах
бонус за лучший ответ (выдан): 5 кредитов
тэги:
алгоритм,
взвешивание,
головоломка,
задача,
затруднение,
монета
категория:
наука и техника
ответить
комментировать
в избранное
3 ответа:
старые выше
новые выше
по рейтингу
4
ОлегТ
[37.8K]
2 недели назад
С нечетным количеством монет на втором шаге похожий алгоритм, но чуть измененный.
У вас возникла проблема с делением кучки пополам на втором шаге? Так давайте решим эту проблему.
Берите большую кучку кратную 4. И нету проблемы.
Давайте на вашем примере в 99 монет.
Делим на 96 (кратно 4) и 3 монеты.
96 делим пополам по 48 монет и взвешиваем между собой. 1 взвешивание
Если не равны: То по алгоритму делим тяжелую кучу в 48 пополам по 24 и взвешиваем между собой. 2 взвешивание
Если не равны то фальшивая тяжелее. Если равны, то фальшивая легче.
Если же после 1-го взвешивания равенство в кучах по 48
То фальшивая в куче из 3 монет
Взвешиваем 3 монеты (они с фальшивой) и любые 3 из 96 — они настоящие: 2 взвешивание
Если 3 с фальшивой легче, то фальшивая легче, если тяжелее, то фальшивая тяжелее.
Можно было изначально делить на 80 и 19
В принципе в 101 монету был тот же алгоритм делили на кучу кратную 4 в 100 монет и 1
Вообщем получаем для любого числа делим на две кучи. Большая должна делится на 4
И получаем 2 взвешивания
автор вопроса выбрал этот ответ лучшим
в избранное
ссылка
отблагодарить
Алекс-89
[91.1K]
ОК, спасибо. Очень хороший алгоритм. Думаю, что Ваш ответ объективно лучший. Правда, если общее количество монет меньше 4, то выделить кучу, кратную четырём, не получится. Т. е. алгоритм почти универсален, кроме нескольких случаев.
— 2 недели назад
ОлегТ
[37.8K]
Формально, конечно надо было упомянуть для полноты ответа случаи меньше 4. Спасибо за замечание.
Для 1 монеты — нет решения ни за сколько взвешиваний. Мы знаем что она фальшивая, но нам не с чем её сравнить.
Для 2 монет — нет решения. Мы никак не узнаем какая фальшивая и тяжелее она или легче.
Для 3 монет — 2 взвешивания (алгоритм отличается, что второй раз пополам делить не надо, а сравнивать с 3-ей монетой) и будет так же 2 взвешивания
Для 4 и больше уже можно выделять кучи кратные 4 и по описанному алгоритму в ответе.
— 2 недели назад
комментировать
3
dinVolt
[8.6K]
2 недели назад
Я бы рискнул взять четыре шага для любого числа.
Для числа 3n (то есть, кратного трём) решение будет находиться в два шага — делим на три кучки (A,B,C), измеряем AB, AC. Наличие фальшивой монеты в любом случае даст уникальное сочетание измерений.
Для числа 3n+1 нужно отложить монету, и если AB=AC, измерить любую монету отсюда с оставшейся.
Для числа 3n+2 есть два варианта. Если число нечётное, то это случай из задачи, решается за два взвешивания.
А вот 3n+2 чётное всё портит. Я бы отложил две монеты и повторил опыт 3n+1, только с двумя измерениями в конце (то есть, суммарно — четыре). Но, возможно, я чего-то в упор не вижу, и тут есть решение попроще.
Собственно, все числа на этом и закончились))
комментировать
в избранное
ссылка
отблагодарить
1
MrLOXI
[441]
2 недели назад
Если при первом взвешивании нет равновесия, то согласно алгоритму вы разбивайте 1 из кучек на 2 равные кучки (24 и 24) и оставляете 1 монетку, если показывает равновесие, то соответственно тоже самое проделываете со 2 кучкой, если и там равновесие, то взвешиваете 2 отложеные монетки, если же при 1 или 2 взвешивании неравенство, то дальше уже по старому алгоритму (делите 1 из кучек на 2 равные, т.е. по 12 монет и так далее пока не дойдёте до фальшивки.
комментировать
в избранное
ссылка
отблагодарить