В скандинавских древних сказах
Есть забавные примеры.
Гномы падки до алмазов,
Что найдут — несут в пещеры.
Так как знал лесной народец,
Что поблизости их нету,
То построили заводец,
Спрятанный в горе от света.
Там алмазного конвейра
Было вечное гуденье,
А народ благоговейно
Думал, что землетрясенье.
Но однажды злые тролли
Дождались-таки момента:
Все приборы раскололи
Испытательного стенда.
Чтоб камней проверить прочность
И никто не видел чтобы,
Гномы стали тёмной ночью
Их бросать из небоскрёба —
Выяснять этаж, с какого
(Значит, выше и подавно)
Камень, брошенный с балкона,
Будет биться постоянно.
Но алмаз — на вес алмаза,
Жалко бить такие камни.
Добровольцам дали сразу
Только два для испытаний.
Пусть на каждое бросанье
Полагается минута.
Сколько в стоэтажном зданьи
Гномы максимум пробудут,
Если под покровом ночи,
Пока люди не глазеют,
Каждый гном до смерти хочет
Сделать это побыстрее?
Ответ: 14 минут.
Решение. Решим задачу: если разрешается сделать n бросаний, то какова максимальная этажность дома f(n), для которого на этот вопрос можно однозначно ответить?
Очевидно, что f(1)=1 (если можно сделать 1 бросание, то дом должен быть одноэтажным).
Выразим f(n+1) через f(n). Пусть 1-е бросание делается с некоторого базового этажа. Если камень не разбился, то критический этаж выше, а в запасе по-прежнему 2 камня. Поэтому этажей выше базового может быть f(n) (одно разрешённое бросание использовали, n осталось). Если камень разбился, то критический этаж либо этот, либо ниже. Единственным оставшимся камнем пробовать этажи можно только последовательно снизу вверх, и при n запасных бросаниях таких этажей должно быть n. Плюс, естественно, базовый этаж. Итак,
f(n+1)=f(n)+1+n.
Отсюда, в частности, f(2)=1+2=3, f(3)=3+3=6, f(4)=6+4=10 и вообще, f(n) есть сумма первых n натуральных чисел. Найдём наименьшее n такое, что f(n)>=100. Продолжим: f(5)=15, f(6)=21, ... , f(13)=91, f(14)=105>=100. Значит, имея в запасе 13 бросаний, можно исследовать дом максимум 91-этажный, а с 14 бросаниями - максимум 105-этажный, а уж 100-этажный наверняка. Начинать следует с (100-91)=9-го этажа.