地板铺硬币怎么放?
在常见的圆形硬币和方形硬币中选择一种,先考虑硬币与硬币刚好紧密相邻的情况。
正方形硬币问题
将地板按硬纸板的尺寸分隔成很多小方格,设想每个方格内有一根垂直的小柱子。要想使方格内有硬币,这个方格内必须有一根柱子。因此,地板上硬币(不重叠的)的个数不超过柱子的根数。而另一个问题是,是否可以做到硬币的个数恰好等于柱子的根数?为了达到这个目的,需要考察一个硬币可以“盖住”(完全或部分盖住)的柱子的情况。一个直径为2厘米的硬币放在边长1厘米的方格内,当硬币中心在小方格的中心时,硬币恰好可以盖住四个小方格的公共顶点上的一根柱子,在其它的情况下,最多只能盖住一根柱子。因此,为了使硬币的个数恰好等于柱子的根数,必须做到凡是硬币能够盖住的柱子,都正好被硬币所盖住。如果每一个硬币恰好盖住一个柱子,那么硬币放在相应的方格的中心,满足这个要求。(见下图)
圆硬币问题
圆硬币的问题与正方形硬币的问题不同,这时每一个硬币可以盖住若干根柱子。能否做到地板上硬币的个数恰好等于柱子的根数呢?事实上,硬币的个数一定小于柱子的根数。不过,硬币的个数不能超过柱子根数的多少倍呢?这个倍数的估值也是一个覆盖问题。这个问题相当复杂。
对于圆硬币问题,如果要求硬币之间没有重叠,那么硬币的个数肯定要小于柱子的个数。下面估计硬币个数的最大值。我们先来看一个硬币能够盖住多少根柱子。由于硬币可以和方格的公共边上及公共顶点上的柱子相切,所以硬币可以“盖住”(包括完全盖住和部分盖住)5根柱子。为了说明方便,下面用覆盖的面积来估计覆盖的柱子数。圆硬币“盖住”了五个柱子(以五个柱子为中心的五个小圆),圆硬币的面积为Π平方米,五个小圆公共部分的面积,小于以硬币直径为一边的小方格的面积。每个小圆的面积为(Π/16)平方米,五个小圆公共部分的面积小于1平方米。因此,硬币“盖住”的柱子数小于5x(1/Π/16)=80/Π≈25.465。
由此可以估计,无论圆硬币怎样放,铺满地板的硬币的个数肯定小于2.5465根柱子的根数,即,硬币的面积和小于地板面积的2.5465倍。不过这个估值较大。按照“铺砖”的方法放硬币,硬币个数等于根数的1.2482倍。可以证明,所放硬币的面积和的最小值是地板面积的1.2092倍。这就是说,无论怎样摆放硬币,硬币的面积和不会小于地板面积的1.2092倍,可以找到符合要求的硬币摆法来达到这个最小值。