文档介绍：该【18高三复习组合基础知识与测试 】是由【江湖故人】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【18高三复习组合基础知识与测试 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。尤新教育辅导学校
第十八章组合
一、方法与例题
。
例1设整数n≥4,a,a,…,a是区间(0,2n)内n个不同的整数,证明:存在集合
12n
{a,a,…,a}的一个子集,它的所有元素之和能被2n整除。
12n
[证明](1)若n{a,a,…,a},则n个不同的数属于n-1个集合{1,2n-1},
12n
{2,2n-2},…,{n-1,n+1}。由抽屉原理知其中必存在两个数a,a(i≠j)属于同一集合,从
ij
而a+a=2n被2n整除;
ij
(2)若n∈{a,a,…,a},不妨设a=n,从a,a,…,a(n-1≥3)中任意取3个数a,a,
12nn12n-1ij
a(a,<a<a),则a-a与a-a中至少有一个不被n整除,否则a-a=(a-a)+(a-a)≥2n,这与
kijkjikikikjji
a∈(0,2n)矛盾,故a,a,…,a中必有两个数之差不被n整除;不妨设a与a之差(a-a>0)
k12n-11221
不被n整除,考虑n个数a,a,a+a,a+a+a,…,a+a+…+a。
121212312n-1
ⅰ)若这n个数中有一个被n整除,设此数等于k,若k为偶数,则结论成立;若k为奇
n
数,则加上a=n知结论成立。
n
ⅱ)若这n个数中没有一个被n整除,则它们除以n的余数只能取1,2,…,n-1这n-1个值,
由抽屉原理知其中必有两个数除以n的余数相同,它们之差被n整除,而a-a不被n整除,
21
故这个差必为a,a,a中若干个数之和,同ⅰ)可知结论成立。
ijk-1
。
例2在n×n的方格表的每个小方格内写有一个非负整数,并且在某一行和某一列的交叉
点处如果写有0,那么该行与该列所填的所有数之和不小于n。证明:表中所有数之和不小
1
于n2。
2
[证明]计算各行的和、各列的和,这2n个和中必有最小的,不妨设第m行的和最小,记
和为k,则该行中至少有n-k个0,这n-k个0所在的各列的和都不小于n-k,从而这n-k
列的数的总和不小于(n-k)2,其余各列的数的总和不小于k2,从而表中所有数的总和不小于
(nkk)21
(n-k)2+k2≥n2.
22
。
俗话说,变化的是现象,不变的是本质,某一事情反复地进行,寻找不变量是一种策略。
例3设正整数n是奇数,在黑板上写下数1,2,…,2n,然后取其中任意两个数a,b,擦
去这两个数,并写上|a-b|。证明:最后留下的是一个奇数。
[证明]设S是黑板上所有数的和,开始时和数是S=1+2+…+2n=n(2n+1),这是一个奇数,
因为|a-b|与a+b有相同的奇偶性,故整个变化过程中S的奇偶性不变,故最后结果为奇数。
例4数a,a,…,a中每一个是1或-1,并且有S=aaaa+aaaa+…+aaaa=:
12n12342345n123
4|n.
[证明]如果把a,a,…,a中任意一个a换成-a,因为有4个循环相邻的项都改变符号,S
12nii
模4并不改变,开始时S=0,即S≡0,即S≡0(mod4)。经有限次变号可将每个a都变成1,
i
而始终有S≡0(mod4),从而有n≡0(mod4),所以4|n。
。
尤新教育辅导学校
例5是否存在一个无穷正整数数列a,<a<a<…,使得对任意整数A,数列{aA}中
123nn1
仅有有限个素数。
[证明]存在。取a=(n!)3即可。当A=0时,{a}中没有素数;当|A|≥2时,若n≥|A|,
nn
则a+A均为|A|的倍数且大于|A|,不可能为素数;当A=±1时,a±1=(n!±1)•[(n!)2±
nn
n!+1],当≥3时均为合数。从而当A为整数时,{(n!)3+A}中只有有限个素数。
例6一个多面体共有偶数条棱,试证:可以在它的每条棱上标上一个箭头,使得对每个
顶点,指向它的箭头数目是偶数。
[证明]首先任意给每条棱一个箭头,如果此时对每个顶点,指向它的箭头数均为偶数,
则命题成立。若有某个顶点A,指向它的箭头数为奇数,则必存在另一个顶点B,指向它的
箭头数也为奇数(因为棱总数为偶数),对于顶点A与B,总有一条由棱组成的“路径”连
结它们,对该路径上的每条棱,改变它们箭头的方向,于是对于该路径上除A,B外的每个
顶点,指向它的箭头数的奇偶性不变,而对顶点A,B,指向它的箭头数变成了偶数。如果
这时仍有顶点,指向它的箭头数为奇数,那么重复上述做法,可以又减少两个这样的顶点,
由于多面体顶点数有限,经过有限次调整,总能使和是对每个顶点,指向它的箭头数为偶
数。命题成立。
。
例7能否在5×5方格表内找到一条线路,它由某格中心出发,经过每个方格恰好一次,
再回到出发点,并且途中不经过任何方格的顶点?
[解]不可能。将方格表黑白相间染色,不妨设黑格为13个,白格为12个,如果能实现,
因黑白格交替出现,黑白格数目应相等,得出矛盾,故不可能。
。
给定平面点集A,能盖住A的最小的凸图形,称为A的凸包。
例8试证:任何不自交的五边形都位于它的某条边的同一侧。
[证明]五边形的凸五包是凸五边形、凸四边形或者是三角形,凸包的顶点中至少有3点
是原五边形的顶点。五边形共有5个顶点,故3个顶点中必有两点是相邻顶点。连结这两
点的边即为所求。
。
例9由2×2的方格纸去掉一个方格余下的图形称为拐形,用这种拐形去覆盖5×7的方
格板,每个拐形恰覆盖3个方格,可以重叠但不能超出方格板的边界,问:能否使方格板
上每个方格被覆盖的层数都相同?说明理由。
[解]将5×7方格板的每一个小方格内填写数-2和1。如图18-1所示,每个拐形覆盖的
三个数之和为非负。因而无论用多少个拐形覆盖多少次,盖住的所有数字之和都是非负的。
另一方面,方格板上数字的总和为12×(-2)+23×1=-1,当被覆盖K层时,盖住的数字之
和等于-K,这表明不存在满足题中要求的覆盖。
-21-21-21-2
1111111
-21-21-21-2
1111111
-21-21-21-2
。
例10生产由六种颜色的纱线织成的双色布,在所生产的双色布中,每种颜色的纱线至少
与其他三种颜色的纱线搭配过。证明:可以挑出三种不同的双色布,它们包含所有的颜色。
尤新教育辅导学校