Даны 2019 неразличимых по виду монет. Все монеты имеют одинаковую массу, за исключением одной, более легкой. За какое наименьшее число взвешиваний можно гарантированно найти более легкую монету при помощи чашечных весов без гирь?
Индукцией по k докажем следующее утверждение: если даны N одинаковых по виду монет, причем из которых одна более легкая, то ее можно найти за k взвешиваний. База индукции: одну монету взвешивать не надо. Шаг индукции: пусть для доказано. Пусть теперь Положим на левую чашу весов не менее монет, но не более монет, и на правую столько же. Если левая чаша легче, если левая чаша легче, то легкая монета на ней, если правая — то на ней, а если весы уравновешены, то более легкая монета находится среди оставшихся, число которых меньше или
Ответ: 7.