Два яйца и небоскреб

Решение

Описание задачи

Это классическая задача динамического программирования и оптимизации. Имеются 100 этажей и 2 яйца. Нужно найти критический этаж (где яйцо начинает разбиваться) за минимальное количество бросков в худшем случае.

Стратегия: Убывающие интервалы

Оптимальное решение основано на концепции убывающих интервалов между бросками первого яйца.

Алгоритм

Ключевая идея: Первое яйцо бросаем на возрастающих этажах с уменьшающимися интервалами.

Пусть интервал между бросками первого яйца: k, k-1, k-2, ... 1

Если первое яйцо разбивается на этаже с интервалом k, то используем второе яйцо для проверки оставшихся этажей между (k-1) и k интервалами.

Расчёт оптимального k

Чтобы охватить 100 этажей:

k + (k-1) + (k-2) + ... + 1 >= 100

Это сумма арифметической прогрессии:

k(k+1)/2 >= 100
k(k+1) >= 200
k >= 14 (так как 14×15 = 210)

Минимальное количество бросков в худшем случае = 14 бросков

Подробная стратегия для k=14

Броски первого яйца: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100, ...

Точнее:

• 1-й бросок: этаж 14
• 2-й бросок: этаж 14 + 13 = 27
• 3-й бросок: этаж 27 + 12 = 39
• 4-й бросок: этаж 39 + 11 = 50
• 5-й бросок: этаж 50 + 10 = 60
• 6-й бросок: этаж 60 + 9 = 69
• 7-й бросок: этаж 69 + 8 = 77
• 8-й бросок: этаж 77 + 7 = 84
• 9-й бросок: этаж 84 + 6 = 90
• 10-й бросок: этаж 90 + 5 = 95
• 11-й бросок: этаж 95 + 4 = 99
• 12-й бросок: этаж 99 + 1 = 100

Сценарии

Сценарий 1: Яйцо разбивается на 14-м этаже

• Первое яйцо разбилось на 1-м броске
• Используем второе яйцо: проверяем этажи 1-13 (до 13 бросков)
• Максимум: 1 + 13 = 14 бросков

Сценарий 2: Яйцо разбивается на 50-м этаже

• Первое яйцо не разбилось на 14, 27, 39
• Первое яйцо разбилось на 4-м броске (этаж 50)
• Используем второе яйцо на этажах 40-49 (до 10 бросков)
• Максимум: 4 + 10 = 14 бросков

Сценарий 3: Яйцо разбивается на 100-м этаже

• Первое яйцо не разбилось ни на одном этаже
• Максимум: 12 бросков (дошли до 100-го)

Доказательство оптимальности

Предположим, есть стратегия с меньшим числом бросков T < 14 в худшем случае:

1. Число возможных ответов = 101 (критический этаж может быть от 0 до 100, т.е. яйцо разбивается с 1-го этажа или не разбивается вообще)
2. С одним яйцом и T бросками можем различить максимум T+1 случаев
3. С двумя яйцами и T бросками: при разбивании первого яйца на i-м броске используем второе для проверки T-i оставшихся
4. Максимум различимых случаев = T + (T-1) + (T-2) + ... + 1 = T(T+1)/2
5. Нужно: T(T+1)/2 >= 101, откуда T >= 14

Реализация алгоритма на Python

def find_critical_floor(eggs=2, floors=100):
    """
    Определяет минимальное количество бросков.
    """
    # Находим k такое что k(k+1)/2 >= floors
    k = 0
    while k * (k + 1) // 2 < floors:
        k += 1
    
    return k

def drop_strategy(n):
    """
    Возвращает последовательность этажей для бросков.
    """
    floors = []
    interval = n
    current_floor = interval
    
    while current_floor <= 100:
        floors.append(current_floor)
        interval -= 1
        current_floor += interval
    
    return floors

print(find_critical_floor())  # 14
print(drop_strategy(14))  # [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99]

Обобщение для N яиц и M этажей

Рекуррентное соотношение:

T(n, m) = 1 + min(max(T(n-1, k-1), T(n, m-k)))
           для всех k от 1 до m

где T(n, m) - минимальное число бросков для n яиц и m этажей.

Для 3 яиц и 100 этажей: ~9 бросков Для N яиц: log(N) бросков асимптотически

Сравнение стратегий

Ключевые моменты

• Информационная теория: Два яйца = два измерения информации
• Компромисс: Баланс между рисками разбить оба яйца и необходимостью проверить все этажи
• Квадратичная сложность: O(√n) в худшем случае для 2 яиц
• Практическое применение: Тестирование систем, отладка, оптимизация параметров