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 довода доказывают что выбранная стратегия оптимальная.
Жила-была такая крыса, но не Лариса. Она любила бегать по углам. Туда -сюда, туда -сюда. И почему-то, делила угол пополам. Сама она не понимала, зачем делила углы пополам. И вот возник вопрос. кто я?,и зачем делю угла? И вот пошла она к королю арифметики. Подошла она к трону, и спросила его.-Будь те вы помилосердней, ни казните ,лучше Буд-те мне так любезны, ответь мне на один вопрос. -Какой? -вы в математики все знаете, скажите кто я ?-Ты кто?!ты биссектриса!, ты такая крыса которая бегает по углам и делит угол пополам!
Вот отсюда и пришло что крыса-это биссектриса, а биссектриса -это крыса, которая бегает по углам и делит угол пополам!
