Problem:
There is a building, we have m identical objects to find out the number of the floor from which the object will break when it is dropped.
Despite the height of the building is fixed when the problem is normally asked, the key to this problem is to actually fix the number of tests with the m balls.
Solution:
We will be looking for a function
->number of the floors we can determine by
objects and with
trials.
Then we have:
with
Look for generating function
by multiplying (where
) on both side of the recursive equation and summing them up:
This will give us below:
expand above we will get
so for any value , we have
.
When ,
, so when
, value of function
first exceeds 100.