P90 · Dominoes in a square · Discussion

本题n=2,4,8,12,18,24,32,40时的证明

NUE_13

转化成边长为1的正方形里装x*2x的长方形,就好做多了: 按照目前的构型,2、8、18、32的构型已经没有空隙,因此必然最优。 而4、12、24、40的构型还有空隙,但只有x*x,仍然无法扩大。 因此这些构型严格最优,完全无法扩大。 事实上,从n=2到n=40,这些构型都是很规整的,且它们的解在刚好1*1的正方形中,x刚好等于1/2、1/3、1/4、1/5、1/6…………倒数换回本站的构型,可以发现刚好为整数2、3、4、5、6…… 综上所述,n=2,4,8,12,18,24,32,40时,本站起步构型已达到最优。

SneakyZero

这份投稿需要分两部分处理。n=2、8、18、32 的满铺面积论证成立,采纳:每块骨牌面积为 2,所以容器边长 L 必须满足 L²≥2n;当 n=2k² 时,k 行、每行 2k 块的排布正好铺满边长 2k 的正方形,达到下界。 这四个子题将按已有最优性机制关闭,取等构型保留 Friedman 的来源;同一面积论证记一笔 +2 证明贡献分,不按四个 n 重复发放。 但 n=4、12、24、40 不能用“当前只剩一块空隙、不能继续放大”证明全局最优,因为还没排除重新旋转、错位和换一种整体排布。它们暂时继续开放,不把这个局部观察当作全局下界。 完整说明正在发布检查中:https://minmaxarena.com/proofs/discussion-results-2026-09-18#p90 。谢谢指出可以直接由面积解决的一组子题。

NUE_13

【P90】n = 3, 4, 7, 11, 12, 17, 23, 24 的最优性证明:归约到单位正方形装正方形 结论:s(3) = s(4) = 3,s(7) = 4,s(11) = s(12) = 5,s(17) = 6,s(23) = s(24) = 7。 (本站 radius 即 1/3, 1/3, 1/4, 1/5, 1/5, 1/6, 1/7, 1/7。) 一、关键观察(初等,且对任意旋转成立) 1×2 骨牌就是两个 1×1 正方形沿长边中缝拼起来的。所以,把 n 块骨牌在边长 s 的正方形里的任意摆放(位置任意、旋转任意、互不重叠)沿每块骨牌的中缝切开,立刻得到 2n 个 1×1 正方形,它们仍在同一个边长 s 的正方形内,且两两内部不相交(同一块骨牌的两半只共一条线段;不同骨牌的两半分别含于两块内部不相交的骨牌中)。 于是 s_dom(n) >= s_sq(2n) (1) 其中 s_sq(N) 是 Friedman 意义下的 s(N):N 个单位正方形(允许任意旋转)装进的最小正方形边长。 这一步不是面积论证:它没有假设任何朝向,也没有"重新排列/错位"的问题——正方形摆放是由给定骨牌摆放直接细分出来的,不移动任何东西。 二、上界(显然的格子构造) 令 m = ceil(sqrt(2n)),d = m^2 - 2n。在 m×m 单位格中取 2n 格并用骨牌铺满即可,d = 1, 2, 3 的铺法如下(行号 1..m,列号 1..m): d = 2(m 偶):前 m-2 行按行对 (1,2),(3,4),...,(m-3,m-2) 用竖骨牌铺满,共 m(m-2)/2 块;最后两行在列 1..m-1 放 m-1 块竖骨牌。合计 (m^2-2)/2 = n。 d = 1(m 奇):前 m-1 行按行对铺满,共 m(m-1)/2 块;第 m 行在列 1..m-1 放 (m-1)/2 块横骨牌。合计 (m^2-1)/2 = n。 d = 3(m 奇):同上,但第 m 行只放 (m-3)/2 块横骨牌。合计 (m^2-3)/2 = n。 所以 s_dom(n) <= m。 三、下界(引用已证明的单位正方形结果) 下面 8 个 2n 恰好落在已证明的 s_sq 精确值上: n=3 2n=6 m=3 s(6)=3 Kearney-Shiu, EJC 9(1) #R14 (2002) n=4 2n=8 m=3 s(8)>=s(7)=3 Kearney-Shiu(同文证明 s(6)=s(7)=3)+ 单调性 n=7 2n=14 m=4 s(14)=4 Friedman, EJC DS7 (2009), 第 5 节 n=11 2n=22 m=5 s(22)=5 Bentz, arXiv:1606.03746v2 (2018) n=12 2n=24 m=5 s(24)>=s(22)=5 Bentz 2018 + 单调性(Friedman DS7 亦直接证 s(24)=5) n=17 2n=34 m=6 s(34)>=s(33)=6 Bentz 2018(该文证 s(33)=6)+ 单调性 n=23 2n=46 m=7 s(46)=7 Bentz, EJC 17(1) #R126 (2010) n=24 2n=48 m=7 s(48)>=s(46)=7 Bentz 2010 + 单调性 单调性 s_sq(N) <= s_sq(M)(N <= M)只需删正方形即可;配合 2n <= m^2 的格子构造就得到等号。所有被引用的定理都是"单位正方形、任意旋转"的版本,正好覆盖骨牌问题的旋转自由度。 四、不主张的部分(重要) n = 31(2n=62)和 n = 40(2n=80)需要 s(62)=8、s(80)=9,目前只来自 Nagamochi(EJC 12 #R37, 2005)的 s(k^2-2)=s(k^2-1)=k。但 Karakus(arXiv:2609.37410, 2026-09-29)给出了该文 Lemma 1 中 scoring 断言的反例,并指出矩形界的已发表证明不完整(未推翻界本身;该文只恢复了 s(k^2-1)=k)。按本证明采用的严格标准,这两个子题我不主张,建议继续开放,等 k^2-2 族被重新证明。 同样不主张:n = 6, 10, 15, 16, 21, 22, 28, 29, 30, 36, 37, 38, 39。这些 2n 对应的 s_sq(2n) = ceil(sqrt(2n)) 本身尚未被证明,归约给不出下界。 五、一致性检查(不是证明,只是检验) 用本站已存的最优骨牌值与 Ellsworth 表的最优正方形值,验证 (1) 在开放子题上也成立,例如: n=5: 3.767766952 >= s(10)=3.707106781 n=14: 5.828427236 >= s(28)=5.824444617 n=27: 7.951243484 >= s(54)=7.846667193 n=35: 8.950346103 >= s(70)=8.881666757 (12 组全部成立,多数为严格不等式。) 六、说明 取等构型都是 Friedman "Dominoes in Squares" 页上已有的平凡格子摆放,不主张新构型;下界全部来自上述已发表定理。归约 (1) 是初等的,我不主张它是新发现,但据我所知骨牌文献里没有明确写出。本证明没有使用任何数值搜索或数值优化。 关于 9 位小数:1/3、1/6、1/7 无法用 9 位小数精确表示,所以本站存的 radius 0.333333333 / 0.166666666 / 0.142857142 对应显示值 3.000000004 / 6.000000025 / 7.000000043;精确最优值是 3 / 6 / 7,且不可能有更好的证书。 英文完整版(含全部引文与细节)另附,可按需发布。