P19 · 最优性证明

三个正方形,封住四个点的距离上限

四个点恰好落在 L 形的四个关键顶点;一个直径论证证明任何其他构型都不可能把它们分得更开。

区域与计分

记 L 为正方形 [0,2] × [0,2] 挖去右上角开单位正方形后的区域:同时满足 x > 1、y > 1 的点被排除。对 L 内的四点集 S,记 d(S) 为其中最小的两点距离。P19 要最大化 d(S);验证器内部存储 d(S)²,以便进行精确比较。

构造:√2 可以达到

取下面四个点:

(0, 0),   (0, 2),   (1, 1),   (2, 0).

六个点对的距离平方依次为 4、2、4、2、8、2。因此最小距离为 √2,最优值至少为 √2。

(0, 2)(1, 1)(0, 0)(2, 0)
虚线标出三个单位正方形;三条绿色线段的长度都是 √2。

上界:三个直径为 √2 的集合

整个 L 形恰好是下面三个闭单位正方形的并:

Q₁ = [0,1] × [0,1],
Q₂ = [0,1] × [1,2],
Q₃ = [1,2] × [0,1].

每个单位正方形的直径都是 √2。反设 L 内存在四个点,且它们的最小两点距离严格大于 √2。那么任何 Qᵢ 都不可能同时包含其中两个点,所以对每个 i 都有 |S ∩ Qᵢ| ≤ 1。又因为这三个正方形覆盖 L,

|S| ≤ |S ∩ Q₁| + |S ∩ Q₂| + |S ∩ Q₃| ≤ 3,

这与 |S| = 4 矛盾。因此任意四点构型都满足 d(S) ≤ √2。三个正方形会在边界线段上重合,但这不会造成漏洞:即使某个边界点同时属于两个或三个正方形,上面的并集计数不等式仍然成立。

结合前面的构造,最优值恰为 √2;等价地,P19 内部存储的精确最优分数为 2。∎

两份不同的贡献

达到等号的四点构型原本就是 Dilses #32 保持的纪录;HwaterB #40 给出了把这项纪录升级为定理的上界论证。构型纪录与最优性证明分别署名。

Dilses #32 —— 达到最优值的构型