My question is about this problem I made up:
'I have a height of unit length, and m glass balls. Dropping a ball higher than some unknown height, h, always breaks them, and dropping a ball lower never breaks them, and h is between 0 and 1. Given n drops, what is the smallest interval size I can guarantee for h?'
Note that a ball can be re-used if it isn't broken, and I am dropping balls 1 at a time. Whatever happens to the balls, I can only drop a maximum total of n times.
Let s(n,m) be the smallest interval size I can guarantee for h with n drops and m balls, with n and m being non-negative integers – is there a closed-form formula for s(n,m)?
I guessed s(n,n) = $\frac{1}{2^n}$ , and s(n,1) = $\frac{1}{n+1}$. I then, independently to the previous guesses, found the recursive definition s(n,m) = $\frac{s(n-1,m)s(n-1,m-1)}{s(n-1,m)+s(n-1,m-1)}$. Using induction and the recursive definition, I proved the previous two guesses. However, I don't know where to go from this, and couldn't find this problem anywhere else online. By closed-form, I mean including standard operations such as addition, subtraction, multiplication, division, exponentiation, and common functions such as logarithms and trigonometric functions, and I don't mind a piecewise definition for s(n,m).
Best Answer
Going purely from the recurrence relation, as noted in comments setting $t(n,m) = \frac{1}{s(n,m)}$ it becomes $$t(n,m)=t(n-1,m-1)+t(n-1,m)$$ with initial conditions $t(n,m)=2^n$ for $n \leq m$ and $t(n,1)=n+1$. The recurrence reminds the Pascal's rule, which suggests that some finite sum of binomial coefficients could be the solution. This and the initial conditions motivates $$ t(n,m)=\sum_{k=0}^{m} \binom{n}{k}. $$ To prove this simply verify the recurrence relation and the initial conditions.
Alternatively you could use bivariate generating function $f(x,y)=\sum t(n,m)x^ny^m$ to derive the same result (see for example Solving two-dimensional recurrence relation $a_{i,\ j}\ =\ a_{i,\ j-1}\ +\ a_{i-1,\ j-1}$ for a similar result).