要用什么姿势玩玻璃球?(经典玻璃球临界值面试题)
2019-07-12
问题
有两个玻璃球做工完全一致，且有一栋100层高到楼，现在要测试玻璃球最高从该楼第几层丢下来不碎，要求测试的次数尽可能少，要什么样的测试策略进行测试？
建模分析
因为有两个玻璃球，所以第一个玻璃球可以从底到高，且间隔大于1层的楼层间进行测试，这样就可以先确定一个大范围。
假设第一个玻璃球在第x层碎了，那么为了可以精确测量临界值，剩下一个玻璃球只能在矮于x层且高于第一个玻璃球上一次测量的楼层由底到高逐层测试直到碎了为止。
记第一个玻璃球测试的间隔为序列 $ x=[x_1, x_2, x_3, , \dots, x_n] $,
例如当 $ x_1 = 10, x_2 = 10, x_3 = 10, \dots, x_{10} = 10 $表示第一个玻璃球每隔10层进行一次测试;
$ x_1 = 10, x_2 = 20, x_3 = 30, x_4 = 40 $ 表示 第一个玻璃球第一次测试在第10层，没有碎则在第30层（10 + 20）测试,第二次也没有碎则在第60层（30 + 30）测试，第三次还没有碎则在第100层（60 + 40）测试。
当第一个玻璃球以一个长度为 $ n $ 的间隔序列 $ x = [x_1, x_2, x_3, … , x_n] $测试，第二个玻璃球如上文所诉逐层测试，其需要的测试次数c可以分为两种情况计算：
- 玻璃球在第100层都碎，则需要扔 $ n $ 次，得 $c_ 1= n$
- 当第一个玻璃球在第 $ i $ 次测试时碎了，则剩下第玻璃球需要测试 $ x_i - 1$ 次。（减1是因为那一层已经碎了），即 $ c= i+x_i - 1$ 。
综上，对于该序列 $ x $ ，最坏的情况下测试数 $ c $ 必须满足： \(n <= c \tag{1.1}\)
\[1 + x_1 - 1 <= c \\ 2 + x_2 - 1 <= c \\ 3 + x_3 - 1 <= c \\ \vdots \\ n + x_n - 1 <= c \tag{1.2}\]另外，因为要测试100层，所以序列 x 还需满足.
\(\sum_{i=1}^{n}x_i = 100 \tag{1.3}\)
好了，下面我们可以通过式1.1和式1.2求解c和序列x啦 :P 。
求解
式1.1的 n 个不等式求和得:
\[\sum_{i=1}^{n - 1}i + \sum_{i=1}^{n}x_i <= n * c\\ \\ 即 \\ \frac{(n-1)n}{2} + \sum_{i=1}^{n}x_i <= n * c\]代入式1.3得:
\[\frac{(n-1)n}{2} + 100 <= n * c\] \[\frac{(n-1)}{2} + \frac{100}{n} <= c \tag{2.1}\]记 $ g(n) = \frac{n-1}{2} + \frac{100}{n} $ ,对 $ g(n) $ 求导得:
\[\frac{dg}{dn} = \frac{1}{2} - \frac{100}{n^2}\]求其零点可以知道:当 $ n > 10\sqrt{2} $ 时 , $ g(n) $ 递减; 当 $ n < 10\sqrt{2} $ 时, $ g(n) $ 递增,$ n $为整数故n取14。即:
\[g(n) >= g(14) = 14\]根据式2.1可以得:
\[c >= g(14) = 14 \tag{2.2}\]这说明最少得测试次数为14次。那么下面来求出序列$ x $。
将式2.2代入到式1.1和1.2有:
\[n <= 14 \\ x_1 <= 14 \\ x_2 <= 13 \\ \vdots \\ x_{14} <= 1\]Yeah! 所以 $ x = [14, 13, 12, 11, \dots , 1] $ 就是我们要求的那个答案。即系，第一个球在第14层扔，没碎就往上走13层扔，碎了就从1到13层逐层扔，巴啦巴拉巴拉，这样最大的。
我们搞定这个题目了，可以闷声发大财了！
并没有，我们目的是把这个题目玩坏。那么，继续给我一首歌的时间。
延伸
上文的讨论都是两个球，那么多个球，比如3个球要怎么玩呢？
显然第一个球也要按照一定的间隔序列 $ x = [ x_1, x_2, \dots, x_n ] $ 来扔。第一个球碎了怎么办？那就剩两个球呀，没错，就是递归两个球的情景。
记 $ k $ 个球，$ y $ 层楼需要的最小测试次数为 $ F(k, y) $, 根据上文可得：
\[F(2, y) = \sqrt{2y} \tag{3.1}\]那么，三个球的情况下，第一个球扔的楼层间隔序列 $ x $，和最坏情况下的测试次数 c 满足( $ n $ 为序列长度)：
\[n <= c \\ 1 + F(2, x_1 - 1) <= c \\ 2 + F(2, x_2 - 1) <= c \\ 3 + F(2, x_3 - 1) <= c \\ \vdots \\ n + F(2, x_n - 1) <= c\]令面所有上式的等号成立并联合 \(\sum_{i=1}^{n} x_i = 100 \tag{1.3}\) 得(其中 $ F^{-1}(2, y) = y ^ 2 / 2$ 为 $ F(2, y) $ 的逆函数):
\[n = c \\ x_1 = F^{-1}(2, c - 1) - 1 \\ x_2 = F^{-1}(2, c - 2) - 1 \\ x_3 = F^{-1}(2, c - 3) - 1 \\ \vdots \\ x_n = F^{-1}(2, c - n) - 1\] \[\sum_{i=1}^{c} F^{-1}(c - i) - c = 100 \tag{3.2}\]解出3.2的 $ c $ 值可以求到答案了。
乔朵麻爹！点解可以啊？
逆向考虑原问题的变种:
给你 $k$ 个球, 测试 $ c $ 次，你最多能测试多少层楼?
对于这个逆向问题，我们就是要最大化 $ \sum x $ ，所以我就要最大化每个 $ x_i $ 。那么原问题就是要求使得这个最大化值 $ F^{-1}(k, c) = 100 $
所以解出3.2就可以求出原问题最少需要多少次测试。
另外，利用这个方法可以实现原问题编程求解。即根据递推式：
\[F^{-1}(1, c) = 1 \\ F^{-1}(k, c) = \sum_{i=1}^c F^{-1}(c - i) - c\]从 $ c = 1 $ 开始迭代，填充二维数组 $ F^{-1}[k][c] $，直到 $ F^{-1}[k][c] == 100 $ 为止， 就可以求到答案。
好了，回来解这个方程啦:
\[\sum_{i=1}^{c} F^{-1}(c - i) - c = \sum_{i=1}^{c-1}\frac{i^2}{2} - c \\ = \frac{c(c-1)(2c-1)}{6} - c\]即求解：
\[\frac{c(c-1)(2c-1)}{6} - c - 100 = 0\]取整解得 $ c = 8 $
wolframalpha大法好!(其实我不会解三次方程囧)
代回到3.2得到 $ x = [33, 25, 19, 13, 9, 5, 3, 1] $ 。
未完待续
(纳尼？原问题也求了，三个球的也搞了，$ k $ 个球都可以编程求解了，还有什么幺蛾子？)
笔者智商不够，还有一个问题没有解决，那就是：
$ F(k, x) $ 的解析解。
猜测，当 $ k = 2$时，其解约等于求解前 $ c $ 个正整数的和大于等于 $ x $的解，$ k = 3 $ 时是平方和；那么会不会就是求 前 $c$ 个正整数的 $ k -1 $ 次方等于 $ x $的解？