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