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

n个长度为1的砖块，叠起来能伸出桌面多远？（只考虑方块各平面都与桌面平行的情况）。

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

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

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

下面这个也不行

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

 

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

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

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

 

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

 

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

文章来自：阅微堂 http://zhiqiang.org/blog/posts/overhang-stacking-wood-how-far-can-extend-desktop.html#new331