overhang 堆积木 - 能伸出桌面多远?

作者:
系列:数学之美

查看该系列所有文章

来自 University of WarwickMike Paterson 星期二在 Yao 的理论计算机课堂上给了一个非常有趣的小讲座。

n 个长度为 1 的砖块,叠起来能伸出桌面多远?(只考虑方块各平面都与桌面平行的情况)。

下面这种放法,很多人高中学物理的时候都见过吧?它用 N 个砖块伸出了大约(\ln(N)/2)。

normal-method

上面这种叠放方法称为 Harmonic Stacks ,但它是最优的吗?下面这个例子可以看出,在 3 个砖块,我们就已经能做的更好了。

normal-method

上面这个能继续往上堆么?很不幸

normal-method

下面这个也不行

往上叠也不行的

如果在上面再压很多砖块就可以了

normal-method

下面是一种叠放方法,可以做到大约(O(lnN)).

normal-method

但它也不是最优的,下面是 20 个和 30 个方块的最优叠放方法,它比上面的要好

normal-method normal-method

下面是砖块数目比较少的时候的最优叠放方法。

normal-method normal-method

不过说了这么多,上面的方法都只能做到 ln(N)的量级,而下面这个方法可以用 N 个砖块,往前伸出 N^(1/3)的长度。

normal-method

而且, Mike Paterson 及其合作者证明了,这种方法在量级上已经是最优的了!

Q. E. D.

系列: 数学之美 »
本文将证明: 最佳约会策略 里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过 \( \frac{u}{n}\sum_{i=u}^{n-1}\frac1i\) ,其中 \( u\) 为满足 \( \sum_{i=u}^{n-1}\frac1i\geq 1\) 的最大值。这个 \( u\) 大约为 37%,最后成功的概率大约为 40%。
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自 姚期智 教授的理论计算机( I )的授课内容——我是其助教之一。
一个面试题,号称是微软的