A4正方形

dlpg070

王守恩 发表于 2020-10-24 19:31
应该还有更好的吧？心里没底。
先往前走一走，看能不能找出什么来。
+2不是最优解(目前为止)，+1有最 ...

mathe 21# 29个和王守恩22#数据99个的验算结果
验算中除了平放和1个立放(歪放)外还考虑了个2个立放(歪放),待加入28#的斜放
计算机自动计算,没有人工干预
结果和他们的数据相同,除了2个数 n=26 ,n=56 待深入研究,没有2个立放的情形
发现几个不同构型正方形边长相同的情形:


dlpg070                              王守恩
n=9 ,9 =3X3 + 0 a=1/3 = 0.333333 === 9 =3X4 -3  a=1/3
n=29,29=5X6  -1 a=1/5 = 0.2      === 29=5X7 -6  a=1/5
n=30,30=5X6 + 0 a=1/5 = 0.2      === 30=5X7 -5  a=1/5
n=42,42=6X7 + 0 a=1/6 = 0.166667 === 42=6X8 -6  a=1/6
n=78,78=8X10 -2 a=1/8 = 0.125    === 78=8X11-10 a=1/8
n=79,79=8X10 -1 a=1/8 = 0.125    === 79=8X11-9  a=1/8
n=80,80=8X10+ 0 a=1/8 = 0.125    === 80=8X11-8  a=1/8
n=98,98=9X11 -1 a=1/9 = 0.111111 === 98=9X12-10 a=1/9
n=99,99=9X11+ 0 a=1/9 = 0.111111 === 99=9X12-9  a=1/9

mathe

大部分紧挨着正放的情况，歪着放的应该只可能一个。
四个以上歪着放的很容易淘汰掉。对于一个歪着放的正方形，对应水平和垂直方向各自产生一条缺口，那么两个缺口宽度之和必须是小正方形的边长之和的$\sqrt{2}$倍。
假设小正方形边长为a, 如果有两个歪着放的正方形在同一个水平线，对应缺口宽度为b,另外一个方向缺口为$c_1,c_2$.那么如果$c_1+c_2 \ge a$,显然结果不是最优的，我们只要将两个垂直方向缺口合并，就得到一个宽度不小于1的缺口，垂直方向至少可以添加两个以上小正方形，产生更好的结果。
所以$c_1+c_2 \gt a$, 但是$b+c_1=\sqrt{2}a, b+c_2=\sqrt{2} a$, 由此得出$a\lt b \lt (\sqrt{2}-\frac{1}{2}) a=0.914... a$
也就是b的可选机会很小很小。
而且进一步很简单可以判断出一行三个歪着的正方形完全不可以，同样两行两列四个以上歪着的正方形也不可以。

mathe

28#到29#方案关键信息是假设倾斜角度为$\theta$,正方形边长为$a$,每排n个正方形。于是横向约束给出了$a(\sin(\theta)+n\cos(\theta))=1$.
其中我们仅考虑$a\gt 1/n$的情况（可以通过设$a=1/n$给出上面方程$\theta$的临界值，略微超越临界值就可以得出一组候选解）。
而垂直方向，根据上下两边接触的点的不同可以列出另外一条约束方程给出一组候选解

王守恩

mathe 发表于 2020-10-28 14:43
大部分紧挨着正放的情况，歪着放的应该只可能一个。
四个以上歪着放的很容易淘汰掉。对于一个歪着放的正方 ...

歪着放的最优解，当然是指：歪着放比全部是正放的会更优
那么，歪着放的只可以是一个正方形，好像只有以下可能
注意：中间这个数恰好(不多也不小)是2,3,4,5,6,7,8,9,...
3=1×2+1
7=2×3+1
13=3×4+1
16=3×5+1
25=4×6+1
36=5×7+1
41=5×8+1
55=6×9+1
71=7×10+1
89=8×11+1
97=8×12+1
118=9×13+1
141=10×14+1
151=10×15+1
177=11×16+1
205=12×17+1

王守恩

mathe 发表于 2020-10-28 14:50
28#到29#方案关键信息是假设倾斜角度为$\theta$,正方形边长为$a$,每排n个正方形。于是横向约束给出了$a(\si ...

55个正方形最优解=\(\frac{\sqrt{2}+1}{\sqrt{2}+15}=0.1470806721\)
63个正方形最优解=\(\frac{1}{7}=0.1428571428\)
28#到29#方案应该是在这两者之间。

王守恩

mathe 发表于 2020-10-28 12:37
上图中取倾斜角度为16.735886895369516302492383471954808726度，边长为0.1430317103546470317344428027897 ...

而查看这个图，感觉59个正方形还有更优秀的
NSolve[{Sin[a] + 9/Cos[a] ==Sqrt[2]/x, (Sin[a] + 7)^2 - (Sin[a] + 2/Cos[a])^2 ==1/x^2, \[Pi]/2 > a > 0}, {a, x}]
{{a -> 0.309814, x -> 0.144976}}
同理，29个正方形
NSolve[{2Sin[a] + 6/Cos[a]==Sqrt[2]/x, (Sin[a]/Cos[a] + 5)^2 - (2Sin[a] + 1/Cos[a])^2==1/x^2,\[Pi]/2> a >0},{a, x}]
{{a -> 0.376616, x -> 0.196753}}

dlpg070

王守恩 发表于 2020-10-24 19:31
应该还有更好的吧？心里没底。
先往前走一走，看能不能找出什么来。
+2不是最优解(目前为止)，+1有最 ...

仔细分析计算结果后,确认发现2个立放的最优解
1 n=26 水平优于垂直
n=26 4x6+2垂直 a= 0.202884, b=0.188465,  c= 0.0984557
n=26 4x6+2水平 a= 0.203332, b=0.0933354, c= 0.19422
2 n=56 垂直优于水平
n=56 6x9+2垂直 a= 0.143283, b=0.140301,  c= 0.0623323
n=56 6x9+2水平 a= 0.1427,   b=0.0718988, c= 0.12991

mathe

补上dlpg070的n=26对应的图:

mathe

32#除了a和角度关系式，极值应该上下边还各有格点，给出两个额外约束.
于是得出一般情况方程组可以为
\(\begin{cases}(u\sin(\theta)+\frac{w}{\cos(\theta)})a-\tan(\theta)=\sqrt{2}\\(\sin(\theta)+n\cos(\theta))a=1\end{cases}\).
其中w代表从落在顶上线的点到落在底上线的点之间平行线间隔数目。
比如下面给出了一部分解（仅选择$a\gt \frac 1 n$). 现在的问题是如何比较方便的计数对应情况可以最多有多少个正方形落在A4纸

u	w	n	a	$\theta$	支持数目
2	9	7	0.171794	0.745661	37
3	9	7	0.16506	0.683685	41
4	9	7	0.159075	0.617481	43,45
5	9	7	0.153965	0.548355	47,48
6	9	7	0.149825	0.478408	50,51
7	9	7	0.146679	0.410443	54,55
8	9	7	0.144464	0.347504	55,57
9	9	7	0.143032	0.292096	58,59
10	9	7	0.142184	0.245492	59,60
2	10	7	0.158347	0.608481	44
3	10	7	0.152621	0.527381	49
4	10	7	0.147789	0.436516	52,53
5	10	7	0.144076	0.334172	57,58
11	8	7	0.144620	0.352615	54,55,56

mathe

42应该可以找到更优结果

u	w	n	a	$\theta$	支持数目
3	8	6	0.183732	0.628017	32
4	8	6	0.176837	0.542446	34,35
5	8	6	0.171471	0.453344	38
6	8	6	0.167764	0.365788	40,41
3	9	6	0.167805	0.366985	40
2	9	6	0.174828	0.512289	36
2	7	6	0.211093	0.843197	26
3	7	6	0.201067	0.778658	26
4	7	6	0.192109	0.708927	28,29
5	7	6	0.184444	0.635687	31
6	7	6	0.178221	0.561585	33,34
7	7	6	0.173466	0.489896	36,37
8	7	6	0.170055	0.42378	38,38,40
9	7	6	0.167753	0.365454	40,41,42
10	6	6	0.171685	0.457522	36,37,38
11	6	6	0.169374	0.408115	38,39,40
12	6	6	0.167748	0.365297	40,41,42