overhang 堆积木 – 能伸出桌面多远？
Posted in Interesting Maths by Eagle Fantasy on May 9th, 2008
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
Related posts:
May 10th, 2008 at 7:44 pm
so strong….
Reply