2020届高三数学毕业班课本知识点整理归纳之十八

2020年高三毕业班数学课本知识点整理归纳之十八
第十八章 组合
一、方法与例题
1．抽屉原理。
例1 设整数n≥4,a
1
, a
2
,…,a
n
是区间(0,2n)内n个不同的整数，证明：存在集合{a
1
,a
2
,…,a
n
}的一个子集，它的所有元素 之和能被2n整除。
[证明] （1）若n
?
{a
1
,a
2
,…,a
n
},则n个不同的数属于n-1个集合{1,2n-1}，
{ 2,2n-2},…,{n-1,n+1}。由抽屉原理知其中必存在两个数a
i
,a
j
(i≠j)属于同一集合，从
而a
i
+a
j
=2n被2n 整除；
（2）若n∈{a
1
,a
2
,…,a
n
} ，不妨设a
n
=n，从a
1
,a
2
,…,a
n-1
(n-1≥3)中任意取3个数a
i
, a
j
,
a
k
(a
i
,j
< a
k
) ，则a
j
-a
i
与a
k
-a
i
中至少有一 个不被n整除，否则a
k
-a
i
=(a
k
-a
j< br>)+(a
j
-a
i
)≥2n，
这与a
k
∈( 0,2n)矛盾，故a
1
,a
2
,…,a
n-1
中必有两个 数之差不被n整除；不妨设a
1
与a
2
之差
(a
2
-a
1
>0)不被n整除，考虑n个数a
1
,a
2
,a1
+a
2
,a
1
+a
2
+a
3
,…,a
1
+a
2
+…+a
n-1
。
ⅰ）若这 n个数中有一个被n整除，设此数等于k
n
，若k为偶数，则结论成立；若k为奇
数， 则加上a
n
=n知结论成立。
ⅱ）若这n个数中没有一个被n整除，则它们除以n的 余数只能取1,2,…,n-1这n-1个值，
由抽屉原理知其中必有两个数除以n的余数相同，它们之 差被n整除，而a
2
-a
1
不被n整除，
故这个差必为a
i
, a
j
, a
k-1
中若干个数之和，同ⅰ）可知结论成立。
2．极端原理。
例2 在n×n的方格表的每个小方格内写有一个非负整数，并且在某一行 和某一列的交叉
点处如果写有0，那么该行与该列所填的所有数之和不小于n。证明：表中所有数之和不 小
于
1
2
n
。
2
[证明] 计算各行的和、各 列的和，这2n个和中必有最小的，不妨设第m行的和最小，记
和为k，则该行中至少有n- k个0，这n-k个0所在的各列的和都不小于n-k，从而这n-k
22
列的数的总和不小于 (n-k)，其余各列的数的总和不小于k，从而表中所有数的总和不小
(n?k?k)
21
2
?n.
于(n-k)+k≥
22
22
3.不变量原理。
俗话说，变化的是现象，不变的是本质，某一事情反复地进行，寻找不变量是一种策略。
例3 设正整数n是奇数，在黑板上写下数1，2，…，2n，然后取其中任意两个数a,b,擦
去这两个数， 并写上|a-b|。证明：最后留下的是一个奇数。
[证明] 设S是黑板上所有数的和，开始时和 数是S=1+2+…+2n=n(2n+1)，这是一个奇数，
因为|a-b|与a+b有相同的奇偶性 ，故整个变化过程中S的奇偶性不变，故最后结果为奇数。
例4 数a
1
, a< br>2
,…,a
n
中每一个是1或-1，并且有S=a
1
a
2
a
3
a
4
+ a
2
a
3
a< br>4
a
5
+…+a
n
a
1
a
2
a
3
=0. 证明：
4|n.
[证明] 如果把a
1
, a
2
,…,a
n
中任意一个a
i< br>换成-a
i
，因为有4个循环相邻的项都改变符号，
S模4并不改变，开始时S =0，即S≡0，即S≡0(mod4)。经有限次变号可将每个a
i
都变成
1，而始 终有S≡0(mod4)，从而有n≡0(mod4)，所以4|n。
4．构造法。
?
例5 是否存在一个无穷正整数数列a
1
,2
3
<…，使得对任意整数A，数列
{a
n
?A}
n?1中

仅有有限个素数。
3
[证明] 存在。取a
n=(n!)即可。当A=0时，{a
n
}中没有素数；当|A|≥2时，若n≥|A|，< br>2
则a
n
+A均为|A|的倍数且大于|A|，不可能为素数；当A=±1时， a
n
±1=(n!±1)?[(n!)±
3
n!+1]，当≥3时均为合数。 从而当A为整数时，{(n!)+A}中只有有限个素数。
例6 一个多面体共有偶数条棱，试证： 可以在它的每条棱上标上一个箭头，使得对每个
顶点，指向它的箭头数目是偶数。
[证明] 首先任意给每条棱一个箭头，如果此时对每个顶点，指向它的箭头数均为偶数，
则命题成立。若有某个顶 点A，指向它的箭头数为奇数，则必存在另一个顶点B，指向它的
箭头数也为奇数（因为棱总数为偶数） ，对于顶点A与B，总有一条由棱组成的“路径”连
结它们，对该路径上的每条棱，改变它们箭头的方向 ，于是对于该路径上除A，B外的每个
顶点，指向它的箭头数的奇偶性不变，而对顶点A，B，指向它的 箭头数变成了偶数。如果
这时仍有顶点，指向它的箭头数为奇数，那么重复上述做法，又可以减少两个这 样的顶点，
由于多面体顶点数有限，经过有限次调整，总能使和是对每个顶点，指向它的箭头数为偶数。命题成立。
5．染色法。
例7 能否在5×5方格表内找到一条线路，它由某格 中心出发，经过每个方格恰好一次，
再回到出发点，并且途中不经过任何方格的顶点？
[解] 不可能。将方格表黑白相间染色，不妨设黑格为13个，白格为12个，如果能实现，
因黑白格交替出现 ，黑白格数目应相等，得出矛盾，故不可能。
6．凸包的使用。
给定平面点集A，能盖住A的最小的凸图形，称为A的凸包。
例8 试证：任何不自交的五边形都位于它的某条边的同一侧。
[证明] 五边形的凸五包是凸五边形、凸 四边形或者是三角形，凸包的顶点中至少有3点
是原五边形的顶点。五边形共有5个顶点，故3个顶点中 必有两点是相邻顶点。连结这两
点的边即为所求。
7．赋值方法。
例9 由2× 2的方格纸去掉一个方格余下的图形称为拐形，用这种拐形去覆盖5×7的方
格板，每个拐形恰覆盖3个 方格，可以重叠但不能超出方格板的边界，问：能否使方格板
上每个方格被覆盖的层数都相同？说明理由 。
[解] 将5×7方格板的每一个小方格内填写数-2和1。如图18-1所示，每个拐形覆盖的
三个数之和为非负。因而无论用多少个拐形覆盖多少次，盖住的所有数字之和都是非负的。
另一 方面，方格板上数字的总和为12×(-2)+23×1=-1，当被覆盖K层时，盖住的数字之
和等于 -K，这表明不存在满足题中要求的覆盖。
-2
1
-2
1
-2
1
1
1
1
1
-2
1
-2
1
-2
1
1
1
1
1
-2
1
-2
1
-2
1
1
1
1
1
-2
1
-2
1
-2

8．图论方法。
例10 生产由六种颜色的纱线织成的双色布，在所生产的双色布中，每种 颜色的纱线至少
与其他三种颜色的纱线搭配过。证明：可以挑出三种不同的双色布，它们包含所有的颜色 。
[证明] 用点A
1
，A
2
，A
3
，A4
，A
5
，A
6
表示六种颜色，若两种颜色的线搭配过，则在相 应的
两点之间连一条边。由已知，每个顶点至少连出三条边。命题等价于由这些边和点构成的