логика - Найти высоту разбития тарелки

Мы давали вариант этой задачи на студенческой олимпиаде в 2010 году. Только у нас были стеклянные шарики. Я обрабатывала решения для издания (все олимпиады по 2010 г). Беру оттуда, не меняя:

Задача. Имеется k одинаковых стеклянных шариков. Их кидают с некоторых этажей 1000 этажного дома. Требуется за наименьшее число бросаний X определить самый нижний этаж, при бросании с которого шарики разбиваются (или убедиться, что таких этажей в доме нет). Вычислить X а) для k = 2; б) для k = 3.

Решение. Нам требуется по числу этажей в доме найти необходимое число бросков. Попробуем решить обратную задачу: по числу бросков найти этажность, для которой гарантированно можно определить самый нижний этаж разбития шаров.

Обозначим через $%p(k, n)$% максимальную этажность дома, для которого это можно сделать k шарами за $%n$% бросаний. Можно считать, что $%p(k, 0) = 0$%.
Рассмотрим сначала случай $%k = 1$%. Если мы бросим шарик хотя бы со второго этажа и он разобьется, то мы не узнаем, можно ли его было бросить с первого. Итак, один шарик надо бросать с 1-го, 2-го и так далее этажей, пока он не разобьется. Значит, $%p(1, n) = n$%.

Пусть теперь шариков больше, чем 1. Бросим первый шарик с этажа $%s_n$%. Если он разбился, то у нас остается $%k – 1$% шарик, $%n – 1$% бросок и $%s_n – 1$% непроверенных этажей. Значит, $%s_n – 1\le p(k –1, n – 1)$% и максимальное $%s_n = p(k –1, n – 1) + 1$%. В частности, $%s_1 = p(k –1, 0) + 1 = 1$%. Более высокие, чем $%s_n$%, этажи проверять не надо, так что $%p(k, n) \ge s_n$%.

Если же при первом бросании шар остался цел, то мы имеем в распоряжении еще $%(n – 1)$% попытку и снова $%k$% целых шара. За $%n – 1$% попытку мы можем проверить $%p(k, n – 1)$% этажей, начиная с номера $%s_n + 1$% (все более низкие проверять уже не надо). Поэтому мы можем определить нужный этаж во всем интервале от 1 до $%s_n + p(k, n – 1)$%.

Итак, $$p(k, n) = s_n + p(k, n – 1) = s_n + s_{n–1} + p(k, n – 2) = … = \sum_1^{n}s_i$$ Как мы показали выше, $%s_n = p(k –1, n – 1) + 1$%.

а) Пусть у нас есть два шарика. Имеем $%s_n = p(1, n – 1) + 1 = n$%. Тогда $%p(2, n) = \sum_1^n i =\frac{n(n+1)}{2}$%. Итак, за 44 броска можно проверить не более 990 этажей, а за 45 – уже 1035. Значит, 45 бросков хватит.

б) Для трех шариков имеем $%p(3, n) = \sum_1^n s_i $%, где $%s_i = p(2, i – 1) + 1 = \frac{i(i-1)}{2} + 1$%. Суммируя по i от 1 до n, получим $%p(3, n) = \frac16 (n^3 + 5n)$%. Поскольку $%\frac16(183 + 5\cdot 18) < 1000 < \frac16(193 + 5\cdot 19)$%, то $%X = 19$%.

Думаю, из этого решения легко сделать обще, для произвольных M и N.

У этой задачи есть два варианта решения: житейский и математический.
Житейский: потребуется $%0$% бросков. Тарелка разобьется при броске с первого этажа. Ну ясно же :)
Математический: представим ответ в виде функции $%f(N,M)$%. После того, как бросим тарелку с $%k$%-го этажа, она либо разобьется и мы продолжаем поиск с $%(M-1)$%-й тарелкой среди $%(k-1)$% этажей, либо она не разобьется и поиск продолжим с $%M$% тарелок среди $%(N-k)$% этажей. То есть, $$f(N,M)=\min_k(1+\max(f(k-1,M-1),f(N-k,M)))$$ Функция $%f$% - неубывающая по $%N$%, следовательно оптимальное $%k$% - то, при котором $%f(k-1,M-1)=f(N-k,M)$%.
С одной тарелкой единственный выбор - бросать тарелку с нижнего этажа (нижнего из оставшихся), пока она не разобьется: $%f(N,1)=N$%.
Когда тарелок хватает на бинарный поиск, то это и есть оптимальный путь (см. решение @falcao): $%\left(M\ge\lceil\log_2(N+1)\rceil\right) \rightarrow \left(f(N,M)=\lceil\log_2(N+1)\rceil\right)$%.

Такое активное обсуждение, разговоры про рекуррентную формулу, поэтому отправляю пока это незаконченное решение. Пища для ума, так сказать.