趣题:用单位圆覆盖平面上的10个点

    证明:对于平面上的任意一个大小为 10 的点集,我们总能在平面上不重叠地放置若干个单位圆,使得它们合起来可以覆盖到所有这 10 个点。


 
 
 
 
 
 
 
 
 
 

      

    让我们先把充分多的单位圆放在平面上,并像上图那样紧密地排列在一起,则它们将覆盖这个平面 π / (2 · √3) ≈ 0.9069 的面积。这是因为,整个图形可以看作是由虚线所示的正六边形平铺得来的,而每个正六边形的面积为 6 · √3 (六个边长为 2 的等边三角形),其中被覆盖的部分正好可以拼成三个完整的单位圆,其面积为 3 · π ,占整个正六边形的 (3 · π) / (6 · √3) = π / (2 · √3) ≈ 0.9069 。

    不过,这并不能保证点集中的每个点都被这组圆覆盖到了。现在,随机地对这组圆进行平移,得到一系列概率均等的圆盘放置方案。在这些圆盘放置方案中,每个点都有 0.9069 的概率被覆盖到,换句话说每个点被覆盖到的期望次数都是 0.9069 ;因此,在这 10 个点中,发生覆盖的期望次数就是 9.069 ,这是一个大于 9 的数。那么,这里面一定有一种圆盘放置方案,它至少产生了 10 次覆盖,这就表明所有的 10 个点都被覆盖到了。

问题来源:http://www.cs.cmu.edu/puzzle/puzzle38.html

30 条评论

发表评论