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

作者: , 共 473 字
系列:数学之美

查看该系列所有文章

来自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%。
类似文章:
以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的overhang 堆积木 - 能伸出桌面多远?。今天这次课,来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。
一个面试题,号称是微软的