You have two glass balls and a 100-story tower. You would like to determine the lowest floor from which a glass ball will break when dropped. You can reuse a ball if it remains unbroken after a trial. Assume that the value of lowest floor is distributed uniformly and find the strategy which minimizes the expected number of tries.
Glass balls and tower
January 14, 2008 by wangyingjie80
迷惑ing…高智商的人啊
翻译过来俺有可能有答案
I think binary search will do? I was asked this question once 🙂
Hi Bear, could you plz disclose more details of your idea or the proposed algorithm as binary is a very general idea.
The proposed solution:
Denote the first glass ball as B1, another as B2. Move B1 to search n stories upwards each time. assume B1 breaks after k times. So the minimum number must be
between n*(k-1) and n*k (because it has not broken on the n*(k-1)th floor). Then use B2 for the secondary search (there are n-1 stories need to be checked, not n !).
Therefore, the total number of searches implemented so far is k+n-1. As previously mentioned, the distribution is uniform. So we have: k=100/n/2 (divided by 2 to get average)
Similarly, for the secondary search, the average is: (n-1)/2. The total number now becomes: 50/n+n/2-0.5. Employ the inequality formula (a+b>=2*sqrt(a*b))
we have: 50/n+n/2-0.5>=2*sqrt(50/n*n/2)-0.5=9.5. So the mimimum No is equal to 10.
Dear Jie, I don\’t think the answer is right although I don\’t know the right answer. It\’s really a interesting question and I hope can see the right answer from you sometime. 🙂