Два яйца и сто этажей — разбор задачи

Условие

Есть $2$ одинаковых яйца и здание в $100$ этажей. Существует неизвестный порог $F$ от $0$ до $100$ с этажей не выше $F$ яйцо цело, выше $F$ разбивается. Целое можно бросать снова. Какое минимальное число бросков гарантирует нахождение $F$ в худшем случае?

О задаче · Школьники и взрослые

Тема: Алгоритмы
Для кого: Школьники и взрослые
Уровень библиотеки: Продвинутый · ориентир

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

После первого разбитого яйца проверять оставшийся промежуток придётся по одному этажу снизу.

Подсказка 2

Чтобы общий лимит не рос, делайте очередной прыжок на один этаж короче.

Разобрать решение по шагам

Уравняйте худшие случаи

Если лимит $14$ первый бросок можно сделать с $14$ -го. При разбитии останется $13$ бросков для этажей $1$ – $13$

Сокращайте прыжок

Если яйцо цело, следующий этаж — $27$ между $14$ и $27$ только $12$ непроверенных этажей, а два броска уже потрачены. Затем $39$ и так далее.

Докажите минимум

При $m$ бросках и двух яйцах можно проверить не больше $m+(m-1)+\cdots+1$ этажей: первый прыжок не длиннее $m$ иначе после разбития не хватит бросков. $\frac{13\cdot14}{2}=91<100$ , а $\frac{14\cdot15}{2}=105\ge100$ . Ответ $14$

Этажи для первого яйца

0114 → 27 → 39шаги 14, 13, 12

0250 → 60 → 69шаги 11, 10, 9

0377 → 84 → 90 → 95 → 99 → 100шаги продолжают уменьшаться

Ответ

$14$ бросков в худшем случае.

Главная идея

Оптимальный план уравнивает худшие последствия раннего и позднего неудачного исхода.

Как заметить эту идею в другой задаче

Есть два расходуемых пробника и нужен худший случай. После первого неудачного испытания должен остаться запас на последовательный поиск.

Возможная ошибка

Применить двоичный поиск: после разбития первого яйца второе не позволяет безопасно делить оставшийся диапазон пополам.

Источник и примечания

Источник и редакция

Классическая задача. Формулировка, рисунки и разбор — Popov Academy.

Проверь себя

Сколько бросков достаточно и необходимо для $36$ этажей и двух яиц?

Ответ к дополнительной задаче

$8$ сумма $1$ + … + $8 = 36$ а $1$ + … + $7 = 28$

Продолжить тему: Поиск и алгоритмы →

Тема, знания и приёмы

Поиск и алгоритмы · Нужна школьная база

Сумма последовательных натуральных чисел
Худший исход серии испытаний

Приёмы решения: Оценка и достижимость

Задать вопрос по задаче →

Условие

Уравняйте худшие случаи

Сокращайте прыжок

Докажите минимум

Источник и редакция

Условие

Дополнительная задача