组合数学问题选讲

1、组合问题选讲例1 将正方形ABCD分割成n2个相等的小方格（n是正整数），把相对的顶点A，C染成红色，B，D染成蓝色，其他交点任意染成红蓝两色中的一种颜色。证明：恰有三个顶点同颜色的小方格的数目必是偶数。（1991，初中联赛）。证 用数代表颜色点，将红色点记为0，蓝色点记为1，再将n2个小方格编号为。设第i个小方格四个顶点数字和记为Ai，恰有三个顶点同色的第i个小方格，则Ai=1或3，即为奇数，否则为偶数。在中，有如下事实：正方形内部的点各加了四次，正方形四边上的点各加两次，四个顶点各加1次，其中两个1，两个0，其和为2。因此，=4×（内部点相应数之和） +2×（四边上点相

2、应数之和）+2即必为偶数。故中奇数的个数为偶数，从而证明了恰有三个顶点有相同颜色的小方格的个数为偶数个。（恰有三个顶点有相同颜色的小方格的顶点颜色和必为奇数）例2 设。且G具有下列性质：（1）对任何，（2）。试证：G中的奇数的个数是4的倍数，且G中所有数的平方和是一定数。（1990，高中联赛）证 对，记，令，（）则G中包含且只包含中的一个元素。设G中有个奇数，于是令，由题（2）得， 另一方面，得， 故k必为偶数，令k=2m，则可化为因为k是偶数，故右端为偶数，从而m是偶数，所以k是4的倍数。G中各数的平方和为： = =1349380即G中各数平方和为一定数。例3一个国际社团的成员来自六个国家共

3、1978人，用1，2， 1977，1978来编号，试证明：该社团至少有一个成员的编号或与他的两个同胞的编号之和相等或者是其中一个同胞编号的两倍。证明：可用反证法来证明与本题完全相当的下列问题：把数列1，2，1977，1978 按任意一方式分成六组，则至少有一组具有这样的性质，其中必有一个数或等于同组的其他两个数的和或者等于其中某一个数的两倍。假设这六组数中的每一组数都不具备上述性质，也就是说每一组数都具备下列性质（记作性质）：同组中任意两个数的差必不在该组中。因为如果 连同 都在一组，那么 与假设矛盾。因 所以由抽屉原则可以肯定有一组其中至少有330 个数（不妨记为）现在在 中任取330个数来

4、，记其中最大的为 把分别减去其余的329个数得到329个数，它们互不相等且大于0而小于1978。由性质（）知这329个数不能在中，即应该属于另外五组中，又 所以其余5组中必有一组至少含有上述329个数中的66个数（不妨记为），从中取出上述329个数中的任66个，其中最大的一个记为 再把减去其余的65个数得出65个数任然大于0而小于1978显然 这65个数不属于 ，当然也不属于假如其中的某个数属于 即 ，由于 分别可写为， 其中 都属于 于是 。 这同 具备性质（）矛盾。这就说明上述65个数必属于另外 四个数组中。由于 所以至少有一组其中含上述65个数中17个数（记为）类似上述过程，最后可得一数

5、组，其中至少有两个数，大数与小数的差是大于0而小于1978的整数，可是它不在的任一组中，这显然是一个矛盾的结果。从而说明假设不对，也就是这六组数至少有一组具备性质（）。即题目结论正确。例 4。在直角坐标系中，格上点的坐标 满足 ，将这144个点分别用染成红，蓝，白三色。证明：存在一个矩形，它的边平行坐标轴，它的顶点具有相同的颜色。证明： 因为 ，则由抽屉原则，则在直线 （） 至少有6个点是同一颜色。不妨设在 ， 上有6个红点是： 考虑如下48个点 ，（ ）如果在某条直线 （）上有两个红点，则结论成立。否则，上述48个点中至多有8个红点，从而至少有40个点是蓝点和白点，由抽屉原理，则至少有20个

6、点是同颜色点，不妨设其中蓝点个数不少于20个，由于这些点分布在直线 上，因，因此至少有一条直线上至少有4个蓝点（设为 ）不妨设为。下面来考虑这样的20个点：，其中 。如果在直线 （）上有两个蓝点，则结论成立。若不然，上述20个点中至多有5个蓝点，又由前知最多只有4个红点，从而至少有11个白点，这些白点分布在5条直线 上，所以至少有一条直线其上至少有3个白点（不妨设为 ）再来考虑这样的12个点：其中 ， 。因为其中至多3个红点，至多4个蓝点，从而至少有5个白点，这5个白点分布在4条直线 上，从而至少有一条线上有两个白点，则这两个白点与 上3个白点中对映的两个白点构成一个符合要求的白顶点矩形。即结

7、论得证。例 5。 求最小正整数 ，使得平面内任意无3点共线的个点中，必有3点是一个非等腰三角形。解: 首先若平面内6点是一个正五边形的5个顶点和它的中心时，以这6点为顶点的所有三角形都是等腰三角形，故所求正整数 。其次，若存在平面7点（其中任意3点不共线），使以这7点为顶点的所有三角形都是等腰三角形。记这7点的集合为 。不妨设 中距离最大的两点为。分别以 为中心，为半径画弧相交于 两点。记， 线段。任取 ，,由于 为等腰三角形，于是下列三种情况至少有一个成立：1，；2，；3，。 所以 。因中无三点共线，故 上至多有中两个点，于是弧（不含端点）内至少有中个点。不妨设弧上有中一点，且在弧内无中的点

8、。再分别以为中心，以为半径作圆弧交于两点。记，线段，同理中的点全部属于。所以，且弧内无中的点。所以，其中是，是，是。记，则上至少有中不同于的3个点。所以或上至少有中不同于的两个点。不妨设中有不同于的两个点在上，则只有下列两种情形：（1）。因为为等腰三角形，且，所以 。同理由是等腰三角形，得。所以，即在的中垂线上，但的中垂线只通过而不通过，矛盾。（2），同一可得。又为等腰三角形，且，所以，所以。在与中，。所以，这与矛盾。可见平面内不存在7点（其中任意三点不共线），使以这7点为顶点的所有三角形都是等腰三角形。综上所知，所求最小正整数。例6。设 为实数，满足 。求证：对每一个整数 ，存在不全为零的整

9、数 使得 且证明：由柯西不等式即 所以 当 时有把区间 等分为 个小区间，每个小区间的长度为 。由于每个 能取 个数，因此 共有 个数。由抽屉原则知，必有两个不同的数会落在同一个小区间内。设它们分别为 与 因此有 很显然， 现在取 于是可得 且 适合 。结论成立。组合计数是非常重要的内容，基本思想是利用排列组合，但在处理实际问题时存在很强的技巧。通常有列举法；配对法；递推法；母函数法等。例7数学奥林匹克评委会由9人组成，有关试题藏在一个保险箱中，要求至少有六名评委在场时才能打开保险箱。问保险箱上应安上多少把锁，配多少把钥匙，怎样分发给评委？解：显然，我们应考虑在保险箱上尽可能少安锁。设保险箱上

10、按锁的集合为，9名评委中所有5人小组的集合为。则。一个5人小组，必有唯一的一把锁，使5人小组中没有人能打开锁。建立集合到集合的映射：设，令。设是另一个5人小组，他们打不开的所必和不同。因为如果和是同一把锁，则两个5人小组与都在场时，锁和还是打不开，这与题中条件矛盾。所以是单射。对于每一把锁，必有5人小组，他们不能打开锁，即。因此是满射。所以由配对原理知。即应安126把锁。另外，对于每把锁，必有5人小组他们不能打开锁，但之外的人都能打开。因此，每把锁应配4把钥匙，分发给5人小组之外的4个人。于是应配1264=504把钥匙，并把每把锁的4把钥匙分发给不同的4人小组的每个人，使不同的4人小组对应不同

11、的锁。组合几何及其应用组合几何诞生于20世纪中叶，是用组合数学的成果来解决几何学中的问题，主要研究几何图形的拓扑性质和有限制条件的欧几里得性质。组合几何以内容丰富，题目新颖，难度有层次而在数学竞赛中异军突起。组合几何问题，常常需要创造“新招”，它需要知识，更需要智慧。一 凸图形与凸包平面图形是平面上点的集合，就其性态而言，可分为离散点集与连续点集。比如一个有限点组就是离散点集；而一条曲线则是连续点集。一条封闭曲线包围的平面部分叫平面区域，其中封闭曲线叫区域的边界；包含边界在内的区域叫闭区域。此外我们还可以将平面图形分为凸图形与非凸图形来进行研究。定义1：如果对于平面图形中任意两点 线段上每一点

12、均属于，则称图形为凸图形。容易验证：线段，直线，射线，半平面，角域，圆域，全平面等都是凸图形，以平面凸多边形为边界的区域也是凸图形。凸图形有下面的重要性质：定理1。 两个凸图形的交仍然是凸图形。定理2。任意个凸图形的交仍然是凸图形。定理3：有限点组的凸包存在而且唯一例8设为平面上的两个有限点集，无公共元素，并且中任意三点都不共线，如果中至少有一个的点数不少于5。证明：存在一个三角形，它的顶点全在中或全在中，它的内部不含另一个集合中的点。 证明：设只含五个点。由于中任三点不共线，所以 中任三点不共线，的凸包为凸多边形。（1） 如果为凸五边形，考虑，如果其中有一个不含中的点，则这三角形即位所求；如果它们分别含有中的点显然不共线，则即为所求。（2）