100层楼2个球问题终极解答

今天笔试腾讯又碰到了哪个扔球的问题。本来这个问题去年就搞明白了，我知道答案是什么样子的，即使简单的估计一个值遍历试一试也用不了几分钟。结果非要装X，写个精确的求解过程，结果时隔一年加上时间紧张，木有写完，不开心。不过，既然推导了就分享给大家呗。

最原始的题目是这样的：

给2个小球，一个100层的楼，要求用最坏情况下最少的掉落次数确定出球能够掉落而不摔坏的最高楼层（在测试过程中，两个球都可以被摔坏）。在最坏的情况下，需要试验多少次？(每一次球出手算试验一次)

为了写出通用的公式，就假设有 $ f $ 层楼吧(由于题目中未明确给出，下面的推导假设在 $f$ 层是否会碎未知,即 $f$ 层是需要测试的)。设第一个球，依次在 $ \{x_1,x_2,x_3…,x_m…\},x_1 \le x_2 \le x_3…\le x_m \le… $ 层测试，当然是在没有碎的情况下继续测试第下个楼层，如果碎了就只能使用第二个球了。假设在 $ x_i $ 层这个第一个球碎了，这个时候就需要确定的是在 $ x_{i-1}+1$和$ x_i-1 $ 之间的哪一层恰好碎掉。由于我们只剩下一个球了，为了一定能得到结果，就只能从 $ x_{i-1}+1 $ 开始一层一层的试，这样最坏（第二个球一直不碎）情况下需要试到 $ x_i-1 $层，所以这时最坏情况下第二个球一共扔了$ x_i-x_{i-1}-1 $次。由于之前用第一个球扔了$ i $ 次，所以第一个球在$ x_i $层碎掉的情况下最坏一共要扔$ i+x_i-x_{i-1}-1 $ 次。由于第二球只可能在$ x_{i-1}+1$和$ x_i-1 $层之间扔，所以最高的能测试的层是某个$ x_i $，所以这个值需要不小于 $f$ （否则怎么测出所有的可能）。所以如果设$ x_0 = 0 $,最坏情况下最少需要扔 $ n $ 次，则此题就是求解如下问题:

$\begin{equation} \begin{aligned} min \ n & \\ subject.to&: \\ & \left\{ \begin{array}{l} \exists m, x_m \ge f \\ \forall i \le m,x_i-x_{i-1}+i-1 \le n \end{array} \right. \end{aligned} \label{conditionfor2} \end{equation}$

即求解满足上述条件最小的$ n $。上述第二个限制条件展开是:

$\begin{equation} \left\{ \begin{array}{l} x_1 - x_0 + 0 \le n \\ x_2 - x_1 + 1 \le n \\ x_3 - x_2 + 2 \le n \\ ..... \\ x_m - x_{m-1} + m - 1 \le n \end{array} \right. \end{equation}$

上式所有项球和有:

$\begin{equation} x_m + \frac{m(m-1)}{2} \le mn \end{equation}$

两端同时除以$ m $有 :

$\begin{equation} \begin{aligned} n &\ge \frac{x_m}{m}+ \frac{m-1}{2} \\ &= \frac{f}{m}+\frac{m}{2}-\frac{1}{2} \\ &\ge \sqrt{2f}-\frac{1}{2} \end{aligned} \label{resultfor2} \end{equation}$

即 $n=\lceil \sqrt{2f}-0.5 \rceil$ 当$ f = 100 $时有: $n \ge \sqrt{200}-0.5= 13.64$ 所以取 $n = 14$ 。限制条件 $\exists m,x_m>f$ 的意义是找一个尽量大的 $x_m$ ,而 $x_i \le x_{i-1}+n-i$ 所以最大的 $x_{i-1}$ 就可以使得 $x_i$ 取最大值。因此，可以使用限制条件取等号,即 $x_i = x_{i-1}+ n -i+1$ 来获得一个满足条件的序列 $\{x_i\}$ ，可以算出 $x_i = i*n-(i-1)$ 即其中一个满足的序列 $\{ x_i \}$ 是 $\{ 14,27,39,50,60... \}$ 。同样当 $ f = 39 $时有: $n \ge \sqrt{74}-0.5= 8.10$ 所以取 $n = 9$ ,其中一个满足的序列 $\{ x_i \}$ 是 $\{ 9,17,24,30,35... \}$ 。当然很多时候满足上述限制条件的序列可能不止一个。

对于上述最小正整数的 $n$ 一定能找出合理的 $\{x_i\}$ ，在此就不证明了。

现在来扩展一下，假设我们有三个球，这个问题该怎么解?对于三个球可以使用类似的过程解决。对于公式( $\ref{resultfor2}$ ) 做简单的变换可得：

$\begin{equation} f \le \frac{1}{2}(n^2+n) \label{resultfor2-sub} \end{equation}$

即在只有两个球的时候通过 $n$ 次仍球最多可以测试到 $\frac{n(n+1)}{2}$ 层。当有三个球的时候，假设仍 $n$ 次最多可以测试 $f$ 层，第一个球分别在 ${x_1,x_2,x_3...},x_1 \le x_2 \le x_3...$ 层测试。假设这个球在 $x_i$ 层碎了，问题就变成了在有两个球的情况下最多仍 $n-i$ 次，完成 $x_i-x_{i-1}-1$ 层楼的测试。通过公式( $\ref{resultfor2-sub}$ )可知有 $x_i-x_{i-1}-1 \le \frac{1}{2}((n-i)^2+(n-i))$ ，所以在三个球的情况下就是求解下面的最小化问题:

$\begin{equation} \begin{aligned} min \ n & \\ subject.to&: \\ & \left\{ \begin{array}{l} \exists m, x_m \ge f \\ \forall i \le m, x_i-x_{i-1}-1 \le \frac{1}{2}((n-i)^2+(n-i)) \end{array} \right. \end{aligned} \end{equation}$

这个问题的求解和求解问题 ( $\ref{conditionfor2}$ ) 的方法是一样的。展开第二个限制条件是:

$\begin{equation} \left\{ \begin{array}{l} x_1 - x_0 - 1 \le \frac{1}{2}((n-1)^2+(n-1)) \\ x_2 - x_1 - 1 \le \frac{1}{2}((n-2)^2+(n-2)) \\ x_3 - x_2 - 1 \le \frac{1}{2}((n-3)^2+(n-3)) \\ ..... \\ x_m - x_{m-1} - 1 \le \frac{1}{2}((n-m)^2+(n-m)) \end{array} \right. \end{equation}$

同样也是求和:

$\begin{equation} x_m - n \le \frac{1}{6}(n(n^2-1)) \end{equation}$

所以说:

$\begin{equation} f \le \frac{1}{6}(n^3+5n) \end{equation}$

这个方程可解，但是不太好解，下面给出它的解：

$\begin{equation} n \ge \frac{1}{3}p^{1/3}-5p^{-1/3} \end{equation}$

其中 $p=3^4f+\sqrt{15^3+3^8f^2}$ 。可惜这个结果不能继续化简了。如 $f=92$ 时, $n \ge 8$ , $f=129$ 时， $n \ge 9$ 。当 $f = 100$ 时， $n \ge 8.23$ 。得出 $n$ 之后就可以使用公式 $x_i = \frac{1}{2}((n-i)^2+(n-i))+x_{i-1}+1$ ，求得满足条件的一个序列 $\{x_i\}$ 。当第一个球碎了之后，问题就变成了上面两个球的问题了,上面已经给出了解。

100层楼2个球问题终极解答

版权信息

文章分类