初始问题
知乎上有人询问, 从一张理想的A4纸(1\times\sqrt{2})上裁剪出25个相等大小的正方形，边长最大可以达到多少？
显然，最大边长不小于\frac15。将A4纸去掉一端截成一个1×1正方形，可以裁成5×5个边长为\frac15的正方形。
图1
不过，这样裁掉的边角余料似乎太多了，从中甚至还可以再裁10个这样的正方形呢。（图1）
应该存在一个别致的布置，可以放下25个更大的正方形，否则题目就太平庸了。
如果所有的正方形都不歪不斜地平放的话，简单试验容易发现不可能更大。
那么必须至少有一个正方形是倾斜放置的！最容易想到的布置就是图2所示的4×6+1方案了。
图2
mathe和wayne经过计算，发现边长=\frac{1+\sqrt{2}}{10+\sqrt{2}}≈0.2115>\frac15.
这是最好的方案吗，还有更好的方案吗？让我们进行更多的探索。
渐近布置
让我们考虑“从一张长宽为(a×b)的纸上裁剪出 n 个相等大小的正方形，边长最大可以达到多少？”
如果 \frac ab 是一个有理数，则不妨假定a,b是一对互质的正整数，那么 ab|n 是最简单的情形，这时纸的利用率可达到100%，没有边角余料。
如果\frac ab 是一个无理数，就没有利用率100%的简单情形了。但是，在 \frac ab 的一个渐近分数 \frac pq（既约分数）附近， n=pq应是相对简单的情形，这时 p×q 的简单布置就可以得到很大的利用率。
比如对于A4纸，\frac75是\sqrt2的一个渐近分数，所以 5×7 的最简布置（图1）就可得到\frac7{5\sqrt2}≈0.98995的利用率。
凭直觉，图1的5×7应是最大布置。这一点不难证明。首先，这显然是无倾布置的最佳方案；其次，有倾布置的最大利用率应小于\frac{n}{n+1}（？）.
我们把与一个渐近分数相对应的铺成完整矩形的正方形布置称为渐近布置。
【定义】（渐近布置）与 \frac ab 的一个渐近分数 \frac pq 相对应的 p×q 个正方形布置称为一个渐近布置。
对于一般化的问题，\frac ab 为一个无理数似乎更为有料，因为涉及到渐近分数。而实际编排发现\frac ab=\sqrt2时尤为微妙，可能跟正方形的对角线与边长之比为\sqrt2有关。
可以预料，在渐近分数附近，最佳方案应该是渐近布置的某种调整。
渐近布置的调整
考虑 “从A4纸裁剪 n 个相同大小的正方形，边长最大可以达到多少？”的问题，由 n 从小到大积累经验，有助于我们解决 n=25 以及更大的问题。
我们看看有哪些较小的渐近布置。
为此我们需要先找到一些较小的渐近分数。
连分数是得到渐近分数的一个不错方法，\sqrt2由连分数得到的前10个既约渐近分数如下
可见分子分母之积增长很快。为了得到更多的渐近分数，可以使用上述既约分数的非既约分数，对于分子分母之积来说，就是乘以一个平方数。此外，由于\frac1{\sqrt2}=\frac{\sqrt2}2, 故由上述某个渐近分数 \frac pq 可以得到渐近分数 \frac{2q}{p}，即序列
从上述渐分数将分子或者分母进行微调（偏大者分子减1或者分母+1,偏小者反之）可以得到更多的渐近分数。
n≤42的较优布置方案
n=1,2,3,4,5,6的情形都比较简单，平放就好。不过n=3时也有一个斜置方案（图3），初显\sqrt2之微妙。
3个正方形，两种布置（左：2×2-2+1，右：2×2-1）
第一个必须用到倾斜布置的是7个正方形（图4）：
图4
我们把这种布置记为2×3+1。
n=8,9,10,11,12所有正方形都是平放的，图5是n=9,10,11,12的布置，都是由 n=3×4减少而得
图5
前面给出的25个小正方形方案还不是最优的，更优的是如下4×6-2+3的方案
此方案倾斜正方形边界和虚线平行或垂直
相对应的26个小正方形方案
此方案倾斜正方形方案同中间挖空部分左下到右上点的连线平行或垂直，而需要注意的各小正方形之间可以有很小的错位。
类似但是略有不同的21个正方形方案:
这时垂直和平行的特点消失了。
还有独特的17个正方形方案
渐近布置的调整方案我们记为p×q-□＋◇, 更多调整方案请查看链接列表
| n | p×q-□＋◇ | 边长 |
|---|---|---|
| 1 | 1* 1 | 1 |
| 2 | 1* 2 | 0.707107 |
| 3 | 2* 2-2+1=2* 2-1 | 0.5 |
| 4 | 2* 2 | 0.5 |
| 5 | 2* 3-1 | 0.471405 |
| 6 | 2* 3 | 0.471405 |
| 7 | 2* 3+1 | 0.376385 |
| 8 | 2* 4 | 0.353553 |
| 9 | 3* 4-3 | 0.333333 |
| 10 | 3* 4-2 | 0.333333 |
| 11 | 3* 4-1 | 0.333333 |
| 12 | 3* 4 | 0.333333 |
| 13 | 3* 4-2+3 | 0.289245 |
| 14 | 3* 5-1 | 0.282843 |
| 15 | 3* 5 | 0.282843 |
| 16 | 3* 5-1+2 | 0.257981 |
| 17 | 3* 5-3+5 | 0.252910 |
| 18 | 4* 5-2 | 0.25 |
| 19 | 4* 5-1 | 0.25 |
| 20 | 4* 5 | 0.25 |
| 21 | 4* 5-2+3 | 0.236625 |
| 22 | 4* 6-2 | 0.235702 |
| 23 | 4* 6-1 | 0.235702 |
| 24 | 4* 6 | 0.235702 |
| 25 | 4* 6-2+3 | 0.211521 |
| 26 | 4* 6-8+10 | 0.207318 |
| 27 | 4* 6-8+11 | 0.207106 |
| 28 | 4* 7 | 0.202031 |
| 29 | 5* 7-6 | 0.2 |
| 30 | 5* 7-5 | 0.2 |
| 31 | 5* 7-4 | 0.2 |
| 32 | 5* 7-3 | 0.2 |
| 33 | 5* 7-2 | 0.2 |
| 34 | 5* 7-1 | 0.2 |
| 35 | 5* 7 | 0.2 |
| 36 | 5* 7-1+2 | 0.180396 |
| 37 | 5* 7-3+5 | 0.180378 |
| 38 | 5* 8-2 | 0.176777 |
| 39 | 5* 8-1 | 0.176777 |
| 40 | 5* 8 | 0.176777 |
| 41 | 5* 8-1+2 | 0.168771 |
| 42 | 5* 8-3+5 | 0.168446 |
全部倾斜的布置
在探索地过程中还发现两种全部倾斜的构图，其最优性尚不能肯定。比如倾斜构造的29个正方形:
不断进化的27个正方形
由于4\times 7=28，根据经验，4\times 7个正放小正方形中去掉一个，得到模式4\times 7 -1对应边长\frac{\sqrt{2}}7=0.2020305是一个很不错的结果。
但是后来发现通过模仿26时的结果，但是将倾斜放置的小正方形从一排改为两排，可以得到一个不规则的更有结果.
![a27.1]https://bbs.emath.ac.cn/data/attachment/forum/202011/03/072552wht45z4lecc25krc.png
对应边长为0.2045372.
上面结果的不对称性促使我们继续寻找更优的结果，最终发现了边长为0.2049424的更新结果:
并且通过简单调整可以优化到0.2049735
uk702指出中间还有两个正放的正方形也可以倾斜放置, 利用这个思路，我们最终找到更加复杂的包含两种倾斜角度的方案
使得边长达到0.2071061.
并且发现26个正方形的也可以类似优化到0.2073180.
Leave a Reply