75
Пошаговое объяснение:
Алгоритм взвешивания гарантирующий нахождение среди 75 орехов:
1. Разбиваем орехи на 3 равные группы по 25.
2. Выберем 2 из групп по 25 и взвесим.
3. Если не равны то отдаем монету и выбираем легчайшую группу. Если совпал вес, то выберем оставшуюся.
4. Выбранную группу 25 орехов, в ней точно есть легкий, разобьем на 12 пар и один орех.
5. Так как у на есть как минимум одна монета начинаем взвешивать, выбранные пары, пока не найдем легкий. Если за 12 взвешиваний все совпали, то легкий орех оставшийся.
Доказательство того что это оптимальная стратегия из общих соображений:
1. Если осталась одна монета, то нельзя класть на весы больше чем по одному ореху, та как в случае неравенства мы можем узнать только группу с легким орехом но который из них мы знать не можем, поэтому если у нас осталость 12 ходов то мы сможем найти легкий орех только в группе из 25. При 26 все 12 взвешиваний могут быть равными и останутся еще 2 в которых не найти.
2. Каким бы не было первое взвешивание оно может быть неравным и оставшись с одной монетой нам оптимально знать группу из 25 орехов в которой точно будет легкий и мы сможем точно его найти.
3. Имея 4 равных группы орехов мы не сможем за одно взвешивание найти в которой из них орех, так как какие бы мы 2 не взвешали они могут оказаться равными и останется еще 2 группы из которых мы не сможем точно указать в какой легкий.
Перечисленные 3 довода доказывают что выбранная стратегия оптимальная.
