区域与计分
记 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。
上界:三个直径为 √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 —— 达到最优值的构型