Ученые разработали новый материал неизвестной прочности. Они знают, что материал разбивается при падении с высоты от 1 метра до 5000 метров. Но не знают, с какой именно высоты.
Чтобы определить прочность, ученые поднимают предмет на некоторую высоту и сбрасывают его оттуда.
Их задача определить начиная с какой именно высоты предмет начнет разбиваться.
Специальная платформа, с помощью которой они осуществляют эксперимент скидывает предмет только с дискретных высот (1, 2, 3 ... 4999, 5000 метров - платформа не может скинуть предмет, например, с 2.5 метров. Точности в 1 метр ученым вполне достаточно).
При падении с высоты "n" метров предмет уничтожается. Если же его сбрасывали с высоты ниже "n", то его можно использовать в повторных экспериментах.
Нужно АБСОЛЮТНО ТОЧНО найти ту высоту, начиная с которой предметы разрушаются.
Сделать это нужно за МИНИМАЛЬНО возможное число экспериментов.
У ученых при этом всего 2 предмета, но они абсолютно одинаковые
Каким образом этого можно достигнуть? Сколько экспериментов при этом максимально потребуется.

Задача: найти минимальное количество экспериментов для определения высоты $n$, начиная с которой предмет разбивается, с использованием двух предметов.

Подход к решению

Эта задача сводится к оптимизации последовательности бросков, чтобы минимизировать наихудшее количество экспериментов. Два предмета дают возможность использовать гибридный метод, объединяющий линейный и бинарный подход.

Шаги решения

1. Анализ задачи:

   • Если у нас был бы только один предмет, пришлось бы использовать линейный метод. Мы бы бросали предмет с высоты 1 м, потом 2 м, потом 3 м и так далее, пока он не разобьется. Это заняло бы до 5000 бросков в худшем случае.
   • С двумя предметами задача становится более эффективной, так как один предмет можно использовать для грубой оценки, а другой — для точной проверки.

2. Стратегия: Чтобы минимизировать максимальное количество бросков:

   • Первый предмет используется для поиска диапазона (где примерно находится высота $n$).
   • Второй предмет используется для точной проверки в этом диапазоне.

3. Идея:

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

Оптимизация шага

Шаг увеличения высоты определяется следующим образом:

• Пусть максимальное количество бросков равно $k$.
• Тогда первый предмет бросается с высот $k, k + (k-1), k + (k-1) + (k-2), \dots$.
• Если первый предмет разбивается на $i$-м шаге, второй предмет проверяет высоты линейно от последней безопасной высоты.

Почему это работает? Потому что:

1. Количество бросков первого предмета ограничено $k$.
2. Количество бросков второго предмета в худшем случае равно $k-1$.
3. Сумма бросков гарантированно не превышает $k$.

Пример расчета:

Для $5000$ метров:

1. Решаем уравнение $k + (k-1) + (k-2) + \dots + 1 \geq 5000$, то есть $\frac{k(k+1)}{2} \geq 5000$.
2. Решив это уравнение, получаем $k \approx 100$ (точное значение — 100, так как $\frac{100 \cdot 101}{2} = 5050$).

Алгоритм действий:

1. Бросаем первый предмет с высот $100, 199, 297, \dots$ — на каждом шаге уменьшая шаг (100 → 99 → 98 и т.д.).
2. Если предмет разбился на, скажем, $400$-м метре (например, бросок с 400 м), начинаем линейную проверку с высоты $300$ до $399$ (включительно) вторым предметом.
3. Найденная высота $n$ — это первая высота, на которой второй предмет разобьется.

Максимальное количество экспериментов:

• В худшем случае потребуется $100$ бросков:
  • $100$ бросков первым предметом.
  • $99$ бросков вторым предметом.
• Итог: $100$.

Заключение:

Используя оптимальную стратегию с двумя предметами, ученые могут найти точную высоту $n$, начиная с которой предметы разбиваются, за максимум $100$ бросков. Это минимально возможное количество экспериментов для данной задачи.