Задача про броски яйца с небоскреба

Условие

Представим, что вы живете в 100-этажном небоскребе и у вас есть два одинаковых яйца. Вам нужно определить самый высокий этаж, с которого можно бросить яйцо и не разбить его. Найдите алгоритм, который минимизирует количество бросков в худшем сценарии развития событий.

Решение

Для начала стоит сделать несколько важных утверждений:

• Эффект падения одинаков для всех яиц.
• Если при падении с конкретного этажа яйцо не разбивается, то оно не разобьется и при падении с более низких этажей.
• Наоборот, если яйцо разбивается при падении, то оно разобьется и при падении с более высокого этажа.
• Если яйцо не разбилось, его можно использовать снова.
• Разбитое яйцо нужно исключить.

Простое решение

Теперь пойдем от простого к сложному. Самый надежный способ найти этаж, начиная с которого разбивается яйцо, это начать бросать с 1го этажа, но в худшем случае нам придется бросить яйцо сто раз. К тому же имеется два яйца, а используем мы одно. Как поступим? Пусть первое яйцо будет разбивать сто этажей на более мелкие отрезки как можно эффективнее. В данных отрезках мы будем бросать яйца с верхней до нижней границы.

Пусть первое яйцо разбивает на 2 отрезка. Тогда первое яйцо нужно бросить с 1/n этажа, например, 1/2. Тогда алгоритм будет выглядеть так:

• Бросаем яйцо с 50 этажа. Если оно разбивается, проверяем первые 49 этажей вторым яйцом.
• Если оно не разбивается, бросаем яйцо с 50 + (50 * 1/2) = 75 этажа. Если разбивается, проверяем этажи 51–74 вторым яйцом.
• … В худшем случае для 1/2 (50, 26,…) — это 50. Так мы можем найти идеальный n, который оптимизирует количество бросков при помощи динамического программирования. Получим, что n равен 5, а наихудшее количество бросков равно 22. Но, данное решение не является оптимальным.

Оптимальное решение

Чтобы найти оптимальное решение, давайте напишем формула вычисления количества бросков в худшем случае:

$$max(F_{1},(F_{2}-F_{1}-1)+1,(F_{3}-F_{2}-1)+2,...)$$

где $F(n)$ - это следующий этаж, с которого мы бросаем первое яйцо. Очевидно, что имеем оптимальное решение, когда все переменные данной функции равны.

В таком случае предположим, что $F_{1}$ - максимум, тогда $F_{2} = F_{1} + (F_{1} - 1)$, или $F_{k} = F{k-1} + (F_{1} - (k - 1))$. Если разница между границами отрезков будет определяться по другому, то найдется ситуция, когда придется совершить больше бросков, чем $F_{1}$. Тогда, исходя из вышеперечисленного получим, что если максимум бросков равен m, то должно выполняться $F_{1} + (F_{1} - 1) + (F_{1} - 2) + ... + (F_{1} - l) = 100$ и $F_{1} - l = 1$. Тогда перепишем и получим:

$$l(l-1) - \frac{l(l+1)}{2} = 100$$

Решая данное уравнение получим, что l = 14. Проверим и получим ряд: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.

Предположим, что можем проверить за 13 бросков. Тогда получим следующий ряд: 13, 25, 36, 46, 55, 63, 70, 76, 81, 85, 88, 90, 91. Дальше нам уже потребуется больше 13 бросков для проверки, значит за 13 не получится.

Всем спасибо! До следующего раза :)

P.S.

Можно поупражняться и попробовать написать код, который решает данную задачу для любого количества этажей.