磨剑(6)易碎的玻璃杯

tags: iq

——————— 好几年前写的东西了,朝花夕拾。

题目

有一栋100层高楼,从某一层开始扔下的玻璃杯刚好摔坏,现有两个玻璃杯,最少几次能找到那一层?

首先我要对题目的表述提点意见。这是一个很有歧义的表述方式,容易误导人向概率的方向去思考。
比如说,我可以回答“最少一次能找到那一层”。我就拿个杯子,从一楼起一层一层的摔。从概率上讲,有可能在一楼就碎了。这不也合题意么。
我觉得题目可以这样表述:

有一栋100层高楼,已知存在一个特殊的楼层,低于这层,摔玻璃杯不会碎;从这一层起往上,摔玻璃杯一定会碎。现在有两个玻璃杯,请设计一种策略,确保一定能在N次内找到这个特殊楼层,并且尽量让N最小。

解答

先随意的考虑几种情况,打开思路:
  1. 一层一层的从下往上摔,这也是一种策略,完全碰运气。可能在第1层就破了,也可能到100层才破。这个策略的N就等于100。
  2. 隔一层摔一下,1,3,5,7…99,假设在7层层破了,我们拿另一个杯子回第6层试一下。这也能找到那个特殊层,并且比第一种优秀,只需要51次就OK了。
  3. 二分法试试。先在第50层摔,如果碎了,我们面对50层楼和一个杯子,只能一层一层往上试了,与第2种方式没有优势。如果没碎,我们倒可以换75层去试试看。
如果第一只杯子破了,第二只就只能一层一层的试,直到破为止。通过这几种尝试,可见关键在于第一只杯子怎么利用。
上面第三种思路给我们一个灵感,从第A层开始摔,至少能保证100-A次内找到特殊层。

根据这个思路,解答如下:
    假设我们有一种最优策略,使得N次内总能找到特殊层。
    第一次选在A层摔,破了,说明特殊层在1到A之间,用剩下的那只杯子,至少能在A-2次内找出特殊层。
    由于A是最优解,那我们可以最大化的利用第一次的跨度,使得A=N+1。
    下一个尝试点应该是A+(N)=(N+1)+(N)。为什么?
    如果这层发现第一个杯子摔碎了,就需要用第二个杯子一层一层试。从A到A+N,中间共N-1层楼,只需要N-2次就可以试出来。由于我们已经甩过两次杯子了,所以N-2正好是我们能够做的尝试次数。
    同理,第三次选的楼层应该是(N+1)+(N)+(N-1),……可以看出,这是一个等差数列,那么第n次选择的楼层应该是,
    (N+1)+(N)+(N-1)+…+(N+2-n) = n(2N+3-n)/2

    另外,最后一次尝试如果小于99,是不可能完成任务的。
    所以我们又有,当n=N时,n(2N+3-n)/2 >= 99,由此可推出:N>=13
对于13,导出我们的序列为:
14,27,39,50,60,69,77,84,90,95,99,
共有11个尝试点,不难验证,这是可行的。

其实后面还可以推出102,104,即13次尝试,一定能从104层楼中找出那个特殊层。
100层楼没有用尽这个策略的所有“能量”,所以对尝试点的选择还可以有一些变化,
比如,每个尝试点都可以往前平移,只要保证第13个尝试点大于等于99。