A4正方形

dlpg070

mathe 发表于 2020-10-31 11:18
98~102的更优解

58#数据得来不易,斜排效果明显,但不是斜排必定好于其它排列方式
下面是斜排与其它方案的比较:
1        6        11        9        0.125444        0.6049        75        2        0.125        True
2        7        11        9        0.122312        0.555055        79        3        0.125        False
3        8        11        9        0.119641        0.505576        83        4        0.118261        True
4        9        11        9        0.117425        0.457521        88        2        0.117851        False
5        10        11        9        0.115639        0.411914        91        5        0.112739        True
6        11        11        9        0.114241        0.369618        95        4        0.111111        True
7        12        11        9        0.113173        0.331219        96        5        0.111111        True
8        13        11        9        0.112377        0.296985        99        6        0.111111        True
9        14        11        9        0.111793        0.266888        101        7        0.111111        True
10        4        12        9        0.124944        0.597432        76        2        0.125        False
11        5        12        9        0.121565        0.541967        80        2        0.125        False
12        6        12        9        0.118645        0.484926        85        1        0.117851        True
13        7        12        9        0.116217        0.42752        90        2        0.117851        False
14        8        12        9        0.114293        0.371344        94        4        0.111111        True
15        9        12        9        0.112854        0.31824        98        3        0.111111        True
16        10        12        9        0.111848        0.270002        100        5        0.111111        True
17        11        12        9        0.111196        0.22796        102        5        0.111111        True
18        6        13        9        0.112069        0.281838        99        3        0.111111        True
19        5        13        9        0.114404        0.374957        93        1        0.111111        True

mathe

取底边上接触点为原点，并且顺时针旋转$\theta$建立坐标系，并且放大$\frac{1}{a}$倍得出
底边$y=-\tan(\theta)x$, 右边$y=\frac{x-s}{\tan(\theta)}$,左边$y=\frac{x+n-s+\tan(\theta)}{\tan(\theta)}$, 上边$y=\sqrt{2}\tan(\theta)+n-tan(\theta)x$.
而平行横线为方程$y=h$,$h$为整数。

mathe

另外48#的公式里面可以得出:
\(u \sin(\theta)\cos(\theta) +w=(\cos(\theta)+\sqrt{2}\sin(\theta))(\sin(\theta)+n\cos(\theta))=\sqrt{2}\sin^2(\theta)+(n\sqrt{2}+1)\cos(\theta)\sin(\theta)+n\cos^2(\theta)\)
即\((w-\sqrt{2})\sin^2(\theta)+(u-n\sqrt{2}-1)\sin(\theta)\cos(\theta)+(w-n)\cos^2(\theta)=0\)
所以
\((w-\sqrt{2})\tan^2(\theta)+(u-n\sqrt{2}-1)\tan(\theta)+(w-n)=0\)
于是我们转化为只含一个满足二次方程的变量\(\tan(\theta)\)的问题(或者可以转化为四次整系数方程的根)，而其中参数u,n,w,s都是整数, 并且要求$w\ge 0, n\ge 1, 2\le u \le 2n, 1\le s \le \frac{u}2$
而且根据几何意义，我们还可以添加限制$0\le \tan(\theta) \le \sqrt{2}$.

于是对于每个n,我们可以先穷举整数w,u使得上面方程有实数根，由于要求二次方程根的判别式大于0，而且要求 $2\le u \le 2n$, 满足上面条件的(u,w)显然是有限的。
于是对于每个满足条件的组合和对应的根$\tan(\theta)$, 计算所有直线$y=h$和楼上矩形四条边的交点横坐标，可以判断出每条$y=h$被矩形截断的线段的横坐标范围。相邻两段这样的线段的横坐标公共范围确定了两条平行线之间可以放置的正方形数目。上面过程如果数值计算，缺点是有时候点很靠近边界时很难准确判断是否落在线段上或边界内外，而利用数学软件还应该可以进行符号运算准确判断正方形的数目。

mathe

mathe 发表于 2020-10-31 17:49
试着让计算机计算了一下，不过数数目的代码应该还有些bug,所以部分数据可能不精确，但是的确找出n=26时更好 ...

60#的斜线模式使得我们找到边长为0.203552的26个正方形方案。通过抹去最上面两排5个正方形并且去除第三排一个正方形而仅保留四个活动的正方形
然后重新摆放六个正向摆放的正方形，计算结果表示可以达到更好的结果（图上红色标识的点是关键点，两个方向的正方形在这里相遇）:
倾斜角度0.46940486925148214431031752385349322966
边长0.20360196761968568290769151202756675595


这个结果表示更加优秀的结果很可能是某些类似的混搭模式，比如26个正方形的方案，是否右下方也可以改为部分正向摆放的正方形呢？

王守恩

mathe 发表于 2020-11-1 10:15
60#的斜线模式使得我们找到边长为0.203552的26个正方形方案。通过抹去最上面两排5个正方形并且去除第三 ...

树个强一些的路杆，也会被超越吗？
边长是1/n的正方形，最多可以放a(n)个。
a(1)=1
a(2)=4
a(3)=12
a(4)=20
a(5)=35
a(6)=48
a(7)=63
a(8)=88
a(9)=108
a(10)=140
a(11)=165
a(12)=192
a(13)=234
a(14)=266
a(15)=315
a(16)=352
a(17)=408
a(18)=450
a(19)=494
a(20)=560
a(21)=609
a(22)=682
a(23)=736
a(24)=792
a(25)=875
a(26)=936
a(27)=1026
a(28)=1092
a(29)=1189

mathe

25个正方形竟然找到了更加好的结果，方程$(6x-\sqrt{2})^2+(4x-1)^2=x^2$的较小根: 0.21152082398998605222225079755549315731

其中需要注意的是三个小正方形的方向不是45度倾斜，而是边分别和虚线平行和垂直。

mathe

类似上面图的分布，26个正方形可以更新为:0.20710678118654752440084436210484903928(方程(2*a+1-4*a)^2+(2*a+sqrt(2)-6*a)^2-16*a^2=0的根）

mathe

13个正方形可以首先用这种方案提升,边长为0.28803075780430984608768922939498297565，中间倾斜正方形的边的斜率为0.84179555985365425986427975960644427277


这种模式设横向m个正方形，纵向n个正方形，边长为a, 于是横向空$b=1-m a$,纵向空$c=\sqrt(2)-n a$, 如果倾斜角为$\theta$,
于是\(\begin{cases}a(\cos(\theta)+\sin(\theta)\le a+b \\ (a+b)\cos(\theta)+(2a+c)\sin(\theta)\le 3a \\ (b\sin(\theta)+c\cos(\theta)\le a\end{cases}\)
上面三个不等式至少两个取等号而且另外一个不等式成立时取到极值。

而更加优秀的方案有:

mathe

16个正方形边长0.25798106084869333926917606053815756044
$(\sqrt(2)-5x)^2+(1-3x)^2=x^2$的根

mathe

17个正方形边长为0.25290961912236896011578682554734919079，中间倾斜角度为0.54381491918201212935952758721403251413