A generatingfunctional solution to the problem of testing from which storey an object that is dropped will break

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

f(m,n)->number of the floors we can determine by m objects and with n trials.

Then we have:

f(m,n) = 1 + f(m-1, n-1) + f(m, n-1)

with f(m,1)=1, f(0,n) = f(m, 0) = 0

Look for generating function

A_n(x) = \sum_{k>=0} f(k,n)x^k

by multiplying x^k(where k>=0) on both side of the recursive equation and summing them up:

A_n(x) = \frac{x}{1-x} + xA_{n-1}(x) + A_{n-1}(x)

This will give us below:

A_n(x) = \frac{x((1+x)^{n-1} + \cdots + 1)}{1-x} = \frac{(1+x)^n - 1}{1-x}

expand above we will get

A_n(x) = \sum_{k>=0} (-1 + \sum_{i+j=k} \binom{n}{i})x^k = \sum_{k>=0} (-1 + \sum_{i=0}^{k} \binom{n}{i})x^k

so for any value m, we have

f(m, n) = -1 + \sum_{i=0}^{m} \binom{n}{i}.

When m=2, f(2, n) = \frac{(n+1)n}{2}, so when n=14, value of function f first exceeds 100.

留下评论