9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

覆盖与划分讲义(厦门双十黄雄)



覆盖与划分
厦门双十中学 黄雄

1.在有限的方格网上按下列要求覆盖着 1*2 的卡片:每张卡片的边缘与方格线对齐,没有 卡片落在方格网外,且每个方格恰被两张卡片覆盖。证明:一定可以移去一些卡片,使得每 个方格恰被一张卡片覆盖。 2.在边长为 11 的正方形中标有 2012 个点。证明:能用一个边长 为 12 的等边三角形覆盖至少 671 个点。

r />
3.如图, 边长为 7 的正三角形被分成 49 个边长为 1 的小正 三角形,问:最多可沿图所示的格线,划分出多少个邻边 长分别为 1 和 2 的平行四边形? 4.求正整数 n(n ? 3) , 满足 n ? n 的正方形能被图所示的图 形完全覆盖(既无间隙又不重叠的覆盖). 5. 求正整数 n(n ? 5) ,满足 n ? n 的正方形能被图所示的 图形完全覆盖(既无间隙又不重叠的覆盖) 6.考虑一个 11×10 的方格表,平行线将表格划分为 110 个单位正方形. 有一种形如十字架形状的瓷砖,它是由 6 个单 位正方形组成的,如图所示. 将瓷砖摆放在方格表中,试确定最多的不重叠摆放的瓷砖 数目,使得每一块瓷砖恰好覆盖表格中的 6 个单位正方形. 7.用 1×2 的瓷砖铺设 m ? n 的矩形区域, 瓷砖可以横放或竖放, 但不能迭盖或部分落在 m ? n 的矩形外,所有方格恰被瓷砖铺设一次,若一条直 线将区域分为两部分, 使得每一块瓷砖只属于同一部分, 则称此直线为 “可分的” . 证明: (1)用 1×2 的瓷砖铺设 4×2010 区域,对任一种铺法都存在一条可分的直线; (2)用 1×2 的瓷砖铺设 5×2010 区域,存在一种铺法找不出一条可分的直线. 8. 一 个 数 列 d1 , d 2 , ?, d n ( 不 必 不 同 ) 称 为 “ 覆 盖 数 列 ” :若存在形如

?ai ? jdi | j ? 0,1,??的等差数列,使得每个正整数至少在上述等差数列的一个数
列中,若不能删掉 d1 , d 2 , ?, d n 中的任何数,使得剩下的数列仍是覆盖数列,则 称此数列是“最小的”. (1)若 d1 , d 2 , ?, d n 是最小的覆盖数列, 且等差数列 ?ai ? jdi | j ? 0,1, ??可以覆 盖所有的正整数,素数 p 整除 d1 , d 2 , ?, d k ,但不整除 d k ?1 , d k ?2 , ?, d n ,证明:

a1 , a2 ,?, ak 模 p 的剩余包含所有的 0,1, ? , p ? 1;

(2)若 d1 , d 2 , ?, d n 中的每一个均只有一个素因数,试给出所有的覆盖数列 和最小覆盖数列. 9.已知一个在平面上被标记了的点集,满足任意三个被标记了的点都能被一个半 径为 1 的圆盘覆盖. 证明:这个被标记了的点集能被一个半径为 1 的圆盘覆盖. 10.定义一个“棋盘多边形” :以形如 x ? a或y ? b(a, b ? N ? ) 的直线作为边界形成 的图案,这些线将图形分割成了一个个单位正方形,且相间地染成黑色和白色. 而“平铺”一个棋盘多边形是用 1×2 的长方形刚好无重叠地铺满这个棋盘多边 形. 一个“完美平铺”则是一种不包含图 1 中的两个图案的平铺(在任意位置均 不能有这两种图案出现) , 图 2 中的两个 3×4 的棋盘多边形,第一个就是完美平 铺,因为上述两个图案均未出现过;而第二个则 不是,因为图案之一出现在了右上方的四个格子 里. 求证:(1)只要一个棋盘多边形能够被平铺,它就 肯定能被完美平铺. (2)这个完美平铺是唯一的. 11.

参考答案:
1.证明:任意选定一个覆盖两张卡片的方格以及其中的一张卡片。先选中该卡片覆盖的相 邻方格, 再选中该卡片覆盖的相邻方格, 再选中该相邻方格的另一张卡片。 继续同样的操作, 直至回到最初方格。 因为在所选的方格中,除了第一个之外,两张卡片均已选过了,所以,不会回到之前 选过的其他方格。 若将方格按国际象棋棋盘的方式染色,则奇数步之后到达一个异色的方格,偶数步之 后到达一个同色的方格。因此,选中的卡片的数目为偶数。 于是,可以移去偶数次选中的卡片。此时,经过的每个方格均恰被一张卡片覆盖。若 此后仍然有被两张卡片覆盖的方格,重复上面的过程。 因为所有恰被一张卡片覆盖的方格只由一张卡片与某个现在恰被一张卡片覆盖的方格 相连,所以,不会从覆盖有两张卡片的方格到达恰被一张卡片覆盖的方格。因此,经过有限 步之后,得到一个新的圈,从中移去偶数次选中的卡片。 重复上面的操作,直到所有的方格均恰被一张卡片 覆盖。

2.证明:如图,放置两个底边落在正方形的一条边所在的直线上,底边所对的顶点分别在 正方形的一组对边上,且边长为 12 的等边三角形。 这两个三角形的公共部分形成了一个边长为 1 的等边三角形。把第三个等边三角形旋 转 180 度放在前两个三角形之间,使其最下边的顶点与小三角形的最上边的顶点重合。 为了证明这三个三角形覆盖了整个正方形,只需证明大三角形与小三角形的高的和至 少是 11,即证:

3 (12 ? 1) ? 11 ? 13 3 ? 22 ? 3 ? 169 ? 484 2

显然成立。 因此,2012 个点中至少有 671 个点落到如上放置的三个三角形之一中。

3. 10 个. 如图,将 49 个小正三角形黑白相间地进行染色. 由于每个邻边长为 1 和 2 的平行四边形必须要包含 2 个白色的小三角形, 又 一共有 21 个白色小三角形,故满足题意的平行四边形的数目不超过 10. 图中给出了一种划分出 10 个平行四边形的方法.

4. 显然,3×3 的正方形能被 3 个 3×1 的矩形安全覆盖;4×4 的正方形能被 1 个 4×4 的正方形完全覆盖. 首先证明:5×5 的正方形不能被图中的任何图形完全覆盖. 因为 5×5 的正方形的方格总数是 25 个,显然不能只用 3×1 的矩形覆盖, 所以,必须用一个 4×4 的正方形,但不管怎样放置 4×4 的正方形,剩下的 9 个方格不能被 3 个 3×1 的矩形完全覆盖. 当 n ? 3k (k ? N ? ) 时, 因为对于 3k×3k 的正方形的每一列都可以被 k 个 3×1 的矩形完全覆盖,所以,3k×3k 的正方形可以被图中的图形完全覆盖. 同样的,3k×m 矩形和 m×3k 矩形可以被完全覆盖. 当 n ? 3k ? 4(k ? N ? ) 时,(3k ? 4) ? (3k ? 4) 的正方形可以划分为一个 4×4 的 正方形、一个(3k+4)×3k 的矩形和一个 3k×4 的矩形. 而 4×4 的正方形能被 1 个 4×4 的正方形完全覆盖. 由前面的结论, 知剩下的两个矩形可以被 3×1 的矩 形完全覆盖. 当 n ? 3k ? 8(k ? N ? ) 时,(3k+8)×(3k+8)的正方形可以划分为一个 8×8 的 正方形,一个(3k+8)×3k 的正方形和一个 3k×8 的 矩形. 而 8×8 的正方形可以被 4 个 4×4 的正方形 完全覆盖. 由前面的结论,知(3k+8)×3k 的矩形和 3k×8 的矩形可以被 3×1 矩形完全覆盖. 故满足题设的 n 为大于或等于 3,且 n ? 5 的全 部正整数. 5. 首先,如图可以看出下面的 5 个图形是满足题设

的完全覆盖. 当 n ? 10 时,设 n ? 5k ? r (0 ? r ? 5, k ? 2, k、r ? N ). 则 n ? 5(k ? 1) ? (r ? 5). 因为 k ? 2 ,所以,k ? 1 是正整数,可把 n×n 的正方形划分为一个(r+5)×(r+5) 的矩形,一个 n ? 5(k ? 1) 的矩形和一个 5(k ? 1) ? (r ? 5) 的矩形. 由前面得到(r+5)×(r+5)的正方形能被安全覆盖. 因为 5a×b 的矩形、c×5d 的矩形均能被 5×1 的矩形完全覆盖,所以,剩 下的两个矩形能被 5×1 的矩形完全覆盖. 故当 n ? 5 时,n×n 的正方形能被给出的两个图形安全覆盖. 6. 考虑表格边框的那条边的覆盖情形,特别是对于表格中的四个角的覆盖情形. 在每个角上放置一块瓷砖,仅覆盖 2 个单位正方形,同时,有 4 个单位正方 形没有被覆盖. 因此,在四个角上,有 16 个单位正方形没有被 覆盖. 下面讨论余下边框上的单位正方形的覆盖情 形. (1)在边长为 11 的这条边上,对于每一个覆盖, 仍有 2 个单位正方形没被覆盖, 则在边长为 11 的这 条边上最少有 2 个单位正方形没有被覆盖. (2)在边长为 10 的那条边上, 可覆盖一个单位正 方形且仍有一个单位正方形没有被覆盖. 由此,知边框上的单位正方形至少共有 16+4+2=22 个没有被覆盖. 因此,可被覆盖的单位正方形最多有 110–22=88 个. 因为每块瓷砖恰好覆盖 6 个单位正方形,所以,在此表格上最多摆放 14 块 瓷砖. 图中是其中一种摆放方法. 因此,在表格中摆放瓷砖的最多的数目是 14. 7. (1)假设存在一种无可分的直线的铺法.
) 列. 考虑第 k、k+1( 1 ? k ? 2009

易知,在这两列中存在一块水平瓷砖,否则,这两列之间存在一条竖直的可 分直线. 由此,在前 k 列有 4k 个方格,即偶数个. 又注意到,在前 k 列中,每块瓷砖恰覆盖两个方格,则在第 k、k+1 列有偶 数块水平铺设的瓷砖. 综上,水平铺设瓷砖数最少为 2.
) ,在第 k、k+1 列有 2 块水平瓷砖. 进而,这些瓷砖 对任意的 k (1 ? k ? 2009

共覆盖了 2×2009×2 个方格. 则对任意 i(1 ? i ? 3), 在第 i 、 i ? 1 列必有 1 块竖直 放置的瓷砖. 这些瓷砖共覆盖了 3×2 个方格. 所以,覆盖的方格总数为(2× 2009+3) ×2>2×2010×2. 这与题设共 4×2010 个方格矛盾,假设不真.

因此,结论成立. (2)用数学归纳法证明更一般的结论. 若 n ? 3 ,则 5×2n 的区域存在没有可分的直线铺法. (i)当 n=3 时,图中的铺法满足命题. (ii)假设对 5×2n 的区域结论成立,则至少有 4 块瓷砖竖 直铺设. 因此, 存在 1 个 k (1 ? k ? 2n ? 1) , 使得在第 k 列有 1 块竖 直铺的瓷砖. 接下来在第 k、k+1 列之间增加两列,记其为 k1 , k 2 . 将原第 k、k+1 列中水 平放置的瓷砖换成第 k、 k1 列和第 k2 、k+1 列各水平放 1 块. 又第 k 列中有 1 块 竖直放置的瓷砖,则第 k1 , k 2 列还没被全覆盖. 注意到,若在某一行中,第 k1 列对 应的格没盖住, 则第 k2 列相应的格也没盖住. 此时, 在这两个格铺 1 块水平瓷砖. 用这样的方法,可将新增加的两列全部铺完. 显然,在此过程中,没有新增水平可分直线. 在没变化的列中也没增加竖直 可分直线. 从而,在第 k1 , k 2 列至少有一块水平放置的瓷砖. 由于在原区域中,第 k、k+1 列间无可分直线,可知第 k、 k1 列和第 k2 、k+1 列方格均用水平瓷砖铺设. 从而,在这些列对中没有可分直线. 所以,5×2(n+1)区域不存在有可分直线的铺法. 综上,命题成立. 进而,所证结论为真. 8. (1)设等差数列 ?ai ? jdi | j ? 0,1, ??为 Si ? (i ? 1,2, ?, n) . 假设 a1 , a2 , ?, ak 模 p 的剩余中不含 r,则数列 S1 , S 2 , ?, S k 中没有数模 p 余 r 考虑等差数列 S ? ?r ? jp | j ? 0,1, ?? 则 S 与 S1 , S 2 , ?, S k 没有公共项,从而,S 可以被 Sk ?1 , Sk ?2 , ?Sn 覆盖. 先证明一个引理. 引理 若 正 整 数 d 、 d ? 互 素 , 则 等 差 数 列 ?a ? jd | j ? 0,1, ?? 和

?a? ? jd ? |

j ? 0,1, ??的公共项是一个公差为 dd?的等差数列.

证明 由中国剩余定理, 知这两个等差数列一定有公共项,且相邻的两项的 差是 d 和 d?的最小公倍数 dd?. 回到原理 由引理, 知 S ? Sk ?1 , S ? Sk ?2 , ?, S ? Sn 是公差分别为 pdk ?1 , pdk ?2 , ?, pdn 的等

差数列. 考虑映射 f : S ? ?0,1, ??,且满足 f ( x) ?
x?r p

则 f (S ? Sk ?1 ), f (S ? Sk ?2 ),?, f (S ? Sn ) 是公差分别为 d k ?1 , d k ?2 , ?, d n 的等差 数列. 因为 Sk ?1 , Sk ?2 , ?, Sn 可以覆盖 S 所以集合 f (S ? Sk ?1 ), f (S ? Sk ?2 ),?, f (S ? Sn ) 可以覆盖所有的正整数. 因此, d k ?1 , d k ?2 ,?, d n 也是一个覆盖数列,与 d1 , d 2 , ?, d n 是最小的覆盖数列 矛盾. (2) 设 d1 , d 2 , ?, d n 的素因数分别为 p1 , p2 , ?, pn , I i ? ?l ?{1,2, ?, n} | pi | dl ? (可以有相同的). 假设等差数列 Si ? ?ai ? jdi | j ? 0,1, ??可以覆盖所有的正整数. 下面证明:至少存在一个由若干个数列构成的集合 Gi ? ?Sl | l ? I i ?,也可覆 盖所有的正整数,即数列 ?dl | pi | dl ?是一个覆盖数列. 假设对于每一个 i ? ? 1,2, ?, n?, Gi 不能覆盖 ri ,设 Di ? ? dl
pi |dl

由中国剩余定理,知存在正整数 r,使得对于每一个 i ? ? 1,2, ?, n?,均有

r ? ri (modDi )
于是,r 不能被任何一个等差数列覆盖,矛盾. 接下来只要假设 di ? p ai 就足够了,其中,p 为素数, ? i 为正整数. 下面证明: ?d i ?是覆盖数列 ? ?
i ?1 n n 1 1 ? 1 , ?d i ?是最小覆盖数列 ? ? ? 1 di i ?1 d i

(i) 假设上述数列 Si 能覆盖所有的正整数,对任意正整数 N , Si 最多覆盖

?1,2,?, N ?中的 N ? 1 个数,于是, ? N ? 1 ? N ,即 ? 1
n n

di

i ?1

di

i ?1

di

?

N N ?1

由 N 的任意性知 ?
i ?1

n

1 ?1 di

(ii)若 ?
i ?1

n

1 ? 1 ,对 n 用数学归纳法证明这样的数列是覆盖数列. di

当 n=1 时,结论显然成立. 若 i 小于或等于 n ? 1 时,结论均成立. 当 i ?? 1,2, ?, n?时,设 ni 是 d1 , d 2 , ?, d n 中等于 p i 的个数,且假设 n0 ? 0 ,则 一定存在 i ,使得 ni ? p ,否则, ?
i ?1 n

?1 1 ? 1 ? ? ( p ? 1)? ? ? ? 2 ?p p ? ? 1 矛盾. di ? ?

将p个

n 1 1 1 用 1 个 来代替,则 的值不变,但是, di 的个数少了. ? i i ?1 p p i ?1 d i

由归纳假设,此时的数列能覆盖所有的正整数. 下面将一个公差为 p i ?1 的等差数列分成 p 个公差为 p i 的等差数列,即

d1 , d 2 , ?, d n 为覆盖数列.

(iii)假设 ?
i ?1

n

n d 1 ? 1 ,且 di ? d 2 ? ? ? d n ,则 ? n ? d n di i ?1 d i

因为

n n dn d 1 1 是整数,所以 ? n ? d n ? 1,即 ? ? 1 ? di dn i ?1 d i i ?1 d i

于是,删掉 d n 后, d1 , d 2 , ?, d n?1 仍为覆盖数列. 从而, d1 , d 2 , ?, d n 不是最小覆盖数列. 因此, d1 , d 2 , ?, d n 是最小覆盖数列当且仅当 ?
i ?1 n

1 ?1 di

9. 由题意知,任三个点集中的点都能被一个半径为 1 的圆覆盖,即知对任三个 点都存在一个点到这三点的距离不大于 1. 这就是说,若以点集中的每个点为圆心、1 为半径作圆,则任三个圆的交集 非空. 由于圆是凸集,故由海莱定理知,所有这些圆的交集非空. 因此,在这个交集中任选一点,它到所有点集中的点的距离都不大于 1. 显 然,以这个点为圆心、1 为半径的圆可将点集中的所有点覆盖. 10. (1)通过对多米诺骨牌个数 n 的归纳来证明第一部分. 对于 n=1,命题显然成立. 假设命题对于 n-1 块多米诺滑牌时的情形成立. 考虑 n 块骨牌的情形, 我们有一个用 n 块多米诺骨牌能够平铺的棋盘多边形, 在棋盘多边形最左边一列的方块中,选择最下面的一个标记为 L.

(i)若 L 是黑色的,在给定的平铺中,移除覆盖 L 的多米诺骨牌,剩余一个 能被 n-1 块多米诺骨牌平铺的多边形,通过归纳假设,这个棋盘多边形能够被完 美平铺. 现在放回被移除的多米诺骨牌. 如果这块多米诺骨牌是水平的,由于正方形 L 是黑色的,并且在棋盘多边 形的最下面,则保证增加的平铺仍然是完美的; 如果这块多米诺骨牌是垂直的, 若不把另一块多米诺骨牌直接垂直地放在它 的右边,n 个骨牌的平铺仍然是完美的,否则,旋转不完美的多米诺骨牌对,得 到两个水平的多米诺骨牌. 只要重复这个过程——移除水平的覆盖 L 的多米诺骨牌,平铺剩余的,替 换多米诺骨牌——则将能得到一个完美的平铺. (ii)若 L 是白色的,通过进行相似的操作,同样可以得到完美的平铺. 此时, 如果覆盖 L 的多米诺骨牌是水平的,而且有另一块水平的多米诺骨牌直接放在 它的上面,才会遇到困难. 旋转这个多米诺骨牌对,移除旋转后覆盖 L 的多米诺 骨牌,使用归纳假设得到剩余图形的完美平铺,再恢复垂直的多米诺骨牌,便可 得到一个新的完美平铺. (2)假设存在给定棋盘多边形的两个完美平铺,通过将这两个平铺叠放,每 个方块均是两个平铺中的多米诺骨牌的一部分,可以获得相交的多米诺骨牌链. 例如,对于长度是 1 的链两种平铺是相同的;对于长度是 2 的链不可能出现,否 则,在 2×2 的棋盘中会出现一种由水平多米诺骨牌平铺的覆盖,另一种由垂直 多米诺骨牌平铺的覆盖,这两个图案中将有一个是不完美的. 由于会出现长度不小于 3 的链,设 R 是由其中一条链连同它的内部一起所 组成的区域(这样的链完全占有一个区域是可能的,因此,仅有链中的一些多米 诺骨牌与 R 外的正方形邻接) . 注意链的最下一行必定包含一块沿着水平方向的 多米诺骨牌. 如果有两块水平相交的多米诺骨牌,则其中之一将是一块 WB(白 黑)多米诺骨牌,即白块在左、黑块在右的多米诺骨牌. 否则,存在两块邻接的 垂直多米诺骨牌与单块水平多米诺骨牌相交,与它们是完美平铺的一部分矛盾, 因此,一定有一块 WB 多米诺骨牌(设为 X).现在把注意力集中在包含 WB 多 米诺骨牌的平铺上. 在 WB 多米诺骨牌上面的两个正方形必定是 R 区域的一部分,且单块水平 多米诺骨牌不可能覆盖它们两者,一对垂直多米诺骨牌也不可能覆盖它们两者 (否则,将出现非完美图形). 因此,一块水平多米诺骨牌恰好覆盖这两个正方 形中的一个,并且也是 WB 型的. 于是,能够推导出在上一行存在水平 WB 多米 诺骨牌,依次向上讨论直到有一块水平 WB 多米诺骨牌在它上面的两个方块不 都在区域 R 内. 因此,这块多米诺骨牌(设为 Y)必定是定义的区域 R 链的一部 分. 现在想像一枚棋子沿着这条链从区域 R 最下面一行的 WB 多米诺骨牌 X 的 白方块开始移动, 第一步向着这块 WB 多米诺骨牌的黑方块走一步. 在这条链上 沿着每一块多米诺骨牌行进的各个方向画一个箭头. 由于方块都是白黑相间的, 这些箭头将总是从白方块指向黑方块. 此外,当这枚棋子开始绕行时,由于初始 时区域的内部都是在这枚棋子的左边,无论何时沿着 R 边界移动,区域的内部 总在这枚棋子的左边. 但是, 现在遇到了一个矛盾. 前面推导出存在一块水平 WB 多米诺骨牌 Y 是 链的一部分, 且是与 R 边界相邻的, 在它上面有一个不是区域 R 部分的方块. 由

于当这枚棋子开始绕行时 R 内部在这枚棋子的左边,这块多米诺骨牌必定是从 右到左行走的. 因此,必然存在一个指向左边的箭头,意味着它必定是一块 BW 多米诺骨牌,与假设它是 WB 骨牌矛盾. 11.解答如下:



更多相关文章:
覆盖与划分讲义(厦门双十黄雄)
覆盖与划分讲义(厦门双十黄雄)_学科竞赛_高中教育_教育专区。2014希望联盟数学夏令营(兰州一中)覆盖与划分厦门双十中学 黄雄 1.在有限的方格网上按下列要求覆盖着 1...
厦门市参加2010年福建省高一数学竞赛
厦门双十中学 厦门外国语学校 同安一中 厦门双十中学 指导教师 黄雄 陈兆坚 黄文忠 张树亮 王娴静 黄雄 黄雄 肖骁 肖骁 王娴静 徐艳 黄雄 肖骁 钟旗法 黄雄 肖骁...
厦门市参加2010年福建省高一数学竞赛
厦门市参加2010年福建省高一数学竞赛_专业资料。厦门市参加 2010 年福建省高一...厦门双十中学 指导教师 黄雄 陈兆坚 黄文忠 张树亮 王娴静 黄雄 黄雄 肖骁 肖骁...
厦门双十中学关于2013-2014学年度考核优秀教职员工的公示(编内)doc
厦门双十中学关于2013-2014学年度考核优秀教职员工的公示(编内)doc_其它考试_...(10 人) :张瑞炳、黄雄、马乐清、丰小燕、余永平、李信任、 许波、张建怀、...
厦门市参加2010年福建省高一数学竞赛
厦门双十中学 厦门双十中学 厦门外国语学校 厦门一中 厦门双十中学 厦门双十中学 ...黄雄 陈兆坚 黄文忠 张树亮 王娴静 黄雄 黄雄 肖骁 肖骁 王娴静 徐艳 黄雄 ...
更多相关标签:
重叠等于未覆盖讲义    植被覆盖度划分标准    集合的划分和覆盖    网络覆盖范围的划分    集合的划分与覆盖    拨备覆盖率    word打字覆盖后面的字    除渣覆盖剂    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图