P21 · 最优性证明

两个精确答案,不依赖“最优解必然对称”

NUE_13 找到了四点与五点的正确构型;下面的上界论证把这两项观察升级为定理。

区域与五个正方形

记 C 为 [0,3] × [0,3] 挖去四个角上的开单位正方形后得到的十字形。等价地,C 是中央单位正方形与下、右、上、左四个单位正方形臂 B、R、T、L 的并。对 C 内的有限点集 S,记 d(S) 为最小两点欧氏距离;验证器内部存储 d(S)²。

达到等号的构型

四点时取

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

按环形顺序连接,它们构成一个正方形:四条边长都是 √5,两条对角线长都是 √10。因此 d(S)=√5。

五点时再加入中心 (3/2,3/2)。中心到四个外点的距离平方都是 5/2,而任意两个外点的距离平方至少为 5,因此 d(S)=√(5/2)。

四点上界:四条臂必然产生一条短边

反设四点的任意两点距离都严格大于 √5。单位正方形的直径只有 √2,所以覆盖 C 的五个单位正方形中,任何一块都不能同时含有两点。如果有一点落在中央正方形,它与任意一条臂的并都包含在一个 1 × 2、直径为 √5 的矩形内,立刻得到矛盾。因此只剩一种情形:四条臂各有一点。

按环形顺序把四点记为 B、R、T、L。令 X 为 BR、RT、TL、LB 四条线段的横坐标差平方之和。两个中间横坐标 x_B、x_T 属于 [1,2],右端横坐标 x_R 属于 [2,3],左端横坐标 x_L 属于 [0,1]。固定 x_R、x_L 后,

X = f(xB) + f(xT),
f(m) = (xR−m)² + (m−xL)².

f 是凸函数,所以它在 [1,2] 上的最大值必在端点取得;对 x_R、x_L 再作同样的端点论证即可。四种 (x_R,x_L)=(2,0),(2,1),(3,0),(3,1) 分别给出 X≤8、2、10、8,因此 X≤10。把整个论证旋转 90°,同理得到纵坐标差平方和 Y≤10。于是

|BR|² + |RT|² + |TL|² + |LB|² = X + Y ≤ 20.

四个相邻距离平方中至少有一个不超过 5,与反设矛盾。因此 d(S)≤√5。

五点上界:总有一整条臂靠近中央点

再反设五点的任意两点距离都严格大于 √(5/2)。因为 √(5/2)>√2,五个单位正方形各自至多含有一点;它们又覆盖整个 C,所以中央正方形和四条臂必定各有一个点。把中央点写成

c = (3/2 + σ,  3/2 + τ),
a = |σ|,  b = |τ|,  0 ≤ a,b ≤ 1/2.

在上、下两条臂中选离 c 较近的一条。c 到这整块单位正方形中任意点的最大距离平方为

Mv = 5/2 + a − 3b + a² + b².

这是因为横向最大偏移为 1/2+a,到较近臂的纵向最大偏移为 3/2-b。同理,在左、右两条臂中选较近的一条,有

Mh = 5/2 + b − 3a + a² + b².

M_v 与 M_h 至少有一个不超过 5/2。否则,把两个严格不等式相加会得到 a²+b²>a+b;但 0≤a,b≤1/2 又推出 a²+b²≤(a+b)/2,矛盾(a=b=0 时两者恰等于 5/2)。所以至少有一整条臂都位于以 c 为圆心、半径 √(5/2) 的圆内;该臂上的点与 c 构成矛盾。因此 d(S)≤√(5/2)。

两个上界都被前面的构型达到,定理得证。等价地,P21 内部存储的精确最优分数分别为 5 与 5/2。∎

为什么 n = 9 没有封盘

投稿中的九点构型有效,确实达到 √5/2:在外层四点正方形的中心和四条边中点各放一点即可。但给出构型只证明了下界;“看上去对称”不能推出任意九点构型都必有一对这么近,目前也没有独立上界。因此 P21 n=9 继续开放。

投稿与严格证明的分工

NUE_13 #31 给出了四点、五点、九点构型并提出对应最优值猜想。本站验证了三个构型,指出对称性不足以充当上界,并补出了封住 n=4、5 的严格不等式。猜想贡献与完成的证明分别说明。