Есть 101 монета. Все они одинаковы на вид. Но при этом известно, что ровно одна монета является фальшивой, чуть-чуть отличаясь по массе от настоящей. Но изначально мы не знаем, легче фальшивка или тяжелее. Все оставшиеся 100 подлинных монет весят одинаково. Также у нас есть чашечные весы без гирь, которые показывают только больше/меньше/равно. Как за минимальное количество взвешиваний определить, тяжелее фальшивая монета настоящей или же легче?
В принципе я знаю ответ. При этом я посмотрел решение этой головоломки на многих сайтах, и все они дают абсолютно один и тот же способ. Предлагаю вам посмотреть три ссылочки. Но уверяю вас, что и на всех остальных сайтах алгоритм будет такой же.
ссылка 1
ссылка 2
ссылка 3
А затруднение у меня такое. Я люблю обобщать задачи и выводить общие алгоритмы решения.
Что, если у нас будет 99 монет?
Допустим, мы попытаемся действовать согласно тому алгоритму, который вы видите, если перейдёте по ссылочкам.
1) Первым действием поделим нашу кучку из 99 монет на 49, 49 и 1. Допустим, это кучки A, B, C соответственно.
2) Положим A на левую чашку весов, B — на правую, C оставим в стороне. Выполним первое взвешивание.
3) Если будет равновесие, то всё понятно. Фальшивой является монета C. Тут вопросов нет и быть не может. В принципе второе взвешивание можно сделать по-разному, но понятно, что C — это подделка.
4) Но что, если у нас при первом взвешивании нет равновесия?
Получается, согласно алгоритму, нужно разбить одну из кучек для второго взвешивания. Но у нас в данном случае обе кучки нечётные.
Выходит, алгоритм дал сбой. Или я чего-то недопонял.
Итак, вопрос. Можно ли решить эту задачу для любого количества монет? Естественно, для натурального числа. Если да, можно, то как нужно действовать?
Как обычно, не жаль бонуса, ибо задача лично для меня важна.
