Из одинаковых ** вид монет мудрец может найти единственную фальшивую, сделав всего 4...

0 голосов
172 просмотров

Из одинаковых на вид монет мудрец может найти единственную фальшивую, сделав всего 4 взвешивания на чашечных весах без гирь. Какое наибольшее число монет
может быть у Мудреца, если известно, что фальшивая монета более легкая?


Математика (70 баллов) | 172 просмотров
0

олимпиада плюс?

Дан 1 ответ
0 голосов
Правильный ответ

Поскольку весы именно чашечные, то задача нахождения фальшивой монеты из N сводится к бинарному поиску - мы каждый раз делим исходную кучку пополам (или на три части, если пополам не делится), определяем ту, которая легче, затем поступаем с ней аналогично. И т.д. пока сравнение не сведется к 2-м монетам - более легкая из них и есть искомая. При этом для N монет нам понадобится log2(N) взвешиваний. Если N не степень двойки, то округление идет до ближайшей СЛЕДУЮЩЕЙ. Т.о. в нашем примере log2(N) = 4. Откуда N = 2^4 = 16. 16 монет.

(63.7k баллов)