Ken*_*oom 3 puzzle math geometry
在ACM通讯,2008年8月的"困惑"专栏中,Peter Winkler提出以下问题:
在我们面前的桌子上是10个点,在我们的口袋里是10美元1个硬币.证明硬币可以放置在桌子上(没有两个重叠),以便覆盖所有点.图2显示了这个特定点集的硬币的有效位置; 它们是透明的,所以我们可以看到它们.底部的三个硬币不需要.
在下一期中,他提出了他的证据:
我们不得不表明桌子上的任何10个点都可以被非重叠的1美元硬币覆盖,这是Naoki Inaba设计的一个问题,由他的朋友Hirokazu Iwasawa送给我,他们都是日本的拼图专家.
关键是要注意,以蜂窝状图案排列的包装盘覆盖了平面的90%以上.但我们怎么知道他们呢？半径为1的圆盘适合由六个等高三角形高度为一的正六边形组成.由于每个这样的三角形都有面积
sqrt(3)/3,六边形本身就有面积2*sqrt(3); 因为六边形将平面平铺成蜂窝状图案,所以每个具有面积π的圆盘覆盖? /(2*sqrt(3))平面表面的~9069.因此,如果磁盘随机放置在平面上,则覆盖任何特定点的概率为.9069.因此,如果我们在桌子上以六边形模式随机放置大量1美元硬币(借来的),平均而言,我们的10个点中的9.069将被覆盖,这意味着至少在某些时候所有10个将被覆盖.(我们最多只需要10个硬币,所以还剩下其余的.)
磁盘覆盖无限平面的90.69%是什么意思？最简单的回答方法是,或许可以说,当方块扩展时,磁盘覆盖的任何大方块的百分比接近该值.关于磁盘放置的"随机"是什么？考虑它的一种方法是固定任何包装和其中的任何磁盘,然后从包含磁盘的蜂窝六边形中随机均匀地选取一个点并移动磁盘使其中心位于所选点.
我不明白.这种证明的概率性质不仅仅意味着在大多数配置中,所有10个点都可以被覆盖.我们还不能提出一个涉及10个(或更少)点的配置,其中一个点不能被覆盖？
我认为我可以重新安排温克勒的论点,使其更有说服力.
你在桌子上给了一个点的排列.你还有一个由硬币粘在一起的硬币制成的大模板.您现在进行蒙特卡罗模拟,在随机位置(但始终具有相同方向)将蜂窝重复地抛在桌子上,并计算覆盖点的数量.如果你得到足够的样本,你最终会发现预期的平均点数是每投掷9.069.
关键的洞察力是,如果平均值是9.069,则必须有一个投掷点,其中包含10个点.因为如果你从未覆盖10个点,平均值将是9或更少.
所以现在你知道至少有一个投掷覆盖了10个点.您复制该投掷,并删除所有未覆盖点的硬币.将剩下10个或更少的硬币.
一个小小的题外话:对于一些巧妙的点排列,有可能的是,覆盖点的长距离平均值不是9.069吗？答案是否定的,因为每个点都可以单独考虑.换句话说,在10000个蜂窝的投掷中,每个点的预期数量将被覆盖9069次.因此我们预计总共可以覆盖90690个点,平均每次投掷9.069个点.