高中数学竞赛讲义-涂色问题2069.pdf

《高中数学竞赛讲义-涂色问题2069.pdf》由会员分享，可在线阅读，更多相关《高中数学竞赛讲义-涂色问题2069.pdf（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、梦想不会辜负每一个努力的人.-1-29 涂色问题 涂色问题是数学竞赛中较为典型的问题，可以直接用抽屉原则解决涂色问题。另一方面，也可以将别的有关问题“涂色”，转化为涂色问题，涂色问题本身，有其深刻的数学背景。有些问题，本来就属于图论的内容。有些问题的解决，则需要用到数论、组合数学的理论和方法。这里介绍，只是中学数学竞赛中的有关问题。1 小方格染色问题 最简单的染色问题是从一种民间游戏中发展起来的方格盘上的染色问题.解决这类问题的方法后来又发展成为解决方格盘铺盖问题的重要技巧.2 线段染色和点染色(1)线段染色.较常见的一类染色问题是发样子组合数学中图论知识的所谓“边染色”（或称“线段染色”），

2、主要借助抽屉原则求解.（2）点染色.先看离散的有限个点的情况.例题讲解 1 把正方形 ABCD 的一边 AB 分成 n 段，使奇数号的线段长度之和等于偶数号的线段长度之和（如图 0101）。过各分点作平行于 AD 的线段，得到 n 个矩形。每一个矩形又被对角线 BD分成两部分。将奇数号矩形左部及偶数号矩形的右部涂上同一颜色。证明：在对角线 BD 两侧的有同色的部分，其面积和相等。2在一张无限方格纸的某些方格上涂上红色，其余方格涂上蓝色，每一个 23的六方格矩形内恰好 2 个红方格。试问：一个 911 的 99 方格矩形内包含多少个红方格？3在 nn（n2）个方格的正方形表中，有 n1 个格子里

3、涂了色，求证：通过交换-2-两行或两列的位置，总可以将所有涂色的方格移到正方形表的左上角顶点到右下角顶点的对角线下方。4有 nn（n3）个方格表中，先在表中任意选出 n1 个方格都涂成黑色，然后将那些凡是至少与两个已涂色的方格相邻的方格也都涂黑色。求证：不论怎样选择最初的 n1 个方格，都不能按这样的法则，将表中的所有方格全涂黑。5设 ABC 为正三角形，E 为线段 BC，CA，AB 上点的集合（包括 A，B，C 在内）。将 E 分成两个子集，求证：总有一个子集中含有一个直角三角形的顶点。6设 a1，a2，a3是一个不减的正整数序列，定义 bm是使 anm 的 n 的最小值，若 a19=85，

4、试求 a1+a2+a19+b1+b2+b85的值。7有 1987 块玻璃片，每块上涂有红、黄、蓝三色之一，进行下列操作：将不同颜色的两块玻璃片擦净，然后涂上第三种颜色。（1）求证：无论开始时红、黄、蓝色玻璃片各有多少块，总可以经过有限次操作而使所有的玻璃片涂有同一种颜色；（2）求证：玻璃片最后变成哪种颜色，与操作顺序无关。8把集合 M=1，2，1987的元素用 4 种颜色涂色，求证：至少存在一种涂色方法，使得M 中任何等差数列的 10 项，不是同一颜色。-3-9平面直角坐标系中，纵横坐标都是整数的点称为整点称为整点。设计一种方法，将所有整点涂色，每一个整点染成白色、红色或黑色中的一种颜色，使得

5、 （1）每一种颜色的点出现在无穷多条平行于横轴的直线上；（2）对任意白点 A、红点 B 及黑点 C，总可以找到一个红点 D，使得 ABCD 为一平行四边形。证明你设计的的方法符合上述要求。10将平面上每个点染上两种颜色中的一种，已知任一边长为 1 的正三角形都有两种颜色的顶点，（1）求证：存在边长为3的同色正三形（即顶点同色）；（2）举出染色满足题设要求的平面的例子。11平面上有 6 点，任何三点都是一个不等边三角形的顶点，求证：这些三角形的边中一定有一条，它在一个三角形中是最长边，而在另一个三角形中是最短边。12平面上任一点都染上红、蓝、黄三色中的一种，求证：一定存在一条端点同色且长度为 1

6、的线段。梦想不会辜负每一个努力的人.-4-例题答案：1.证明：设矩形中涂的是红色，不涂的为白色，则 正方形左白右红右白左红SSSSS21 另外，正方形左白左红SSS21 右白右红左白左红SSSS 右红左红SS 2.答案：33 个红方格。分析：如图 0102，取任一个红格 K0为中心的 33 正方形。不能在K处涂红色。因为，如果在K处涂红色，在 23 的矩形：AFHD、ABST、MNCD 中均有两个红方格。为了使矩形BCGE 内含有两个红方格，不论红方格放在任何一处，都将使上述的三个矩形的一个出现三个红方格。这就说，红方格不能与 K0有公共的边，只能是在其对角线上。从总体上来说，只能，如图 01

7、03。因此，每一个 33 的正方形中有且只有 3 个红方格。又在 911 矩形中，可分为九个 33 的正方形及三个 23 的矩形，故一共有 9332=33 个红方格。3.由于涂色的格子总共有 n1 个，所以 n 列中至少有一列的格子未涂色，经过调整，可以使最下面的一行中涂色格 子都在对角线下方（如图 0104）。再考察除去最右一列与最下一行的（n1）（n1）个方格，继续上面的过程，必可将 n1 个涂色的格子移到所设的对角线下方。4.证明：设每个小方格的边长为 1，考察黑方格区域的边界长度 L。开始时，由于只有 n1 个方格，L4（n1）。在以后的涂色过程中，尽管黑方格的总体面积增加了，但其周长

8、不变，即仍有 L4（n1）。如果要填满 nn 的方格，就有 L=4n，显然发生矛盾。命题得证。5.证明：将 E 中的点染成红、蓝二色，即证明必存在一个直角三角形，它们的顶点同色。在三边上取三等分点 P，Q，R，如图 0105。易知 RQBC，QPAC，PRAB。这三点必至少有两点同色。不妨设 R，Q 为红色。（1）如果 BC 边上除 Q 点外还有红色的点 X，则 RtRQX 三个顶点同为红色。（2）如果 BC 边上除 Q 外不存在红色点，梦想不会辜负每一个努力的人.-5-则 B 点是蓝色的。如果 AB 上除 B 外还有蓝色点 Y，作 YMBC，M 为垂足，显然 M 不同于 Q。所以 RtYBM

9、 三个顶点均为蓝色；如果 AB 上除 B 点外均为红色。作 QZAB，Z 为垂足，则 RtRQZ 的三个顶点均为红色。证毕。6.解：如图 0106，第 i 行（1i19）中的 ai个方格涂黑（例如，a2=3，则涂 3 格），在第 j 列（1j85）中白方格数，是小于 ai的个数（例如，a3=5），在第 5 列上方有两个白格子，就是 a15，a25，b5-1=2。因此，所有的格子（黑的和白的）的个数就是 a1+a2+a19+（b11）+（b21）+（b851）=1985，a1+a2+a19+b1+b2+b85=1985+85=2085=1700。注：从这几个例子可以看出，既可作为手段，转化问题的

10、形式，便于叙述，也有本来就是涂色的形式，要调整、构造新形式。思考起来很灵活。设等差数列首项为 k，公差为 d，则91987,19781kdk，其中x表示 x 的整数部分，941111197814222921978)91986(991985198691987kka 9.解：将 y 轴上的整点染上黑色或白色，并且黑、白各有无穷多个（例如黑、白相间）。再将梦想不会辜负每一个努力的人.-6-其余整点都染上红色，则这样的染色满足题设要求。证明：不难看出到上述设计，白色点、黑色点、红色点出现在无穷多条平行于横轴的直线上，故满足条件（1）。设 A 为白点，B 为红点，C 为黑点，显然 B 不在 y 轴上，即

11、 B 不在 AC 上，而且ABCD 顶点 D 的横（纵）坐标，所以 D 一定是整点。由于 A，C 横坐标为 0，B 横坐标不为 0，所以 D的横坐标不为 0，即 D 为红点。满足条件（2）。注：例 8 要用到重复排列的问题解法，还要进行计算，放缩。例 9 则是设计一种方案，证明它符合要求。数学竞赛中，常见的是与拉姆赛数有关的问题。无三点共线的 n 个点中，任两点都连成线段，所得的图称为完全图，记为 Kn.如果设 R（k）表示用 k 种颜色涂 Kn 中所有边时，总能找到同色三形的点数 n 的最小数，则称 R（k）拉姆赛数。10.证明：（1）取长为 2 的线段 AB，且两端点不同色，又设 AB 的中点 C 与 A 同色。作正AEC 和ADC（如图 0108），由题设，D，E 不能与 A，C 同色。于是BDE 是边长为3的正三形，其顶点同色。（2）将平面分成宽度为23的水平带状区域，每个区域含它下面的一条直线（边界），不含它上面的一条直线。让相邻的带状区域染上不同颜色即可。