题目
设\(X\)是平面上的一个有限点集，且\(|X|=n\)。已知\(X\)中任意两点之间的最大距离为\(d\)。
证明：在\(X\)中，距离恰好等于\(d\)的点对数最多为\(n\)。
分析
为避免“长度”和“计数”混在一起，先固定两个记号：
- \(\operatorname{diam}(X)=d\)表示点集\(X\)的直径，也就是最大距离。
- \(M(X)\)表示\(X\)中距离恰好等于\(\operatorname{diam}(X)\)的点对数，也就是“最大点对数”。
下面要证明的就是\(M(X)\leq |X|=n\)。接着用反证法。
图1（引理反设示意）：先假设两组最大点对\(AB,CD\)不相交，并连接对角线\(AD,BC\)导出矛盾。
先证明一个几何引理：若\(AB\)和\(CD\)都是最大点对，也就是\(|AB|=|CD|=d\)，且四点互异，则线段\(AB\)与\(CD\)必须相交。
原因是：若它们不相交（如上图），先注意最大点对的端点都在四点凸包的边界上。按凸包边界次序可记为\(A,B,D,C\)（必要时交换\(C,D\)），于是得到一个凸四边形，其中\(AB\)与\(CD\)是两条对边，\(AD\)与\(BC\)是两条对角线。设对角线\(AD\)与\(BC\)交于点\(O\)。在三角形\(AOB\)中有\(|AO|+|BO|>|AB|\)，在三角形\(COD\)中有\(|CO|+|DO|>|CD|\)。两式相加得到
\[ |AD|+|BC|=(|AO|+|DO|)+(|BO|+|CO|)>|AB|+|CD|=2d.\]
所以至少有一条对角线长度大于\(d\)，这与\(\operatorname{diam}(X)=d\)矛盾。
现在反设命题不成立，取一个最小反例\(X\)，其中\(|X|=n\)，且
\[ M(X)>n.\]
把点看成顶点、把最大点对看成边，得到一张简单图\(G\)。这样\(G\)的边数正好是\(M(X)\)，所以\(|E(G)|=M(X)>n\)。由握手定理1，
\[ \text{平均度}=\frac{2M(X)}{n}>2.\]
因此至少存在一个顶点的度不小于\(3\)（否则若所有顶点度都至多为\(2\)，平均度也至多为\(2\)，矛盾）。记该点为\(P\)，取与它相连的三个点\(A,B,C\)，则\(P\)与\(A,B,C\)都是最大点对，即
\[ |PA|=|PB|=|PC|=d.\]
由余弦定理，
\[ |AB|^2=|PA|^2+|PB|^2-2|PA||PB|\cos\angle APB=2d^2(1-\cos\angle APB).\]
又因\(|AB|\leq d\)（因为\(\operatorname{diam}(X)=d\)），得\(\angle APB\leq 60^\circ\)。同理其余两角也都不超过\(60^\circ\)。
因此三条射线\(PA,PB,PC\)中必有一条夹在另外两条之间，不妨设\(PB\)夹在\(PA\)与\(PC\)之间。
图2（关键位置关系）：当\(PB\)夹在\(PA,PC\)之间时，虚线\(BQ\)无法同时满足与\(PA,PC\)都相交。
现在看点\(B\)是否还能与别的点\(Q\)形成最大点对\(BQ\)。若有这样的\(Q\)，则按引理：
- 线段\(BQ\)必须与\(PA\)相交（因为\(BQ\)与\(PA\)都是最大点对）。
- 线段\(BQ\)也必须与\(PC\)相交（同理）。
但当\(B\)位于扇形\(\angle APC\)内部边界方向时，一条从\(B\)出发的线段不可能同时穿过射线\(PA\)与射线\(PC\)（除非经过\(P\)，但\(Q\neq P\)），矛盾。
所以\(B\)只参与一条最大点对，即\(BP\)。
由上一步知，在\(X\)中含点\(B\)的最大点对只有\(BP\)这一条。因此删去\(B\)后，原来\(X\)中其余最大点对都还保留在\(X'=X\setminus\{B\}\)里，至少有\(M(X)-1\)对点的距离仍为\(d\)。
另一方面，\(X'\subset X\)，所以\(\operatorname{diam}(X')\leq \operatorname{diam}(X)=d\)；而刚才又有至少一对点在\(X'\)中的距离为\(d\)，故\(\operatorname{diam}(X')\geq d\)。于是
\[ \operatorname{diam}(X')=d.\]
因此这至少\(M(X)-1\)对距离为\(d\)的点，在\(X'\)中仍然都是最大点对，故
\[ M(X')\geq M(X)-1>n-1=|X'|.\]
所以\(X'\)也是一个更小的反例，这与“\(n\)最小”矛盾。
故反设不成立，命题得证：最大点对数至多为\(n\)。
-
握手定理：任意有限无向图满足\(\sum_{v\in V}\deg(v)=2|E|\)，因此平均度为\(\frac{1}{|V|}\sum_{v\in V}\deg(v)=\frac{2|E|}{|V|}\)。 ↩