>>5577144Понятно, что если при броске с этажа, скажем, 89 первый шар разбился, то вторым шаром нужно проверять все этажи с первого по 88, бросая его по очереди с 1го этажа, со 2го, с 3го и т.д. Других вариантов нет. Воспользуемся этим наблюдением.
Пусть мы живем в доме, в котором количество этажей бесконечно. Пусть мы с нашими двумя шарами решаем вот какую задачу: для заданного числа бросков k узнать про наибольшее количество этажей, разобьётся ли шарик при броске с них. И пусть задача решена. То есть мы притворяемся сейчас, что оптимальная выигрышная стратегия у нас уже есть для любого количества бросков k. То есть у нас имеется описание вида:
"первый шар бросить с этажа номер a1
- если не разобьётся, то бросить его с этажа a2; если не разобьётся, то бросить с этажа a3;
- если разобьётся, то [бла-бла-бла, пока не знаем, что тут написано]".
Изучим, как бы мы должны были пользоваться оптимальной стратегией, если бы она у нас была.
Пусть a1 - номер этажа, с которого мы бросаем первый шар.
Допустим, шар разбивается. Тогда первым шаром нам придётся проверять все этажи с 1го по a1-1.
Тогда первым шаром мы сделаем один бросок, вторым (a1-1).
То есть сделаем двумя шарами в общей сложности a1 бросок.
Но ведь наше k оптимально. Значит, a1 не может быть больше k. Итак, a1 <= k.
Пусть теперь первый шар не разбивается при броске с a1-го этажа.
Тогда про все этажи ниже a1 мы уже знаем, что шар не разобьётся.
Мы снова бросим наш первый шар, с этажа номер a2.
Понятно, что a2 > a1.
Если шар разобьётся, то вторым шаром нам придётся проверять все этажи между a1 и a2.
Мы уже сделали два броска. Значит, у нас остался k-2 бросок вторым шаром.
Тогда между a1 и a2 не больше чем k-2 этажей.
Как узнать, сколько этажей между a1 и a2?
Ну, между пятым и восьмым два этажа. Между первым и девятым семь этажей.
Значит, между a1 и a2 ровно a2-a1-1.
Имеем
a2 - a1 - 1 <= k-2,
a2 <= a1 + (k-1) <= k + (k-1).
Далее, если шар не разбился при броске с a2 этажа, то бросим его с этажа номер a3.
Аналогично рассуждая, получаем, что a3 <= k + (k-1) + (k-2).
И вообще, ak <= k + (k-1) + ... 2 + 1.
Известно, что сумма натуральных чисел от 1 до k равна k(k+1)/2.
Значит, ak <= k(k+1)/2.
ak - этаж, с которого мы делаем последний бросок. Про этажи выше чем ak мы не знаем ничего.
Значит, количество этажей, про которые мы всё узнали, не превосходит ak и потому не превосходит k(k+1)/2.
Допустим теперь, что k бросками мы получаем инфу про сто этажей. Определим нижнюю границу для k - то есть найдем наибольшее такое k, что неравенство 100 <= k(k+1)/2 перестаёт выполняться. Легко видеть, что это k=13.
То есть нам понадобится не менее чем 14 бросков. Осталось найти стратегию, которая за 14 бросков позволит протестировать все сто этажей.
Такая стратегия есть - это видно из нашего построения.
Бросаем первый с 14 этажа; если разбился, то проверяем вторым шариком этажи с 1 по 13.
Если первый не разбился, бросаем его с 27 этажа. Если не разбился, то с 39, 50, 60, 69, 77, 84, 90, 95, 99.
