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

Ещё одна довольно известная задача, которую включают почти во все сборники задач с собеседований в Гугл.

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

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

Решение
Пусть мы знаем, что минимальное число бросков в худшем случае K.

Очевидно, что для того, чтобы сделать не более K бросков, первый бросок должен быть не выше чем с K-го этажа. В самом деле, если мы сбросим первое яйцо с этажа M>K, и оно разобьётся, у нас не будет иного выхода кроме как методично проверять все этажи подряд начиная с первого и заканчивая M-1. В худшем случае мы проверим M-1 этажей, что в сумме с первым броском даст M>K бросков. Очевидно также, бросать в первый раз ниже чем с K-го этажа нет смысла.

Итак, в первый раз мы бросаем с этажа K. Если яйцо разбилось, то за K-1 попыток мы проверим все K-1 нижних этажей. Если же нет, у нас останется K-1 бросок в запасе на верхние этажи.

Рассуждая аналогично, мы должны будем совершить второй бросок с этажа K+(K-1). Если яйцо разобьётся, нам нужно будет проверить этажи с K+1 по 2*K-2, которых всего K-2, что в сумме с двумя первыми бросками даст искомые K бросков.

Понятно, что если первое яйцо не разобьётся, третий бросок мы будем делать с этажа K+(K-1)+(K-2), четвёртый - с K+(K-1)+(K-2)+(K-3) и так далее. Самый последний бросок мы можем сделать с этажа K*(K+1)/2.

Следовательно, для того чтобы небоскрёб из N этажей можно было проверить за K бросков, должно выполняться условие K*(K+1)/2>=N. В случае N=100 получается K>=14.

Таким образом, нам нужно сделать в худшем случае 14 бросков. До тех пор, пока первое яйцо не разбивается, мы бросаем его с этажей 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. Если оно разбивается, например, на 69-м этаже, мы начинаем бросать второе яйцо со всех этажей начиная с 61-го, т.е. с первого непроверенного.