- 主题:总面积大于3的有限个正方形是否一定能覆盖单位正方形?
rt,证明或否定,总面积大于3的有限个正方形一定能覆盖单位正方形
--
FROM 111.205.43.*
补充一下,正方形不允许倾斜摆放,所有的正方形的边必须和要覆盖的正方形的边平行
--
FROM 111.205.43.*
可以考虑一下,如果有这么一大堆正方形摆在你面前,总面积明显有富余
不过每个正方形上面也没写着边长,你也说不好有多大,你会怎样去尝试做这个覆盖?
--
FROM 111.205.43.*
感觉也有可能是对的,这个方法和我所知道的方法在手法上有一点点相似
【 在 littlestone9 的大作中提到: 】
: 大概明白了,
: 1.如果只有3个正方形,肯定可以,因为必有一个正方形面积大于,这1个就覆盖了
: 2.如果只有4个正方形,摆法为每个正方形摆一个角,设4个正方形边长分别为a1、a2、a3、a4,且1>a1>=a2>=a3>=a4(a1>=1的话,a1自己就覆盖了),可以证明a3+a4>=1,也就是最小的2个正方形也可以覆盖一条边。
: ...................
--
FROM 111.205.43.*
赞,至少我没看出有什么问题
【 在 littlestone9 的大作中提到: 】
: 完整证明来了。
: 前提说明1:下面的A1,A2,A3...An,都是正方形的边长,且按照大小排了序,也就是A1>=A2>=A3...
: 前提说明2:具体操作方法是,如果正方形个数n为4,7,10,13...,则用最小的4个正方形An,An-1,An-2,An-3去拼一个更大的正方形,4个正方形放4个角,如果An+An-1>An-3,则拼出来的更大正方形边长为An+An-1,否则,拼出来的其实就是An-3。拼出来的正方形放到原来的队列里去排序,再重复这个步骤,一直到最后拼成1个正方形。
: ...................
--
FROM 111.205.43.*
参考方案
只需讨论所有正方形边长均<1的情形
将正方形从大到小排列,让它们的上边缘对齐到一条水平线上
依次取出若干个,直到它们的总水平长度≥1
如此得到了一个像有锯齿的梯形一样的图形,设最右侧的正方形边长为A1
那么如果用这个图形来覆盖单位正方形,由于总长度≥1,高度最窄处为A1,所以至少可以覆盖单位正方形高为A1的一截
依次继续选出第二组总长度≥1的正方形,同理设最右侧的正方形边长为A2
如此继续,直到剩余部分不足以构成总长度≥1的图形,这部分图形(如有)舍弃不用
下面来证明S{An}≥1,如此便可覆盖整个单位正方形
考虑第一组图形
它的总长度必然<1+A1,否则在A1前一个正方形就已满足总长度≥1
它的高度最宽处是第一个正方形的边长,根据假设,它<1
于是它的面积≤(1+A1)*1,或者说是1+A1
考虑第二组图形
同理它的总长度必然<1+A2
它的高度最宽处是第一个正方形的边长,这个边长≤上一组最后一个边长,也就是A1
于是它的面积≤(1+A2)*A1,或者说是A1+A1*A2,放缩一下,它更是<A1+A2
以此类推,最后一组有效图形的面积<An-1 + An
最后剩余舍弃的图形,面积<An * 1,也即An
将上面所有面积相加,可知
1+2S{An} > 所有正方形总面积 ≥ 3
于是S{An}>1,可覆盖单位正方形,证毕
【 在 liushuoshu 的大作中提到: 】
: rt,证明或否定,总面积大于3的有限个正方形一定能覆盖单位正方形
--
FROM 111.205.43.*