У Беллы есть N одинаковых орешков, один из которых пустой и поэтому весит легче
остальных (все остальные весят одинаково). У мистера Фокса есть чашечные весы без
гирь, он разрешил Белле сделать 13 взвешиваний на них, но каждый раз, когда одна из
чаш перевешивает, он берёт с Беллы один рубль. У Беллы есть всего два рубля. Если у
Беллы больше не остаётся
денег, то она не может больше взвешивать орешки (ведь в
случае неравенства на весах ей нечем будет заплатить).
При каком наибольшем N она наверняка сможет найти пустой орех?
решите пж как можно быстрее очень нужно, заранее спасибо!
Ответы
Ответ:
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 довода доказывают что выбранная стратегия оптимальная.