()bry
2021-02-20T16:03:32+00:00
用1*2的长方形覆盖5*5的正方形，可以横放或竖放，长方形不能重叠。在无法继续放置长方形的情况下，最多有多少个小正方形不被覆盖(即空着)?
答案是显然的，即最多7个，如图是一种摆法：
[img]https://img.nga.178.com/attachments/mon_202103/02/-7Q16r-1449KdT1kSau-ao.jpg[/img]
问题是有没有正经的证明过程或步骤呢？目前有的一些想法是：
因为放置的是1*2的长方形，那么空格的数量，即25-2n一定是奇数(1,3,5,7,9...)。那么也许只需要证明9个空格的情况不可能？因为7个的情况已经做出来了，那么一定是最多的。
按题设 m个长方形和n个正方形组成的边长为k的大正方形
经观察得出结论有m≥n
只要证明了这个结论 就可以计算出当k=5的时候
2m+n=25，m≥n
n最大为7
现在问题变成了怎么证明m一定是大于等于n
思路可以考虑反证法 假设m小于n 然后推导出当m小于n时 必定有2个以上的n正方形相邻 所以假设不成立
粗看了下这个应该是vertex cover的变异版吧 实际上就是求最少放多少个长方体
将大正方形纸剪成宽度为1的纸带，纸带为正方形和长方形交错排列，当无法交错时则剪断，则可以得到一个或多条纸带，这些纸带有三种情况：
1.正方形开头和正方形结尾(正方形比长方形多一个)
2.正方形开头和长方形结尾(正方形和长方形一样多)
3.长方形开头和长方形结尾(长方形比正方形多一个)
由于正方形不能相邻，因此情况1的纸带最多只能有1条，即正方形的数量最多只能比长方形多一个。
(借鉴1楼)由m个长方形和n个正方形拼成边长为5的正方形，有2m+n=25，m≥n-1，有3n≤26且n为奇数，于是n最大为7
[quote][pid=496941715,25736701,1]Reply[/pid] Post by [uid=7162512]ww55126449[/uid] (2021-03-02 01:47):
将大正方形纸剪成宽度为1的纸带，纸带为正方形和长方形交错排列，当无法交错时则剪断，则可以得到一个或多条纸带，这些纸带有三种情况：
1.正方形开头和正方形结尾(正方形比长方形多一个)
2.正方形开头和长方形结尾(正方形和长方形一样多)
3.长方形开头和长方形结尾(长方形比正方形多一个)
由于正方形不能相邻，因此情况1的纸带最多只能有1条，即正方形的数量最多只能比长方形多一个。
(借鉴1楼)由m个长方形和n个正方形拼成边长为5的正方形，有2m+n=25，m≥n-1，有3n≤26且n为奇数，于是n最[/quote]老哥你这个我有点没看懂
剪成一条是什么样的 那长方形如果是占两条的位置时是把它剪断么？
[quote][pid=497449366,25736701,1]Reply[/pid] Post by [uid=40822731]苏珞[/uid] (2021-03-03 23:56):
老哥你这个我有点没看懂
剪成一条是什么样的 那长方形如果是占两条的位置时是把它剪断么？[/quote]剪的时候可以转向，不能破坏基础图形，剪到不满足正方形和长方形交错排列的时候才剪断。