Раскрываю ответы на задачку с небоскрёбом и двумя бутылками.
Попробуем обобщить на 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!
Это можно доказать по индукции, но мне лениво.
Попробуем обобщить на 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!
Это можно доказать по индукции, но мне лениво.