4 crystal balls and a 10,000 story building There is an analog of this question I've heard with 2 crystal balls but a higher number like 4 or more makes it much more interesting. You are given 4 crystal balls and there is a 10,000 story building. You are guaranteed that a crystal ball will break if dropped from a certain floor $m$ of the building or higher, otherwise it will not break when it is dropped from a floor lower than $m$. What is the minimum number of times you need to drop a ball in order to guarantee you can determine $m$ by the time all the crystal balls break? 
As a bonus question, can an explicit formula for the maximum number of floors of the building be determined so that the problem can be solved with $k$ balls and $d$ drops, as a function of $k$ and $d$? I believe the answer should be a polynomial in $d$ of degree $k$.
 A: With $k=1$, you have to drop the ball from each floor as you go up, so the most floors you can handle with $d$ drops is $d$  When $k=2$, you can afford to start at floor $d$, as if it breaks you can use the other ball $d-1$ times.  If it doesn't break, we have the problem with two balls and $d-1$ drops.  If $N(d)$ is the number of floors we can handle with two balls and $d$ drops, we get a recurrence $N(d)=(d-1)+1+N(d-1)$  We can compute some small values and discover $N(d)=\frac 12d(d+1)$, the triangular numbers.
For more balls, the same idea applies.  If we let $F(k,d)$ be the number of floors we can handle with $k$ balls and $d$ drops, the recurrence is $F(k,d)=F(k-1,d-1)+1+F(k,d-1)$  because you drop the first ball from floor $F(k-1,d-1)+1$.  You are correct that you get a polynomial in $d$ of degree $k$.  For four balls, I just put the recurrence into Excel, found trendline as a polynomial of degree $4$ and get $F(4,d)=\frac 1{24}d^4-\frac 1{12}d^3+\frac {11}{24}d^2+\frac 7{12}d=\frac 1{24}d(d+1)(d^2-3d+14)$
A: The maximum is ${d\choose 4}+{d\choose 3}+{d\choose 2}+{d\choose 1}$.
You need to deduce the correct floor from the pattern of crashes - which of the $d$ drops caused balls to crash?  There were $4,3,2$ or $1$ crashes, which can happen in ${d\choose 4}+{d\choose 3}+{d\choose 2}+{d\choose 1}$ ways.  You can't have no crashes because then you still haven't found the ball's limit.
Ross Millikan shows how to achieve this limit.
