Какие математические методы используются для поиска одной фальшивой монеты среди множества одинаковых?

Для поиска фальшивой монеты среди множества одинаковых используют метод разделения и взвешивания. 23

Монеты делят на кучки и кладут на весы по несколько штук за раз, постепенно подбираясь к фальшивой. 3

Пример алгоритма: 3

1. Разделить 12 монет на три кучки по четыре монеты в каждой. 3
2. Положить на каждую чашу весов по четыре монеты. 3
3. Если вес двух кучек одинаковый, то все монеты в них настоящие, а фальшивая лежит где‑то среди четырёх невзвешенных монет. 3 Чтобы отслеживать результат, все подлинники помечают ноликом. 3
4. Берут три подлинника и сравнивают с тремя невзвешенными монетами. 3 Если их вес равен, то оставшаяся (четвёртая) невзвешенная монета фальшивая. 3
5. Если вес отличается, то на трёх непомеченных монетах ставят знак «плюс», если они тяжелее, или «минус», если легче. 3
6. Берут две монеты, помеченные знаком, и сравнивают их вес. 3 Если он одинаковый, то оставшийся экземпляр — подделка. 3 Если нет, смотрят на знаки: среди монет с плюсом фальшивой будет та, что тяжелее, среди монет с минусом — та, что легче. 3

Если вес двух кучек с монетами неодинаковый, то в тяжёлой кучке ставят знак «плюс», в лёгкой — «минус», в невзвешенной — «нолик», так как известно, что фальшивый экземпляр был на весах. 3 Затем перегруппировывают монеты, чтобы уложиться в два оставшихся взвешивания. 3

Существуют и другие алгоритмы поиска фальшивой монеты среди множества одинаковых, в зависимости от условий задачи. 15