Решение

[vak]

Раскрываю ответы на задачку с небоскрёбом и двумя бутылками.

Попробуем обобщить на K бутылок.

1. Сколько этажей можно обследовать с одной бутылкой за L шагов? Ответ - L этажей.

2. Сколько этажей можно обследовать с двумя бутылками за L шагов? Суммируем 1+2+3+...+L, ответ - L*(L+1)/2 этажей. Обозначим как S(L,2).

3. С тремя бутылками за L шагов? Суммируем 1 + S(2,2) + S(3,2) + ... + S(L,2). Пропуская пару страниц тривиальных вычислений, получаем ответ S(L,3) = L*(L+1)(L+2)/6 этажей. Для 100 этажей достаточно семи бросков.

4. В общем виде для K бутылок получается S(L,K) = (L+K-1)! / (L-1)! / K!
Это можно доказать по индукции, но мне лениво.

Comments

[tnt23.livejournal.com]

Таки для двух бутылок какой будет результат?

[vak]

Для двух бутылок и N-этажного дома ищем минимальное значение S(L,2) >= N.
Пусть имеем 100 этажей. Находим S(14,2) = 14*15/2 = 105 >= 100.
Ответ - 14 бросков.

[http://users.livejournal.com/_kalle_/]

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

[vak]

Мне изначально формулировали с двумя стаканами. Но с бутылками колоритнее получается.