|
If you are stuck, you first might want to hear about the experiment with eggs before giving up.
In order to find the height at which a sphere shatters, it is necessary to test at exactly that height, and one meter below, to be sure that the shattering point is neither higher nor lower. However, we don't need to test every single height, because we can tell whether the shattering point is above or below wherever we test. Therefore, we should try to test as high as possible in order to eliminate the most possibilities, but we have to make sure that we have enough tests and spheres to test all heights below, should it break.
Therefore, the basic strategy for each test is to drop from height N meters above the ground such that if it breaks, the remaining spheres and tests are exactly enough to test up to N-1 meters. For example, perhaps we knew that with 6 tests and 2 spheres, we could test up to 21 meters. If we had 7 tests and 3 spheres, our very first drop would be at 22 meters. If it breaks, we use the remaining 6 tests and two spheres to test all heights below 22. If it doesn't break, we test even higher.
Let us express the above in mathematical form. Let f(t,s) be the height up to which it is possible to test if you have s spheres and t tests.
f(t,s) = ∑(i=1 to t) ( f(t-i,s-1) + 1 )
f(0,s) = f(t,0) = 0
We could use this recursive formula to find our answer, but for those interested, here is the non-recursive formula and a proof.
Proposal:
f(t,s) = ∑(i=1 to s) ( C(t,i) )
Proof by induction:
f(t,0) = 0, as given
Assume true for s=k
f(t,k) = ∑(i=1 to k) ( C(t,i) )
f(t,k+1) = ∑(j=1 to t) ( f(t-j,k) + 1 )
f(t,k+1) = t + ∑(j=1 to t) ( ∑(i=1 to k) ( C(t-j,i) ) )
f(t,k+1) = t + ∑(i=1 to k) ( ∑(j=1 to t) ( C(t-j,i) ) )
f(t,k+1) = C(t,1) + ∑(i=1 to k) ( C(t,i+1) )
f(t,k+1) = ∑(i=1 to k+1) ( C(t,i) )
QED
Using the above equation, f(8,4) = C(8,4) + C(8,3) + C(8,2) + C(8,1) = 70 + 56 + 28 + 8 = 162.
It has been noted, correctly, in the comments that this formula can be explained by the number of possible test results. If 1 represents a break, and 0 no break, each string of test results might look like 10000010 or 01101010. Each string of test results can only correspond to exactly one conclusion. Note that there can be no more than 4 ones, since there are only 4 spheres. Also, if there are 8 zeroes, the conclusion is that the height at which the spheres break is above 162. |
