结果
| n | 连续最优值 | 九位网格最大值 | 证明 |
|---|---|---|---|
| 1 | 0.288675134 | §1 | |
| 2 | 0.384900179 | §1 | |
| 3 | 0.549038104 | §1 | |
| 4 | 0.617524884780866… | 0.617524883 | §2–4, §6–7 |
| 5 | 0.693904526840437… | 0.693904525 | §2–4, §6–7 |
| 6 | 0.803847575 | §2–4, §6–7 | |
| 7 | 0.855687593470088… | 0.855687591 | §2–4, §6–7 |
| 8 | 0.912454563520543… | 0.912454561 | §2–4, §6–7 |
| 9 | 0.976596443373822… | 0.976596440 | §2–4, §6–7 |
| 10 | 1.056624324 | §2–4, §6–7 | |
| 11 | 1.098475709724551… | 1.098475706 | §2–4, §6–7 |
| 15 | 1.308432222 | §2, §5–7 |
没有闭式的值是该接触图方程组唯一正根的半径和,表中给出前 15 位;我们以 60 位精度求得,误差小于 10⁻³⁰。连续最优值都不在网格上,网格最大值严格小于它。
0. 记号
容器顶点为 (0,0)、(1,0)、(1/2, √3/2)。圆 i 的圆心 (xᵢ, yᵢ)、半径 rᵢ ≥ 0。约束为三条墙 yᵢ ≥ rᵢ、√3xᵢ − yᵢ ≥ 2rᵢ、√3(1 − xᵢ) − yᵢ ≥ 2rᵢ,以及每对圆 |cᵢ − cⱼ| ≥ rᵢ + rⱼ(允许相切)。记 z = (x₁, y₁, r₁, …, xₙ, yₙ, rₙ) ∈ ℝ³ⁿ,目标 c·z = Σrᵢ。本站提交的每个数最多九位小数,分数为整数 10⁹·Σrᵢ。
Mₙ 记 n 个圆的连续最优值。三角形的对称群 D3(三个旋转、三个反射)和圆的重新编号都不改变可行性与目标。
1. n = 1、2、3
n = 1
圆心到三边距离之和恒为高 √3/2(三个小三角形面积相加),每个距离至少 r,故 3r ≤ √3/2,内切圆取等:M₁ = √3/6。九位网格:整数 m 须满足 (6m)² ≤ 3·10¹⁸,而 (6·288675134)² < 3·10¹⁸ < (6·288675135)²,故最大为 288675134,内切圆取 r = 0.288675134 达到。
n = 2
记 ρ = √3/6。半径 r 的圆心可行域是三边各内移 r 的正三角形 T_r。固定 r、s,两圆心距离是凸函数,最大值在 T_r 与 T_s 的某对顶点取到。令 t = r + s、d = |r − s| ≤ 2ρ − t。同一角的顶点相距 2d;不同角的顶点距离平方为 (1 − √3t)² + d²。
若 t > 4ρ/3,则 d ≤ 2ρ − t < 2ρ/3 < t/2,同角距离 2d < t 不够;且
(1 − √3t)² + (2ρ − t)² − t² = 3(t − 4ρ/3)(t − 4ρ) < 0 (4ρ/3 < t ≤ 2ρ)
不同角也不够。故 r + s ≤ 4ρ/3 = 2√3/9,内切圆加同一角隙中半径 ρ/3 的相切圆取等。网格:(9·384900179)² ≤ 12·10¹⁸ < (9·384900180)²,故最大为 384900179,由 (0.5, 0.288675134, 0.288675134) 与 (0.5, 0.673575313, 0.096225045) 达到。
n = 3
沿用上面的顶点论证:异角与同角距离平方之差为 (1 − 2√3a)(1 − 2√3b) ≥ 0,所以每对圆必须满足
F(a, b) = 1 − 2√3(a + b) + 3a² + 2ab + 3b² ≥ 0.
F 对 b ∈ [0, ρ] 严格递减,故 b ≤ g(a) = [√3 − a − 2√(a(√3 − 2a))]/3。令 R = (√3 − 1)/4,半径排序 a ≥ b ≥ c。若 a ≤ R,和 ≤ 3R。若 a ≥ R,和 ≤ H(a) = a + 2g(a);记 h = √(a(√3 − 2a)),g″(a) = 1/(2h³) > 0,H 凸,最大值在端点:H(R) = 3R,H(ρ) = 5ρ/3 < 3R。故 M₃ = 3R = 3(√3 − 1)/4,三个半径 R 的圆各靠一角并两两相切取等。
网格:⌊10⁹M₃⌋ = 549038105,但它达不到。若最大半径 ≥ 0.183012703,H 在两端的值都小于 0.549038105(有理区间严格验证);否则三个半径都 ≤ 0.183012702,和 ≥ 0.549038105 要求两个半径都等于 0.183012702,而 F(b, b) < 0。故最大为 549038104,当前纪录达到。
2. 化为满接触图
引理 2.1(最优解半径全正)。 可行集紧,最大值存在。若某最优解有半径为 0 的圆:三角形顶点附近总有未被覆盖的小区域(三角形内的圆盘碰不到顶点),在那里放一个小正圆会增大目标,矛盾。
引理 2.2(满接触)。 存在一个最优解,其活跃约束(相切的圆对与贴墙)的梯度张成 ℝ³ⁿ。在所有最优解中取使 |z|² 最大者。若活跃梯度不满秩,取公共零向量 v ≠ 0。圆对约束 |cᵢ − cⱼ| − rᵢ − rⱼ 是凸函数,不会低于它沿 v 为零的线性化;墙约束是仿射的;非活跃约束对小步保持成立。于是对小的正负 t,z + tv 都可行。若 c·v ≠ 0,一侧增大目标;若 c·v = 0,两侧都是最优解,而 |z + tv|² 在一侧严格增大。两者都矛盾。
引理 2.3(接触图是三角剖分)。 把三条墙当作三个顶点,接触图连同外三角形是简单平面图,边数至多 3(n + 3) − 6 = 3n + 3,扣掉三条墙–墙外边,接触至多 3n 个。引理 2.2 给出至少 3n 个,所以恰好 3n,平面图边数取到最大值,即三角剖分。(顶点附近不接触的弧先保留再收缩,包中的接触引理逐一处理了这些边界情形。)
结论:连续最优值是有限个“外面为三面墙、内部为 n 个圆的三角剖分”所实现的半径和中的最大者。
3. 每个接触图至多一个实现
圆 i 周围每个三角面在 i 处的角为:两墙 2π/3;一墙一圆 j 为 2 arctan √(rⱼ/rᵢ);两圆 j、k 为 2 arctan √(uv/(1 + u + v)),其中 u = rⱼ/rᵢ、v = rₖ/rᵢ。后两式对每个邻居半径比严格递增,每个圆周围角和为 2π。
引理 3.1。 同一接触图的两个正实现半径相同。取新旧半径比最大的圆,它的每个邻居比值只减不增;若有一个严格减小,它的角和将小于 2π。所以它的圆邻居比值都相同,由圆–圆子图连通传遍全部圆。最后,每条墙上切点链的长度对半径是一次齐次的(角圆贡献 √3r,相邻相切圆的切点相距 2√(rᵢrⱼ)),两个实现中都等于 1,故公共比例为 1。
半径确定后圆心也确定:从墙–墙角面里的圆出发沿对偶图逐面推进,每个新圆心是到两个已知点距离给定的两个交点之一,三角剖分的定向选定其中一个。
4. n = 4–11:枚举全部接触图
外面固定的三角剖分在边翻转下连通(Bose 与 Verdonschot,arXiv:1206.0303,§2 引理 1、3),所以从任一三角剖分出发、做所有合法翻转直到闭合,就得到全部。包中对每个图的每条合法翻转都给出到列表中某图的显式同构见证;我们用自己的程序从头重新生成了列表。
| n | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|
| 图数 | 16 | 78 | 457 | 2 938 | 20 118 | 144 113 | 1 065 328 | 8 068 332 |
对 n = 4–9 的每个图,包中给出一个有理盒和近似逆矩阵 R,用精确有理算术验证 Krawczyk 条件 ‖I − RJ(X)‖∞ < 1 与自映射,从而盒内恰有一个根;所有不接触的圆对与墙都有严格正的间隙,所以该根是合法排布。最高图的半径和下界严格高于其余所有图的上界。n = 10、11 包中用更短的路线(§5 式的类型界;n = 11 为顶点分裂覆盖加比较界)。我们独立地对 n = 4–11 的每个图解角和方程、检查全部接触与非接触,得到相同的最优图,最优值与包中所有打印位数一致。
n = 6、10 的最优图是等圆三角阵(3 行、4 行):m 行时 r = 1/(2√3 + 2(m − 1)),给出 6 − 3√3 与 5(3 − √3)/6。
5. n = 15:幂单元
n = 15 的接触图太多,不再枚举。取 §2 的满接触最优解。若某圆同时贴三面墙,它是内切圆,由面积与 Cauchy–Schwarz:Σr ≤ √3/6 + √(14(√3/(4π) − 1/12)) < 1.308432221,低于目标。以下设每个圆至多贴两面墙。
幂单元。 Cᵢ = 三角形 ∩ {x : |x − cᵢ|² − rᵢ² ≤ |x − cⱼ|² − rⱼ²,对所有 j}。这些凸多边形划分三角形,圆 i 含于 Cᵢ。每个物理接触给 Cᵢ 一条正长度的边;平面对偶图已含 3n 条接触边和 3 条外边,达到最大边数,所以没有别的邻接:单元 i 的边数 kᵢ 恰为圆 i 的度数,三个角各只属于一个单元。记 wᵢ 为贴墙数、tᵢ ∈ {0, 1} 为所含的角数,电荷 qᵢ = kᵢ + wᵢ − 6。计数给出 Σqᵢ = 0、Σtᵢ = 3。
三个关系。 (i) 面积:Cᵢ 的边都与圆 i 相切,相邻外法向夹角 β₁…β_k 之和为 2π,面积 = rᵢ² Σ tan(βⱼ/2),由 tan 的凸性有下界 Cᵢ·rᵢ²,Cᵢ 只依赖类型 (k, w, t) 与角的分配;各单元面积之和为 √3/4。(ii) 墙长:每条墙上切点链长度为 1,用 2√(rᵢrⱼ) ≤ rᵢ + rⱼ 得 3 ≤ Σ bᵢrᵢ,bᵢ = 2wᵢ + 2(√3 − 1)tᵢ。(iii) 墙上交点:每个墙上交点恰有两个单元,内角和为 π,故 Σ(Sᵢ − πwᵢ/2) = −3π/2,Sᵢ 为单元 i 在墙交点处的外法向半角之和。
以 λ > 0、μ ≥ 0、ρ ≥ 0 加权三者,并对每个 rᵢ 配方:
Σr ≤ λ√3/4 − 3μ + [Σᵢ F(typeᵢ) + 3πρ/2] / (4λ), F = max角 [(1 + μb)²/C + ρ(S − πw/2)].
每个单元类型 (k, w, t) 的 F 上界是一个有限的有理计算:把归一化角域二分,在每个叶盒上用有理的 sin/cos 截断级数严格下界面积系数。n = 15 时 k ≤ 16,共 135 个类型、22 937 个节点。
按电荷分情形。 若电荷不全为 0,则或有两个正电荷单元,或有单元电荷 ≥ 2,或缺陷在角上、或有非角的双墙单元、或两个缺陷都贴墙:七个结构性对偶证书(各 55 个精确不等式)把这些情形的上界压到目标以下。剩下恰好一个 +1、一个 −1:三个角单元都是 (4, 2, 1) 型,按边界圆数 B 与缺陷位置共 33 个类型直方图,各自的角域证书(共 3 101 个节点)都严格低于 1.308432221。所以最优解的电荷全为 0。
零电荷引理。 在半径最大的圆处,三圆面角 ≤ 60°、一墙面角 ≤ 90°、两墙面角 = 120°,上界之和为 (k + w)π/3 = 2π,必须全部取等:邻居半径都相等,由连通性传遍,所有圆等半径。等圆满接触时墙链整齐,构成完整的三角阵,n = m(m + 1)/2。n = 15 即 5 行,r = (4 − √3)/26,Σr = (60 − 15√3)/26,圆心 x_ij = r(√3 + j + 2i)、y_ij = r(1 + j√3),j = 0…4,i = 0…4 − j。
6. 网格:把高分排布锁进小盒
设要排除的分数为 T,比网格纪录高 1 个单位。T 高于 Mₙ₋₁,所以分数 ≥ T 的排布半径全正(去掉任一圆还剩 n − 1 个);T 也高于除最优图外所有接触图的上界。
引理 6.1。 分数 ≥ T 的可行集 H 的每个连通分量都包含最优排布 z* 的某个 D3 像(重新编号后)。在该分量内先最大化半径和、再最大化 |z|²,引理 2.2 的论证照搬(扰动停留在同一分量内),得到满接触点;它的接触图只能是最优图,由 §3 即为 z* 的某个像。
引理 6.2(二次分离)。 在 z* 处取 3n 个活跃约束(墙为仿射距离,圆对为 |cᵢ − cⱼ|² − (rᵢ + rⱼ)²),Jacobian J 可逆,乘子 λ = −J⁻ᵀc 全部严格为正。令 d = z − z*、δ = |d|,则 F(z) = Jd + Q(d),墙的余项为 0,圆对的余项 ≤ 2δ²。记 p 为圆对行的指示向量、ε = M − T,取
A ≥ maxᵢ |(J⁻¹)·i| / λᵢ, B ≥ 2A Σpairs λᵢ + 2|J⁻¹p|.
则每个分数 ≥ T 的可行点满足 δ ≤ Aε + Bδ²。若 4ABε < 1,球面 δ = 1/(2B) 上没有这样的点;连通分量含 z* 的像又不能跨过球面,所以整个分量都在球内,在那里同一不等式给出 δ < 2Aε。于是所有高分排布(重新编号后)都落在 z* 的六个 D3 像周围半宽 2Aε 的坐标盒内。n = 11、15 用同一论证的 ∞ 范数版本。
常数用有理区间计算:由 ‖I − RJ‖∞ ≤ θ < 1 得 J⁻¹ 每个元素与 R 相差至多 θ‖R‖∞/(1 − θ);A、B 向上取整,√3 用有理平方夹逼,盒的下界向上、上界向下取整到 10⁻⁹。六个 D3 像各给出一个整数盒,相同的盒只在给出显式圆置换后才合并(n = 11 另用 x → 1 − x 把六个像配成三对)。
7. 网格:盒内逐点排除
在每个整数盒内,把圆对约束在盒上展开、二次余项按最坏情况移到右端,墙约束用 √3 的有理上界,得到一组必要的线性不等式 A w ≤ b(w 为相对盒底的整数偏移),再加目标行 −Σwᵣ ≤ ΣR − T。这是外逼近:每个真实可行点都满足它。
然后是一棵分支树:每个节点先用非负有理对偶乘子投影出各坐标的界并按整数取整收紧,再把某个整数变量分成 ≤ k 与 ≥ k + 1 两支。每片叶子要么目标上界低于 T,要么 phase-I 下界严格为正(不可行),都由存储的非负有理乘子精确验证,残差用全部变量界补偿。没有任何浮点求解器的“不可行”被当作证明。n = 15 还在每个节点加入整数凸包割(墙用 ⌊√3x⌋ 表、圆对用 ⌈√(R² − dy²)⌉ 表),每条割都对相关的全部整数逐一验证。
| n | 排除的分数 | 证书 |
|---|---|---|
| 4 | ≥ 0.617524884 | 3 个盒,85 个节点 |
| 5 | ≥ 0.693904526 | 6 个盒,474 个节点 |
| 6 | ≥ 0.803847576 | 1 个盒,287 个节点 |
| 7 | ≥ 0.855687592 | 2 844 个节点 |
| 8 | ≥ 0.912454562 | 4 400 个节点 |
| 9 | ≥ 0.976596441 | 5 276 个节点 |
| 10 | ≥ 1.056624325 | 1 个盒,3 997 个节点 |
| 11 | ≥ 1.098475707 | 3 棵树,368 119 个节点 |
| 15 | ≥ 1.308432223 | 1 个盒,20 191 个节点 |
树覆盖盒内全部整数点,叶全部关闭,所以没有分数 ≥ T 的九位排布;当前纪录达到 T − 1,它就是网格最大值。
8. 本站的独立核验
证明包由 zzzcy #308 于 2026 年 10 月 4 日通过邮件提交(约 1.1 GB,投稿时注明借助 AI 完成)。按本站规定,我们没有运行包中的任何脚本,只读取数据,用自己写的程序判定每一步:
- n = 1–3:按上文推导以 60 位精度与精确整数重算,并用本站验证器检查三个答案。
- n = 4–11 连续:自己枚举全部三角剖分并求每个图的半径(tools/p93-contact-graphs.py、tools/p93-contact-enum.cpp)。
- n = 4–11 网格:以 60 位精度重新推导 A、B、ε 与各盒,自己重建外逼近模型,逐一核对每片叶子的乘子(tools/p93-grid-certificates.py、tools/p93-n11-grid-certificate.py);n = 4–8 另用独立搜索复现。
- n = 15:全部类型界、结构证书与 33 个直方图(tools/p93-power-cell-certificates.py),以及局部化与 20 191 个节点的整数凸包树(tools/p93-n15-grid-certificate.py)。
每个 n 的检查耗时从几秒到几分钟(n = 11 的 368 119 个节点约 82 秒)。所有数值与包中一致,推理中没有发现错误。
贡献与范围
这些构型此前已知:n = 4–11 的最优排布由 David W. Cantrell(2011)给出,n = 6、10、15 的等圆三角阵见 Erich Friedman 的汇编。本证明说明它们是最优的,并确定了网格上的最高分。本项采纳的贡献记 zzzcy #308 一次永久 +2 证明分。
同一份证明包还证明了 n = 21、28、36、45 的连续最优值,本站已核验;这几档的网格分数仍可提高,将在第 6 周周赛结束(10 月 11 日)后处理。