Table of Contents
题目
FBI新招募的特工Elspeth要在一间圆形房间里安装7个天花板麦克风。
房间直径为40英尺。若这些麦克风的摆放方式要使得“房间内任一点到最近麦克风的距离的最大值”尽可能小，那么这7个麦克风应当放在什么位置？
分析
把房间看成半径\(20\)的圆盘。问题就变成：
在半径\(20\)的圆盘中放7个点，使圆盘内任一点到最近一个点的距离的最大值最小。
这本质上是一个覆盖问题。
先说明一个可以做到\(d=10\)的摆法。
- 1个麦克风放在圆心；
- 在房间圆周上作一个内接正六边形。由于房间半径是\(20\)，这个正六边形的边长也正好是\(20\)；
- 另外6个麦克风放在这个内接正六边形6条边的中点上。
边中点到圆心的距离是
\[ 20\cos30^\circ=10\sqrt3\]
所以这和“1个在圆心、另外6个在外接圆半径\(10\sqrt3\)的同心正六边形顶点上”是同一个构型。
下图把“大圆内接正六边形”“6个边中点麦克风”“中心覆盖区对应的内层正六边形”一起画了出来：
在这个构型里，最危险的点有两类：
- 中心麦克风与相邻两个外围麦克风之间的三重点；
- 房间边界上、位于两个相邻外围麦克风正中间的点。
对第一类点，中心麦克风与相邻两个外围麦克风构成一个边长为\(10\sqrt3\)的正三角形，所以三重点到这三个麦克风的距离相同，等于
\[ \frac{10\sqrt3}{\sqrt3}=10\]
对第二类点，取房间边界上位于两个相邻外围麦克风正中间的点\(P\)。它到相邻外围麦克风的距离满足
\[ d^2=20^2+(10\sqrt3)^2-2\cdot20\cdot10\sqrt3\cos30^\circ =400+300-600=100\]
所以\(d=10\)。
因此，这个摆法确实能把房间内任一点到最近麦克风的最大距离压到\(10\)，也就是说
\[ d\leq10\]
接下来说明：不可能做得比\(10\)更好。
为什么\(d<10\)不可能
反设可以做到\(d<10\)。
先看房间的圆周。任取某个麦克风，它的覆盖圆半径是\(d\)。如果它在房间圆周上覆盖到一段弧，那么这段弧的两个端点之间的弦长至多是它的直径，也就是\(2d\)。由于\(d<10\)，所以
\[ 2d<20\]
而在半径\(20\)的圆里，弦长\(20\)对应的圆心角正好是\(60^\circ\)。所以任何一个半径小于\(10\)的覆盖圆，在房间圆周上所能覆盖的弧长都严格小于\(60^\circ\)。
要覆盖整整\(360^\circ\)的房间圆周，就至少需要7个这样的覆盖圆。
也就是说，如果\(d<10\)，那么7个麦克风必须全部拿去照顾房间边界。
但这样一来，房间中心怎么办？
如果某个麦克风既能覆盖房间中心，又能覆盖房间边界上的某一点，那么由三角不等式可知：
\[ 20\leq d+d=2d<20\]
这显然矛盾。
所以，当\(d<10\)时，任何能覆盖房间中心的麦克风都不可能同时覆盖房间边界。但全部7个麦克风又已经都被边界“占满”了，于是中心无法被覆盖，矛盾。
因此，\(d<10\)不可能，也就是
\[ d\geq10\]
结合上面的构造\(d\leq10\)，最终得到
\[ d=10\]
结论
最优摆法是：
- 一个麦克风放在房间中心；
- 在房间圆周上作一个内接正六边形；
- 把另外六个麦克风放在这个内接正六边形6条边的中点上。
此时房间内任一点到最近麦克风的最大距离恰好是\(10\)英尺。
如果改用“同心六边形”的语言来描述，这完全等价于：
- 一个麦克风放在房间中心；
- 其余六个麦克风放在一个与房间同心、外接圆半径为\(10\sqrt3\)的正六边形的六个顶点上。
因为正六边形的边长等于其外接圆半径，所以这个六边形的边长也是
\[ 10\sqrt3\]
而中心那块覆盖区域的边界，则是另一只内切于半径\(10\)圆的正六边形。
换句话说，这6个外层麦克风距离墙壁的距离是
\[ 20-10\sqrt3\approx2.68\]
也就是约\(2.68\)英尺。
数学本质
这道题的核心是“上界构造 + 下界反证”：
- 先给出一个具体摆法，证明\(d\leq10\)；
- 再证明任何\(d<10\)的方案都不可能覆盖整个房间，于是得到\(d\geq10\)；
- 上下界合并，立刻得到最优值就是\(10\)。
这种做法在几何优化里很常见：
先构造一个好的方案，再证明任何更好的方案根本不可能存在。
这一题里，“更好的方案不可能存在”的关键障碍，就是：半径小于\(10\)的覆盖圆在房间边界上覆盖不了足够长的弧段。