平面上有n个点,两两之间最远距离是d.求证,最远距离是d的点对最多有n对.

Question

平面上有n个点,两两之间最远距离是d.求证,最远距离是d的点对最多有n对.

Answer 1

我们在这 n 个点之间连线：如果两个点的距离是 d,那么它们之间就有一条边；否则,他们之间就没有边.我们要证的就是：最多有 n 条边.



如果每个点的度数（与之相邻的边数）都不超过2,那么显然最多有 n 条边,因为：
边数 = （各个点的度数之和）/ 2


下面我们考察某个点的度数大于2的情形.



如图,点 P0 的度数大于2,也就是与 P0 距离为 d 的点超过2个.
我们以 P0 为圆心,d 为半径画一个圆,则与 P0 距离为 d 的点 P1、P2、P3……都在这个圆上.实际上,P1、P2、P3……都在一个圆心角不超过60度的圆弧上,也就是说：不妨设 P1、P2 位于最外侧,其它点都位于 P1、P2 之间,则角 P1P0P2 不超过60度（因为否则 P1P2 之间的距离就大于 d 了）.


下面是关键：
除 P1P2 外,任何一个与 P0 距离为 d 的点（比如说：P3）,它的度数只能是1,也就是说：与 P3 距离为 d 的点只有 P0.
用反证法.假设还有一个点 P4,P4 与 P3 的距离也是 d.
以 P4 为圆心画一个半径为 d 的圆,叫圆 C,就是图中红色的圆.圆 C 交圆弧 P1P2 于 P3,所以 P1、P2 中至少有一个点在圆 C 外.不妨设：P1 在圆 C 外,那么 P1 与 P4 的距离就大于 d,矛盾.


综上,对于任意一个度数大于2的点 P0（设 P0 的度数为 k）,在所有与 P0 相连的 k 个点中,除了其中 2 个点（图中的 P1、P2）的度数可以是 <=2,其它 k-2 个点的度数全部是1.
所以,这 k+1 个点的度数之和：
<= k + 2*2 + 1*(k-2) = 2k + 2
也就是：平均度数 <= (2k+2) / (k+1) = 2


图中有 n 个点,将它们分组：
(1) 对每个度数大于2的点,将这个点与和它相连的点分成一组.
(2) 剩下点分为一组,它们的度数全不超过2.
显然,这样分组后,每个点都属于且仅属于一个组.
每组的平均度数都 <= 2
所以最后的边数 <= 2n / 2 = n


BTW：由推导,可见极限的有 n 条边的情形是这样的：
P0、P1、P2 组成一个等边三角形,其它点全部位于 P1P2 之间的圆弧上.