数学竞赛讲义
第一讲 组合计数
本讲概述
组合数学是竞赛中最重要的一个板块，也是变化最多，最灵活，难以掌握，至今还没有一个系统体系的学科.解决竞赛中的组合数学问题，往往不需要太多专门的知识，而是要求深刻的洞察能力和强大的化归、转化能力.所谓“得组合者得天下”，在联赛一二试乃至冬令营、集训队、IMO 中，最后的胜者往往是成功完成组合问题的同学.因此，学习组合数学对于竞赛获奖以及数学能力的培养都有着十分重要的意义.
从本讲开始，我们将用七讲来对组合数学做一个大致的勾勒.通过这七讲的学习，达到以下目的：1、掌握联赛一二试组合问题的特点与解法；2、对组合数学这门学科有一个初步的认识，为进一步学习打下基础；3、了解部分冬令营级别组合问题的难度与解题模式.
七讲内容分别为：一、组合计数（1） 比高考略难的基本计数问题 二、组合计数（2） 需要较多技巧的专门计数问题 三、组合恒等式 较为重要和有趣味的组合恒等式 四、抽屉原理与存在性问题 五、容斥原理与极端性原理
六、染色问题与操作问题 七、组合数学综合问题
本讲中，假定各位同学已经大致学完了高考难度的排列组合模块内容，对加法原理、乘法原理等有一定的理解并能完成相关的问题.
教师备注：本讲可与下一讲打通讲述，也可本讲专门讲常规的枚举、基本的组合问题，下一讲专门讲述一些较为高级的技巧.
首先给出一些相关的基本知识： 1、 加法原理与乘法原理
加法原理：完成一件事的方法可分成n 个互不相交的类，在第1类到第n 类分别有12,,...,n m m m 种方法，则总共完成这件事有
121
...n
i
n i m
m m m ==+++∑种方法.
应用加法原理的关键在于通过适当的分类，使得每一类都相对易于计数.
乘法原理：完成一件事的方法有n 个步骤，，在第1步到第n 步分别有12,,...,n m m m 种方法，则总共完成这件事有
1
21
...n
i
n i m m
m m ==∏种方法. 应用乘法原理的关键在于通过适当的分步，使得每一步
都相对易于计数.
由上可见，加法原理与乘法原理也是化归思想的应用，通过这两个原理以及它们的组合，可以将
一个复杂的组合计数问题分解成若干个便于计数的小问题.
2、 无重排列与组合
阶乘：定义 !(1)(2)...21n n n n =?-?-???，读作n 的阶乘
无重排列：从n 个不同元素中任取m 个不同元素排成一列，不同的排列种数称为排列数，记为m
n
A （部分书中记为m n P ），由乘法原理得到
!
(1)...(1)()!
m n n A n n n m n m =
=?-???-+-
无重组合：从n 个不同元素中任取m 个元素并为一组，不同的组合种数称为组合数，记为m
n C ，
其公式为
(1)...(1)!
!!()!!m
m
n n
A n n n m n C m m n m m ?-???-+===
- 3、 可重排列与组合（仅给出结论，请自证之）
可重排列：从n 个不同元素中可重复地任取m 个元素排成一列，不同的排列种数有m
n 种； 有限个重复元素的全排列：设n 个元素由k 个不同元素12,,...,k a a a 组成，分别有12,,...,k n n n 个（12...k n n n n +++=），那么这n 个元素的全排列数为
12!
!!...!
k n n n n ???
可重组合：从n 个不同元素中，任意可重复地选取m 个元素，称为n 个不同元素中取m 个元素的
可重组合，其种数为1m
n m C +-
4、 圆排列（仅给出结论，请自证之）
在n 个不同元素中，每次取出m 个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）．圆排列有三个特点：（i ）无头无尾；（ii ）按照同一方向转换后仍是同一排列；（iii ）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列．
在},,,,{321n a a a a A =的n 个元素中，每次取出m 个不同的元素进行圆排列，圆排列数为m
n A m
．
例题精讲
板块一 利用加法、乘法原理以及枚举方法计数
联赛一试的填空题中出现的计数问题有接近一半的问题不需要用到很高深的技巧，而是直接利用
最基本的加法、乘法原理，以及枚举方法来计数.这主要是考虑到有一部分参加联赛的同学并未经过专业的竞赛训练.虽然如此，这部分计数问题枚举起来往往分类复杂，需要小心仔细.
从往年的联赛试题来看，枚举法解决计数问题是最主要的题型之一，其难点在于做到“不重不漏”，这是加法原理的一个简单的应用.枚举过程中，采用恰当的分类、分步形式，往往会收到化难为易的效果.
【例1】 (高考难度的热身问题)
（1）等腰三角形的三边均为正整数．它们周长不大于10．这样不同的三角形的种数为
A ．8
B ．9
C ．10
D ．1l
（2）有两排座位，前排11个座位，后排12个座位，现安排2人就座，规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是 A.234 B ．346 C. 350 D ．363 【解析】 （1）设三边为x,y ，z ，则x+y+z ≤10，由三边关系共有(1，1，1)，(1，2，2)，(1，3，3)，(1，4，
4)，(2，2，2)，(2，2，3)，(2，3，3)，(2，4，4)，(3，3，3)，(3，3，4)共10种．
（2）B 前排中间的3个座位不能坐，有排法2
20
A ，其中相邻的分三类，在前排的其中的4个座位有3
2
2
A ；则符
合条件的排法种数中2
2
22
22
220
1133A A A A ---=346，故选B （这是正难则反的思想，从总体中除去不符合要求
的）
另解：分三类：①两人坐在前排，按要求有4·6+4·5=44种坐法．
②两人坐在后排，按要求有：
2
11
A =110种坐法．③两人分别坐在前后排，有8×12×2=192种
∴共有346种排法．
【例2】 （1）有多少个能被3整除而又含有数字6的五位数？
（2）集合{1,2,...,100}的子集中共有多少个至少包含一个奇数？
【解析】 （1）按照上题正难则反的思想，可以先找出所有的五位数，共有90000个，其中可被3整除
的有30000个，下面研究这30000个数中不含数字6的数，最高位有8种选择，千、百、十位各有9种选择，个位数除不能为6外，还应满足恰各位数之和可被3整除，这恰有3种选择，例如当前四位除以3余2时，个位应为1,4,7之一；故能被3整除且不含数字6的有8999317496????=个，故所求五位数有30000-17496=12504个
（2）显然全部子集数为100
2
个，不包含任何奇数的子集即{2,4,6,...,98,100}的子集共有502
个，故所求子集个数为100
50
22-个.(思考：请用最简洁的方法确定为何n 元集合子集数为2
n
个)
【例3】 设ABCDEF 为正六边形，一只青蛙开始在顶点A 处，它每次可随意地跳到相邻两顶点之一．若
在5次之内跳到D 点，则停止跳动；若5次之内不能到达D 点，则跳完5次也停止跳动，那么这只青蛙从开始到停止，可能出现的不同跳法共 种
【解析】 这是标准的联赛风格的枚举问题，所谓杀鸡焉用牛刀，用递归方法来解这类问题就太麻烦了.
显然青蛙不能跳1，2,4次到达D 点，于是青蛙的跳法只有以下两种： （1）青蛙跳3次后到达D 点，有2种跳法； （2）青蛙跳5次后停止，跳3次有3
22-种，后两次有2
2种，共计24种； 所以，合计有26种跳法
注 本题为1997年联赛试题
【例4】 从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，
每两个具有公共棱的面染成不同的颜色。则不同的染色方法共有 __________ 种。（注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、下、左、右、前、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相同。）
【解析】 因为有公共顶点的三个面互不同色，故至少要用3种颜色，下面分四种情形来考虑.
（1）6种颜色都用时，现将染某种固定颜色的面朝上，从剩下5种颜色中取一种颜色染下底面有
1
5
C 种方法，余下4种颜色染四个侧面（应是4种颜色的圆排列）有3！种方法.所以不同的染色方案有30!315=?C 种.
（2）只用5种颜色时，从6种颜色中取5种颜色有5
6C 种方法，这时必有一组对面同色.从5种颜色中取一种颜色染一组对面，并将它们朝上和朝下，有15C 种方法，其余4种颜色染四个侧面（应是4
种不同颜色的链排列）有
?213！种方法.所以不同的染色方案有5
6C 90!32
115=???C 种. （3）只用4种颜色时，从6种颜色中取4种颜色有4
6C 种方法，这时必有两组对面同色，另一组对面不同色，将不同色的一组对面朝上和朝下，并从4种颜色中取两种颜色染上、下底面，有24C 种方
法，其余两种颜色染四个侧面且使两组对面同色（应是两种不同颜色的链排列），只有1种方法.所以
不同的染色方案有46C 90124=??C 种.
（4）只用3种颜色时，从6种颜色中取3种颜色有3
6C 种方法，这时三组对面都同色，用三种颜色去染它们只有1种方法.所以不同的染色方案有3
6
C 201=?种. 综上可知，不同的染色方案共有30＋90＋90＋20＝230种.
注 本题为1996年联赛试题，是历年来一试计数问题中最复杂的一道，其背景与波利亚群论计数原理有关，这远远超出了高中范围，此处略去
【例5】 将24个志愿者名额分配给3个学校，则每校至少有一个名额且各校名额互不相同的分配方法
共有 222 种．
【解析】 用4条棍子间的空隙代表3个学校，而用*表示名额．如
||||******** 表示第一、二、三个学校分别有4，18，2个名额．
若把每个“*”与每个“|”都视为一个位置，由于左右两端必须是“｜”，故不同的分配方法相当于
24226+=个位置（两端不在内）被2个“｜”占领的一种“占位法”．
“每校至少有一个名额的分法”相当于在24个“*”之间的23个空隙中选出2个空隙插入“｜”，故
有223C 253
=种． 又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有31种． 综上知，满足条件的分配方法共有253－31＝222种．
[解法二] 设分配给3个学校的名额数分别为123,,x x x ，则每校至少有一个名额的分法数为不定方程 12324x x x ++=．
的正整数解的个数，即方程12321x x x ++=的非负整数解的个数，它等于3个不同元素中取21个元素的可重组合：
212123
23
23
H C C 253===．
又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有31种． 综上知，满足条件的分配方法共有253－31＝222种
注 本题为2008年联赛试题，从近年来联赛一试组合问题来看，组合计数问题难度明显降低了.本题所应用的插空法是一种在高考和竞赛中常用的计数方法
【例6】 将2个a 和2个b 共4个字母填在44?方格表内，每个小方格内至多填1个字母，若使相同
字母既不同行也不同列，则不同的填法共有________种（用数字作答）。
【解析】 使2个a 既不同行也不同列的填法有C 42A 42=72种，同样，使2个b 既不同行也不同列的填
法也有C 42A 42=72种，故由乘法原理，这样的填法共有722种，其中不符合要求的有两种情况：2个a 所在的方格内都填有b 的情况有72种；2个a 所在的方格内仅有1个方格内填有b 的情况有C 161A 92=16×72种。所以，符合题设条件的填法共有722?72?16×72=3960种。
注 本题为2007年联赛第12题
【例7】 设三位数n abc =，若以a ，b ，c 为三条边的长可以构成一个等腰（含等边）三角形，则这
样的三位数n 有（ ） A. 45个 B. 81个 C. 165个 D. 216个 【解析】 本题是标准的枚举问题，情况繁多. a ，b ，c 要能构成三角形的边长，显然均不为0。即,,{1,2,...,9}a b c ∈
（1）若构成等边三角形，设这样的三位数的个数为1n ，由于三位数中三个数码都相同，所以，
1
19
9n C ==。
（2）若构成等腰（非等边）三角形，设这样的三位数的个数为2n ，由于三位数中只有2个不同数码。
设为a 、b ，注意到三角形腰与底可以置换，所以可取的数码组（a ，b ）共有2
92C 。但当大数为底时，
设a>b
2b a b <<
共20种情况。
同时，每个数码组（a ，b ）中的二个数码填上三个数位，有2
3C 种情况。 故2222399(220)6(10)156n C C C =-=-=。 综上，12165n n n =+=。
注 本题为2004年联赛试题
板块二 映射与对应方法
由一一映射的定义可知，若存在从集合M 到N 的一一映射，则M N =.于是在难以直接计算集合M 中元素个数时，我们可以设法构造这样一个映射，将问题转化为计算较为容易计算的集合N 的元素个数.基于这种两集合元素一一对应的特点，也称为“配对法”
【例8】 （1）试用对应方法证明可重组合公式：从n 个不同元素中，任意可重复地选取m 个元素，
称为n 个不同元素中取m 个元素的可重组合，其种数为1m
n m C +-
（2）证明：不定方程12...k x x x n +++=（k,n 为正整数）的非负整数解组数为11k n k C -+-
【解析】 （1）设n 个元素为1,2,...,n ，并设取出的m 个元素为121...m a a a n ≤≤≤≤≤，于是
12101...11m a a a m n m ≤+<+<<+-≤+-，作对应
1212(,,...,)(0,1,...,1)m m a a a a a a m ?+++-，易证明它为一一对应
后者为从1n m +-个元素中取m 个元素的组合数1m
n m C +-，故得证
（2）将n 个圆圈与k-1个竖线排成一排，k-1个竖线将n 个圆圈依次分成k 个部分：12,,...,k x x x ，易见不同的排列对应不定方程不同的解，易证它为一个一一对应，而在n+k-1个元素中取出k-1个的
全排列数为11k n k C -+-，故得证.
【例9】 凸n 边形的任意3条对角线不相交于形内一点，求其对角线在形内的交点总个数. 【解析】 任一形内交点对应两条对角线l,m; 反之，任意两条对角线唯一确定形内一个交点P,从而P 与
（l,m ）构成一一对应；又任一对角线对应形内2顶点，n 边形中任取4顶点即可唯一确定两对角线，于是有如下一一对应：点(,)(,,,)P l m A B C D ??
于是交点总个数=四顶点组个数=4
n C
注 本题为组合数学一个重要分支——组合几何中的非常重要的一个结论，可以利用它解决一些高难度的组合几何计数问题
【例10】 将集合A 中的n 个元素排成一行，若某个子集中任意两元素不相邻，则称此子集为不好的，
试证明：k 元的不好的子集个数为1k
n k C -+
【解析】 设n 个元素排成一行依次为为1,2,...,n ，并设取出的k 个元素为121...k i i i n ≤<<<≤，
显然有12(1,2,...,1)j j i i j k +≤-=-； 作变换 12311 2...(1)1
k i i i i
k n k ≤<-<-<--≤-+，并取序列：
123(,1,2,...,(1))k i i i i k ----，它是1,2，n-k+1中的一个严格上升的序列 作对应12123(,,...,)(,1,2,...,(1))k k i i i i i i i k ?----，
易证明它为一一对应，且后者的种数为从1n k -+个元素中取k 个元素的组合数1k
n k C -+，故
得证
注 本题为第16届普特南竞赛题
大显身手
1． （1）在100件产品中有6件次品，现从中任取3件产品，至少有1件次品的不同取法的种数
是
A ．2
941
6C C B ．2
991
6C C C.394
3
100C C - D ．3943100A A -
（2）从4名男生和3名女生中选出4人参加某个座谈会，若这4人中必须既有男生又有女生，
则不同的选法共有
A.140种 B ．120种 C 35种 D ．34种
【解析】 （1） C 任取3件产品有3100C 种方法，其中无次品有394C 种方法，故至少有1件次品的方法数为.3
943100C C -
（2）D 既有女生又有男生，可以分类表示，三男一女有1334C C ?种选法，二男二女有2
424C C 种，
一男三女有3514C C ?种选法，则总的不同的选法有3
31423341334C C C C C C ?+?+?=34(种)
2． 由三个数字 1、2、3 组成的 5 位数中, 1、2、3 都至少出现 1 次, 这样的 5 位数共有多少个？
【解析】 在 5 位数中, 若 1 只出现 1 次，有 1123
5444()70C C C C ++= 个；
若 1 只出现 2 次，有 212
533()60C C C += 个；
若 1 只出现 3 次，有 315220C C = 个． 则这样的五位数共有 150 个． 故填 150个．
注 本题为05年江苏省预赛试题
3． 已知集合{}05≤-=a x x A ，{}
06>-=b x x B ,N b a ∈,，且{}2,3,4A B N ??=，则整数对()b a ,的个数为
A. 20
B. 25
C. 30
D. 42 【答】 （ ）
【解析】 由50x a -≤5a x ?≤；60x b ->6b x ?>。要使{}2,3,4A B N ??=，则126
45
5b a ?≤
，
即6122025
b a ≤
4． 记集合}6,5,4,3,2,1,0{=T ，?
??
??
?=∈+++=4,3,2,1,77774433221i T a a a a a M i ，将M 中的元素按从大到小顺序排列，则第2005个数是
A.
43273767575+++ B. 43272767575+++ C. 43274707171+++ D. 4327
3707171+++ 【解析】 用p k a a a ][21 表示k 位p 进制数，将集合M 中的每个数乘以4
7，得
32123412347{777|,1,2,3,4}{[]|,1,2,3,4}.i i M a a a a a T i a a a a a T i '=?+?+?+∈==∈=
M ' 中的最大数为107]2400[]6666[=。
在十进制数中，从2400起从大到小顺序排列的第2005个数是2400-2004=396; 而=10]396[7]1104[, 将此数除以4
7，便得到M 中的数：
.7
4
707171432+++故选C 。 注 本题为2005年联赛试题，题目形式提示我们，要采用进制转换.事实上，这类题目在小学和初中是
极为常见的.
5． 已知两个实数集合A ={a 1,a 2,…,a 100}与B ={b 1,b 2,…,b 50}，若从A 到B 的映射f 使得B 中每个元
素都有原象，且
f (a 1)≤f (a 2)≤…≤f (a 100) 则这样的映射共有
(A)50100C (B) 5099C (C) 49100C (D) 49
99C
【解析】 不妨设b 1
→B ，使得第i 组的元素在f 之下的象都是b i (i=1,2,…,50)，易知这样的f 满足题设要求，每个这样的分组都一一对应满足条件的映射，于是满足题设要求的映射f 的个数与A 按足码顺序
分为50组的分法数相等，而A 的分法数为4999C ，则这样的映射共有49
99C ，故选D 。
注 本题为2002年全国联赛试题
6． 在世界杯足球赛前，F 国教练为了考察A 1,A 2,…,A 7这七名，准备让他们在三场训练比赛(每场
90分钟)都上场，假设在比赛的任何时刻，这些中有且仅有一人在场上，并且A 1,A 2,A 3,A 4每人上场的总时间(以分钟为单位)均被13整除，如果每场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况。
【解析】 设第i 名队员上场的时间为x i 分钟(i=1,2,3,…,7)，问题即求不定方程
x 1+x 2+…+x 7=270 ①
在条件7|x i (1≤i ≤4)且13|x j (5≤j ≤7)下的正整数解的级数。 若(x 1,x 2,…,x 7)是满足条件①的一组正整数解，则应有
∑=4
1
i i
x
=7m
∑=7
5
j j
x
=13n m,n ∈N
∴m,n 是不定方程
7m+13n=270 ② 在条件m ≥4且n ≥3下的一组正整数解。 …………10分 ∵ 7(m-4)+13(n-3)=203
令 m ′=m -4 n ′=n -3 有
7m ′+13n ′=270 ③ ∴ 求②满足条件m ≥4且n ≥3的正整数解等价于求③的非负整数解。 ∵易观察到 7·2+13·(-1)=1
∴ 7·406+13·(-203)=203 即 m 0=406 n 0= -203是③的整数解 ∴ ③的整数通解为
m ′=406 -13k n ′= -203+7k k ∈Z
令 m ′≥0 n ′≥0,解得 29≤k ≤31 …………20分 取k=29,30,31得到③满足条件的三组非负整数解：
???='='029
n m
?
??='='716
n m ?
??='='143
n m 从而得到②满足条件的三组正整数解： ??
?==3
33
n m
??
?==10
20
n m ??
?==17
7
n m …………30分 1)在m=33,n=3时，显然x 5=x 6=x 7=13仅有一种可能， 又设x i =7y i (i=1,2,3,4)，于是由不定方程y 1+y 2+y 3+y 4=33有4960332
141
33==--C C 组正整数解。
∴此时①有满足条件的3
32C
=4960
组正整数解。
2)在m=20,n=10时，设x i =7y i (i=1,2,3,4)，x j =13y j (j=5,6,7)
由y 1+y 2+y 3+y 4=20，有319C 组正整数解；以及y 5+y 6+y 7=10，有2
9C 组正整数解。 ∴此时①有满足条件的29
319C C ?=34884组正整数解。 3) 在m=7,n=17时，设x i =7y i (i=1,2,3,4)，x j =13y j (j=5,6,7)
由y 1+y 2+y 3+y 4=7，有36C 组正整数解；以及y 5+y 6+y 7=17，有216C 组正整数解。…………40分
综上所述，①满足条件的正整数解的组数为
216
3639319332C C C C C ?+?+=4960+34884+2400=42244 …………50分 注 本题为2002年联赛二试最后一题，是一道不是很难的组合数论问题.问题求解过程中多次用到了我们的例8的结论.
(2)
本讲概述
组合计数的方法很多，除了上一讲的枚举、对应方法之外还包括：算两次、递推方法、容斥原理、利用恒等式、母函数方法等；容斥原理的方法将在第四讲讲述，递推方法我们在数列部分单独讲述.本讲主要讨论利用算两次方法计数的问题以及较为简单的递推方法（因为我们暂不具备完善的递推数列知识）；另外，本讲还将涉及到组合计数的二试与冬令营级别难度的少数问题.
首先给出本讲问题中要用到的知识（虽然这些知识可能暂时没有学到，但本讲只需会用即可）：
二项式定理：0
()n
n
k
n k
k
n
k x y C
x
y -=+=∑，特别地，0
(1)n
n
k k
n k x C x =+=∑，其中n N +∈ 特征方程与数列通项：
记一列数12,,...,,...n a a a 为数列{}n a ，如果它满足21,(1)n n n a pa qa n ++=+≥，那么称2x px q
=+为此数列的特征方程，（1）当有两互异实根时，数列通项为12
n n n a x x αβ=?+?； （2）当有二等根时，数列通项为1()n
n a n x αβ=+?
其中,αβ为根据初值确定的待定系数
例题精讲
板块一 算两次
算两次是一种非常重要的思想方法，在代数、组合、几何中都有涉及.组合问题中，组合极值、组合不等式也常常涉及到算两次.组合计数中，在直接计算非常复杂甚至无从入手时，我们常常利用算两次方法.顾名思义，算两次是指用不同的方法或者从不同的角度对同一个量进行计算，当两次都得到精确值时，我们就得到一个等式，当为估计式时，我们就得到一个不等式.事实上，数学中有相当大一部分定理就是利用算两次思想对原有的问题进行剖析，得到新的内在关系式.
【例11】 设12,,,n a a a …为1，2，…，n 的一个排列，k f 是集合{}
,i i k a a a i k <>元素的个数，而k
g 是集合{}
,i i k a a a i k ><元素的个数（1,2,,k n =…），证明
1
1
n n
k k
k k f g
===∑∑
【解析】 考虑集合{}
(,),i k i k S a a a a i k =<>的元素个数S 。一方面，固定k 先对i 求和，然后再对
k 求和，得1
n
k k S f ==∑；另一方面，固定i 先对k 求和，然后再对i 求和，又得到
1
1
n n i k i k S g g ====∑∑，所以得1
1
n n
k k k k f g ===∑∑。
注 本题只是为了说明算两次的基本思想和方法，这里的计数是抽象的，这种方法相当于考虑各个分量对总体的“贡献”，因此也有人把它叫做“贡献法”.请参考习题第一题
【例12】 有n 粒小球，任意将其分成两堆，求出两堆球数之积，再将其中一堆任意地分成两堆，求出
此两堆之积，如此下去，直至将小球分成n 堆（每个球1堆）为止.记此过程中所有的乘积之和为S ，求S 的所有可能值.
【解析】 以n=8为例，不论如何分，最后总得到2828S C ==，于是猜想对一般情形总有2
n S C =，即
n 粒小球中任取两个组成小球对的个数；另一方面，每将一些小球分成两堆，就将原来的一
些小球对（假设只有同一堆才能组成小球对）拆开，拆开的数目恰为两堆个数之积，最终的小球对个数为0，从而乘积之和即为最初的小球对个数，故得证.
注 本题构造了一种巧妙的对应，使原来无法下手的问题变得有章可循.事实上，组合问题，特别是算两次问题最关键的就是寻找算两次的对象，本题中就是对小球对进行算两次，使得问题清晰明了.
【例13】 一张正方形纸片内有1000个点，这些点及正方形的顶点中任意3点不共线.在这些点及正方
形的顶点间连一些线段将正方形全部分成小三角形（它们都以所连线段及正方形的边为边，且所连线段除端点外两两无公共点）.问一共连有多少条线段，一共得到多少个三角形？
【解析】 设一共连有l 条线段，得到k 个三角形.
首先对角度和进行计数： 一方面，所得k 个三角形的内角和为180k ?；另一方面，计算
1000个内点及4个正方形顶点处内角和为1000360490?+?，从而算得k=2002;
其次，对边数进行计数： k 个三角形共3k 条边，另一方面，每条线段是两个三角形的公共边，正方形的每条边被计算1次，共24l +条边，从而243l k +=，得到3001l =
注 本题的背景是计算机图形学中著名的三角面片分划问题，这类问题在冯康先生的有限元中也有应用.
从本题及习题2可以得到计算这类问题的一般方法，即对边、角乃至同色角、异色角等元素进行计数.
【例14】 （选讲）能否把1,1,2,2,3,3，…，1986,1986这些数排成一行，使得两个1之间夹着1个数，
两个2之间夹着2个数，两个1986之间夹着1986个数？
【解析】 设能将上述数字排成一行满足题设，这是每一个数(11986)i i ≤≤可赋予它一对有序实数
(,)i i x y 作为坐标，这里坐标值分别为它第一次与第二次出现的位置序号. 显然有关系：
1i i y x i =++.
现用两种方法计算全体数的坐标和：
一方面，直接从整体看，坐标和为
21986
1
1986(219861)k k ?==??+∑为偶数；
另一方面，就某一个i ，两坐标和为21i x i ++，从而所有坐标和为
198619861986
1
1
1
(21)21986i
i i i i x i x i ===++=++∑∑∑=偶数+9931987?为奇数. 此两者显然矛盾
注 本题为第二届冬令营的一道很难的问题,方法较多，上面给出的方法是一个很巧妙的解法，利用奇
偶性导出了矛盾，是命题人所没有想到的.
板块二 递推方法
当所计数对象按从1到n 有规律出现时，可视之为一个数列并考察其相邻项之间关系，得到递推
关系式,进而利用数列知识进行求解.一般来说，这类问题的关键在于如何得到递推关系式.对于竞赛选
手而言，由组合问题的递推关系式得到通项总是很简单的,因为组合问题的特性决定了递推关系式不会太过复杂.
由于我们没有详细讲述数列通项求法，所以这里只给出较为简单的问题.
注：建议教师主要讲述如何由题目条件得到递推式，至于递推式求解可以淡化或者让学生自行求解
【例15】 （Fibonacci 数列）假设一对兔子每隔一月生一对小兔，每对小兔两个月后也逐月生一对小
兔，如年初时放一对成年兔，那么一年以后兔房中有多少只兔子？
【解析】 用n a 表示第n 个月初的小兔对数，易得到1231,2,3,...a a a ===
一般地，第n 个月初的小兔分为两部分：第n-1个月的兔子数与第n 个月初出生的小兔对数，
即得到递推式12n n n a a a --=+，由特征方程的结论及初值，可得到13377a =
11
)n n n a ++=
-
注 关于斐波那契数列的进一步知识我们到数列部分再详细讲述
【例16】 用1,2,3来构造一个n 位数，但不允许数位中出现两个连续的1，问这样的数有多少个？ 【解析】 设有n a 个，显然123,8a a ==，讨论：
若n 位数第一位不是1，那么后面可以随便写，于是这样的有21n a -个， 若第一位是1，第二位写2或3，第三位后可以随便写，于是这样的有22n a -个， 得到递推式1222,3n n n a a a n --=+≥，由特征方程的结论及初值，化简得到
22(1)n n n a ++=
-
注 一般写出原始结果即可，或者把化简结果同时写出
板块三 组合计数综合问题
【例17】 设t s r ,,为整数，集合}0,222|{r s t a a t
s
r
<<≤++=中的数由小到大组成数列}{n a ：
,14,13,11,7，则=36a 131 。
【解析】 ∵t s r ,,为整数且r s t <<≤0，∴r 最小取2，此时符合条件的数有12
2=C
3=r ，t s ,可在2,1,0中取，符合条件有的数有323=C 同理，4=r 时，符合条件有的数有62
4=C
5=r 时，符合条件有的数有102
5=C 6=r 时，符合条件有的数有1526=C 7=r 时，符合条件有的数有2127=C
因此，36a 是7=r 中的最小值，即131********=++=a
注 本题为2005年四川预赛题，事实上此题源自2003年全国高考理科试卷压轴题，用二进制方法求解最为方便，可参考左晓明《2003年高考理科数学压轴题的一种巧妙解法及其推广》中学教研2003.12
【例18】 如果自然数a 的各位数字之和等于7，那么称a 为“吉祥数”.将所有“吉祥数”从小到大排
成一列,,,,321 a a a 若,2005=n a 则=n a 5__________ . 【解析】 准确理解“吉祥数”的定义是解题的前提，根据题意，可将此计数问题转化为考虑不定方程的非负整数解的个数.
∵方程m x x x k =+++ 21的非负整数解的个数为m
k m C 1-+.而使)2(0,11≥≥≥i x x i 的整数解的个数为12--+m k m C .现取7=m ，可知，k 位“吉祥数”的个数为.)(6
5+=k C k P
∵2005是形如
abc 2的数中最小的一个“吉祥数”，且
,7)2(,1)1(6766====C P C P ,28)3(6
8==C P
对于四位“吉祥数”abc 1，其个数为满足6=++c b a 的非负整数解个数，即286136=-+C 个.
∴2005是第1+7+28+28+1＝65个“吉祥数”，即.200565=a 从而.3255,65==n n
又,210)5(,84)4(6
1069====C P C P 而
∑==5
1
.330)(k k P
∵从大到小排列的最后六个五位“吉祥数”依次是：70000，61000,60100,60010,60001,52000. ∴第325个“吉祥数”是52000，即.520005=n a
注 1、本题为2005年全国联赛试题
2、很多计数问题都可以转化为求不定方程的解的组数，一般地，有
（1）不定方程m x x x n =+++ 21的非负整数解的组数为m
m n n m n C C 111-+--+=； （2）不定方程m x x x n =+++ 21的正整数解的组数为11--n m C .
【例19】 若四位数n abcd =的各位数码,,,a b c d 中，任三个数码皆可构成一个三角形的三条边长，则
称n 为四位三角形数，试求所有四位三角形数的个数．
【解析】 三个数构成三角形的三条边长的充要条件是任意两个数之和大于第三个数.本题需要根据四
个数码的各种可能情况分类进行分析，按照四个数码取值个数的不同进行分类比较容易入手一些.
称(,,,)a b c d 为n 的数码组，则,,,{1,2,,9}a b c d M ∈=.
（1）当数码组只含一个值，为(,,,),1,2,
,9a a a a a =，共得9个n 值.
（2）当数码组恰含二个值,a b （a b >）．
①数码组为(,,,)a a a b 型，则任取三个数码皆可构成三角形，对于每个{2,
,9}a ∈，b 可取
1a -个值，则数码组个数为9
2
(1)36a a =-=∑，对于每组(,,,)a a a b ，b 有4种占位方式，于是这种n 有
364144?=个．
②数码组为(,,,)a b b b 型（a b >），据构成三角形条件，有2b a b <<，
M 中a 的个数共得16个数码组，对于每组(,,,)a b b b ，a 有4种占位方式，于是这种n 有16464?=个．
③数码组为(,,,)a a b b 型（a b >），据构成三角形条件，有2b a b <<，同上得16个数码组，对
于每组(,,,)a a b b ，两个a 有2
46C =种占位方式，于是这种n 有16696?=个．
以上共计1446496304++=个．
（3）当数码组恰含三个值,,a b c ()a b c >>．
①数码组为(,,,)a b c c 型，据构成三角形条件，则有2c b a c <<<，这种(,,,)a b c c 有14组，每
组中,a b 有2
412A =种占位方式，于是这种n 有1412168?=个．
②数码组为(,,,)a b b c 型，c b a b c <<<+，此条件等价于{1,2,
,9}M =中取三个不同的数构
成三角形的方法数，有34组，每组中,a b 有2
412A =种占位方式，于是这种n 有3412408?=个．
③数码组为(,,,)a a b c 型，c b a b c <<<+，同情况②，有2
434408A =个n 值．
以上共计168408408984++=个n 值．
（4）,,,a b c d 互不相同，则有d c b a c d <<<<+，这种,,,a b c d 有16组，每组有4!种排法，共得164!384?=个n 值．
综上，全部四位三角形数n 的个数为93049843841681+++=个．
注 本题为2007年江西省预赛试题.本题的情况非常多，一定要注意分类的合理性和计数的准确性.
教师备注： 若例题不够可适当选择习题讲授
大显身手
7． 在一次测验中满分100分，所有同学得分都是非负整数，设n 位同学的的得分分别为
12,,...,n a a a ，其中得分至少为k 分的有k b 个（1100k ≤≤）
，记12...n M a a a =+++，12100...N b b b =+++，那么M,N 的大小关系为？
【解析】 M =N.一方面，得分为k 的同学对M 的贡献为k,另一方面他在12,,...,k b b b 中各被计算了一次，每次为1，共计为k ，于是得证.
注 本题为典型的算两次方法
8． 在一张正方形纸片的内部给出了1985个点，现用M 记这纸片的4个顶点与内部1985个点构
成的集合，并按下述规则将这张纸剪成一些三角形： （1） 每个三角形的三个顶点都是M 中的点；
（2） 除顶点外，每个三角形中不再含有M 中的点.
问：可剪出多少个三角形，共需剪多少刀？（剪出一条边需要剪一刀）
【解析】 M 中每个点都是若干三角形的公共顶点，不论怎样剪，纸的四个顶点处各三角形内角和均为
90度，其余1985个点处所有三角形内角和则为360度. 设剪出了x 个三角形，那么全体三角形内角和为180x 度，于是我们得到：18049019853603972x x ?=?+??=
又每个三角形都有三条边，共有39723?条边，另一方面，每剪一次产生两条三角形的边，而四边形的四条边不用剪，设共剪了y 刀，于是所有三角形共有2y+4条边， 由39723245956y y ?=+?=
注 考虑计算“角度”是问题的突破口.请注意比较例3
9． 一个立方体的顶点标上+1或1-，面上标一个数，它等于这个面的4个顶点处的数的乘积.这
样所标的14个数的和能否为0？
【解析】 考虑这14个数的乘积S ：
将每个面所标的数写成4个顶点处的数的乘积，这样，在S 中，每个顶点所标的数将作为乘数出现4次（其中面上乘积中出现3次），从而它对S 的贡献为1，因此8
11S ==；
另一方面，14个数的积S 为1，故这14个为1或1-的数中，1-的个数为偶数，由于1-的个数不为7，故和必不为0.
10． 一条走廊宽 2 m, 长 8 m, 用 6 种颜色的 1?1 m 2
的整块地砖来铺设(每块地砖
都是单色的, 每种颜色的地砖都足够多), 要求相邻(即有公共边的)的两块地砖颜色不同, 那么所有的不同拼色方法有
A. 830个
B. 73025?个
C. 73020?个
D. 73021?个
【解析】 铺第一列(两块地砖)有 30 种方法；其次铺第二列．设第一列的两格铺了 A 、B 两色(如图)，那么，第二列的上格不能铺 A 色．若铺 B 色，则有 (61)- 种铺法；若不
铺 B 色，则有 2
(62)- 种方法. 于是第二列上共有 21 种铺法. 同理， 若前一列铺好，则其后
一列都有 21 种铺法．因此，共有 7
3021? 种铺法． 故选 D ． 注 本题为2005江苏预赛题.
11． 一次竞赛有(2)n n ≥名选手参加，每天选手的得分恰好组成集合{1,2,...,}n ，如果在第k 天
末，每两名选手的得分之和均为52分，求出使这件事成立的所有数对(,)n k
【解析】 一方面，k 天末所有选手得分总和为1
1
(1)2n
l k l kn n =?
=
+∑，另一方面，由每两名选手的得分之和均为52分知总分为26n ，从而(1)52(,)(51,1),(25,2),(12,4),(3,13)k n n k +=?=，经
检验，除第一组外其他都满足，从而共有3对.
注 本题为一个简单的算两次问题 12． 某人有n 元钱，去买三种物品：甲物品1元，乙丙均为2元，求花完这n 元钱有多少种方式？ 【解析】 121,3a a ==，122n n n a a a --=+，1
1(2(1))3
n n n a +=
+- 13． 将一个三位数的三个数字顺序颠倒，将所得到的数与原数相加，若和中没有一个数字是偶数，
则称这个数是“奇和数”，那么，所有的三位数中，奇和数有 （ ） （A ）100个． （B ）120个． （C ）160个． （D ）200个． 【解析】 设三位数为abc ，对,,a b c 的可能取值进行分析.
100()10()()abc cba a c b b a c +=+++++，若a c +不进位，则和数的十位数必为偶数，不
符合题意，所以a c +只能是11，13，15，17.
因为11＝9＋2＝8＋3＝7＋4＝6＋5，所以,a c 取值有2
24A 种可能； 因为13＝9＋4＝8＋5＝7＋6，所以,a c 取值有223A 种可能； 因为15＝9＋6＝8＋7，所以,a c 取值有222A 种可能； 因为17＝9＋8，所以,a c 取值有22A 种可能；
由于b b +不能进位，所以b 只能取0，1，2，3，4.
因此，满足条件的数共有222222225(432)100A A A A +++=个，故选（A ）.
注 本题为2007年广西预赛试题. 对于新定义题，准确理解概念是关键，本题以a c +的可能取值为突破口，使得计数变得简单. 这种题型在小学和初中非常常见
第三讲 二项式定理与组合恒等式
本讲概述
本讲将涉及到组合学的一个重要内容：组合恒等式.从组合数和二项式定理开始，可以得到很多有
A
B
趣的恒等式.事实上，历史上出现过数以千计的组合恒等式，直到现在仍然有新的恒等式出现.在中科大小丛书《组合恒等式》中，史济怀教授给出了两百多个组合恒等式.
由于现在各级竞赛中对组合恒等式要求大为降低，因此本讲只涉及比较简单的恒等式，以及利用这些恒等式来解决问题
以下给出一些基础知识： 1．二项式定理
∑=-∈=+n
k k
k n k n n
n b a C b a 0*)()(N
2．二项展开式的通项
)0(1n r b a C T r
r n r n r ≤≤=-+它是展开式的第r+1项.
3．二项式系数
).0(n r C r
n ≤≤
4．二项式系数的性质
（1）).0(n k C C k
n n k n ≤≤=-
（2）).10(11
1
-≤≤+=---n k C
C
C k n k n k
n
（3）若n 是偶数，有01
122,n n n n
n n n
n
n n C C C C C C -<<
<>>>，即中间一项的二项式系数2n
n
C 最大. 若n 是奇数，有111
10112222,,n n n n n n n n
n
n
n
n
n
n
C C C
C
C C
C
C --++-<<
<=>>>，即中项二项的二项式系
数21
2+n n
n n
C
C 和相等且最大. （4）.2210
n
n n
n n n
C C C C =++++
（5）.21
531420
-=+++=+++n n
n n n n n C C C C C C
（6）.1
11
1
----==k n k n
k n k n
C k
n C nC
kC
或
（7）).(n k m C C C C C C m
m k n m k n
m k m n m n m k k n ≤≤=?=?+---- （8）.11
2
1
++++++=+++++n k n n k
n n n n n n n C
C
C
C
C
以上组合恒等式（是指组合数m
n C 满足的恒等式）是证明一些较复杂的组合恒等式的基本工具.
（1）——（6）请自证.（7）和（8）的证明将在后面给出. 5．证明组合恒等式的方法常用的有
（1）公式法，利用上述基本组合恒等式进行证明.
（2）利用二项式定理，通过赋值法或构造法用二项式定理于解题中. （3）利用数学归纳法.
（4）构造组合问题模型，将证明方法划归为组合应用问题的解决方法. （5）母函数法，此方法仅在冬令营以上级别要求
例题精讲
【例20】 试证明恒等式：
2,(1)0,23n
n n
k
n
k
k
k k
n n
n
n k k k C
C C ====-==∑∑∑ 【解析】 由二项式定理∑=-∈=
+n
k k k
n k
n
n
n b a
C
b a 0
*)()(N 0
(1)n
n
k k
n k x C x =?+=∑，
上式中取1,1,2x =-即得到上述恒等式
注 可见取不同的x 还可以得到一系列恒等式
【例21】 证明： （1）
11
2n
k n n
k kC
n -==?∑
（2）.1
121++++++=+++++n k n n k n n n n n n n
C C C C C
【解析】 （1）由1
1k k n n kC nC
--=可得
1
111
1
1
11
1
1
2
n n
n
n k k k k n n
n n n k k k k kC nC
n C
n C n -------======?=?=?∑∑∑∑ （2）由1
11(01)k k k n n n C C C k n ---=+≤≤-得到
11111
111
121213211()()().n n n
n n n n n n n n n n n n n k n n n n n n k n k n k C C C C C C C C C C C C ++++++++++++++++++++++++++=+-+-++-=
【例22】 证明：220
(1)2n
k n n
k k C
n n -==?+∑
【解析】 首先求
1)n
k n
k k
k C =-∑（，
2
22
2
20
2
01)1)1)(1)2
n
n
n k
k l n n
n n k k l k
k C n n C n n C n n -----===-=-=-=?-∑∑∑（（（， 又
1
1
2n
k n n k kC n -==?∑，相加即得原式 注 类似地，我们还可以求得330
(1)(3)2,....n
k
n n
k k C
n n n -==?++∑
【例23】 证明：2122
(2)!
22(!)
n
k n n k n C n -==+
?∑ 【解析】
222222220
1
1
2n
n
n
n
k k k n
k n
n
n
n
k k k n k n C
C C
C
===+=+=-
=-
∑∑∑∑，
其中令k=2n-j,
21
12222221
n
n n n
k n j j k n n
n
n
n
n
k n j j k C
C
C C C ---=+======-∑∑∑∑,
于是221
222
1(2)!(2)222(!)n
k n n n n
n k n C C n -==+=+?∑
【例24】 已知数列)0(,,,0210≠a a a a 满足 ),,3,2,1(211 ==++-i a a a i i i 求证：对于任何自然数n ，
n n n n n n n n n n n n n n x C a x x C a x x C a x x C a x C a x p +-++-+-+-=-----)1()1()1()1()(111222211100
是x 的一次多项式或零次多项式. 【解析】 由}{211n i i i a a a a 知=++-是等差数列，
则),,2,1(01 =+=+=-i id a d a a i i 从而可将)(x p 表示成d a 和0的表达式，再化简即可.
因为),3,2,1(211 ==++-i a a a i i i ,所以数列}{n a 为等差数列，设其公差为d. 有),3,2,1(0 =+=i id a a i . 从而
n
n n
n n
n n
n
n
x
C nd a x x C d a x x C d a x C a x P )()
1()2()
1()()1()(02
2
2
01
1000+++-++-++-=-- ],)
1(2)1(1[])
1()1([2
2
21
11
10
0n
n n
n n
n n
n
n n
n n
n
n
x nC x x C x x C d x C x x C x C a ++-+-?+++-+-=---
由二项式定理，知
,1])1[()1()1()1(222110=+-=++-+-+---n n n n n n n n n n x x x C x x C x x C x C 又因为,
)]!
1()1[()!1()!1()!(!!1
1--=-----?=-?
=k n k n nC k n k n n k n k n k kC 从而n
n n n n n n x nC x x C x x C ++-+--- 22211)1(2)1(
])
1()1[(12
111----++-+-=n n n n x x x C x nx .])1[(1nx x x nx n =+-=- 所以.)(0ndx a x P +=
当x x P d 为时)(,0≠的一次多项式，当为时)(,0x P d =零次多项式.
注 本题有一定的难度，运算量也很大，需要对二项式定理及常用组合恒等式相当熟练.建议选择讲授. 本题亦可用递推方法来解
【例25】 证明：（1）
2
20
()n
k n
n n k C
C ==∑
（2）
k t k t
n m m n k
C C C -+?=∑ （3）
222(1)()(1)k
k n
n n
n
k
C
C -=-∑
【解析】 考虑(1)(1)m n x x +?+中t
x 的系数：
一方面t
x 的系数即(1)m n x ++的系数，即t
m n C +，
另一方面，利用二项式定理将(1)(1)m n x x +?+展开并相乘，得到t
x 的系数即为（2）式左边，
从而（2）式得证；在此式中令m n t ==即得（1）式. 下证（3）：利用(1)n x -的展开式， 考虑22(1)(1)n n x x -?+中2n
x 的系数：
一方面22(1)n x -展开式中2n x 的系数即为右端；
另一方面22(1)(1)n n x x -?+分别用二项式展开后乘开，2n
x 的系数即为左式，故得证
注 本题使用的方法即母函数方法，但母函数方法在联赛中不要求，我们只举此两例，以供有兴趣的同学了解一下
【例26】 设n m ≥，证明：
2
n m
m k m n m m n m k n k C
C C -+-+=?=∑ 【解析】 考虑从n 个人中选出m 名正式代表及若干名列席代表（列席代表不限，可为0）
一方面，先选定正式代表，有m
n C 种方法，从余下n-m 人中选列席代表，有2n m
-种方法，一
共有2n m m n C -种方法；
另一方面，可先选出包括正式代表和列席代表共m+k 人(0,1,2,...,k n m =-),然后再从中选出m 名正式代表，对每一个k 有m k
m
n
m k C
C
++?种选法，从而选法总数为
n m m k m n m k k C
C -++=?∑种，故
得证
注 本题采用了构造组合模型的方法.事实上，近年来组合恒等式考察内容非常浅，联赛中不会涉及到利用母函数、递推方法、组合模型的复杂恒等式证明，因此，我们仅各举一例说明方法.
【例27】 试用恒等变形方法证明例7的等价形式：
2n
k p n p p n k n k p C
C C -=?=∑
【解析】 注意到k p p n k n k n n p
C C C C --?=?，于是
2n p
n
n
k p
p n k p l n p p n
k
n
n p
n
n p n k p
k p
l C
C C C
C
C
C -----===?=?=?=∑∑∑
注 本题重点是前面的变形
【例28】 （1）试求6432)(x x x x +++展开式中15
x 的系数；
（2）在一次实战军事演习中，红方的一条直线防线上设有20个岗位。为了试验5种不同新式武器，打算安排5个岗位配备这些新式武器，要求第一个和最后一个岗位不配备新式武器，且每相邻5个岗位至少有一个岗位配备新式武器，相邻两个岗位不同时配备新式武器，问共有多少种配备新式武器的方案？ 【解析】 （1）由6
26
6
6
32
6
643
2
)1()1()1()(x x x x x x x x x x x ++=+++=+++，
知只须求626
)1()1(x x ++展开式中9
x 的系数。又
)
615201561( )615201561()1()1(1210864265432626x x x x x x x x x x x x x x ++++++?++++++=++
因此9x 的系数为 6×15＋20×20＋6×15 ＝ 580
（2）设20个岗位按先后排序为1，2，，… ，20，且设第k 种新式武器设置的序号为k a )5,4,3,2,1(=k 。令11a x =，122a a x -=，233a a x -=，344a a x -=，455a a x -=，
5620a x -=，则有
20654321=+++++x x x x x x （*） 其中52≤≤k x )5,4,3,2,1(=k ，416≤≤x 。
作代换 1-=k k x y )5,4,3,2,1(=k ，66x y =，从而有
15654321=+++++y y y y y y （**） 其中41≤≤k y )6,5,4,3,2,1(=k 。
问题（**）的解数等于6
43
2
)(x x x x +++展开式中15
x 的系数，由第一问知它等于580
因为5种新式武器各不相同，互换位置得到不同的排列数，所以配备新式武器的方案数等于
69600!5580=?。
注 本题为2005年浙江省预赛题改编
教师备注：由于本讲内容近年来考察较少，因此不安排过多题目，如内容不够可从习题中选择或适当自行增加例题
备选题： 求证：
∑=+--+=?-n
k k
k n k n k
n C 0
1222.12)
1(
【分析】考虑到恒等式1
2212---+-+=k k n k k n k k n C C C ，仿例2解决.
【证明】令∑=+--??-=n
k k
k n k
n k
n C
a 0
1
222,2
)
1(
因为，1221
2---+-+=k k
n k
k
n k
k n C
C
C
，
.
2)1(2)1(2
)
1(,1.2)1(2
)1()(2)1(2
2)1(2
11)1(21
02)1(21)1(21
2)1(211
21
221
21220
2221212222112222-+---=--+---=--+--=---=-=----=--=+---=--=?-=?--=?-+?-=+?-+=?-+=∑∑∑∑∑∑∑n r r n n r r n r r
r n n r r n r k k
n n
k k
n k
k k n n
k k n k n
k k
k
n k
n k
k k n n
k k k n k n k n
n
k k
k n k n k n
n a C C C
k r C C C C C a 则
令所以
令
∑=---+==?-n
k n n n n k
k n k n k
a a
b b C 0
1222,2)
1(则 ①
.
42)1(4)1()(2)1(2
)1(2)1(2
1110
)1(22)1(211121
1122221
1
2222---=---------=----=---=?--=-++?-+=-+?-+=∑∑∑n n n j j j
n j n j n n k k n n k k k n k n k n
n k n k k n k n k n
n b a C a C C C b 又
于是由①式得1221112112,4,---------=+--=++=n n n n n n n n n n n a a a a a a a a a a b 即从而推知. 这说明{a n }为等差数列，而a 0=1,a 1=2，故公差d=1，且a n =n+1 .
【说明】此题运用变换求和指标的方法，找出了a n ，a n －1，a n －2之间的线性关系式，再由 初始条件求
得a n .这种利用递推关系求组合数的方法，在解决较复杂的计算或证明组合恒等式时经常用到
.
大显身手
14． 数码1232006,,,
,a a a a 中有奇数个9的2007位十进制数12320062a a a a 的个数为
A ．2006
20061(108)2+ B ．200620061(108)2
- C ．20062006108+ D ．20062006108- 【答】（ ）
【解析】 （ B ）出现奇数个9的十进制数个数有12005320032005
200620062006999A C C C =+++，
又由于2006
2006
20062006
(91)
9
k k
k C
-=+=∑以及2006
2006
200620060
(91)
(1)9k
k k k C -=-=-∑，从而得 120053
20032005
20062006
2006200620061999(108)2
A C C C =+++=
-
15． 证明：
1121n
k n k n n
n
n
k C C
C
+-+==∑
【解析】 考虑(1)(1)n n x x +?+中1
n x
+的系数：
一方面1
n x
+的系数即2(1)n
x +的系数，即1
2n n C +，
另一方面，利用二项式定理将(1)(1)n n x x +?+展开并相乘，得到1
n x
+的系数即为原式左边，从而得证；
注 本题为例6（2）的特例
16． 证明：
1
1
(1)11k n
k
n
k n C k n -=-=++∑ 【解析】 1111
111111
1120
(1)(1)11(1)[1(1)]11111k k n n n n k k k k k k
n n n n n k k k k n C C C C C k n n n n --+++++++====--==-=-++-=+++++∑∑∑∑
17． 数列}{n a 中，1
13,3(2)n a n
a a n -==≥，求2001a 的末位数字是多少？ 【解析】 先利用n 的初值猜想n a 的特点与n a 的末位数字： 当n=1时，a 1=3，3642733321+?====a
a
27)81(3)81(3)3(3336363643642732?=?=?====+?a a ，因此32,a a 的末位数字都是7，
猜想，.*,34N ∈+=m m a n 现假设n=k 时，.*,34N ∈+=m m a k
当n=k+1时， 34341)14(33
+++-===m m a k k
a
340
34342412434124134034034)1
(4)1(4)1(4)1(4++++++++++-??+-??++-??+-?=m m m m m m m m m m C C C C ,3)1(414+-=-=T T 从而完成了归纳论证. 所以对任意正整数n ，*)(34N ∈+=m m a n 于是.27)81(33
341?===++m m a n n
a 故2001a 的末位数字是7.
注 本题中利用初值得到规律进而猜想34+=m a n 是问题解决的关键. 在很多数学竞赛问题解决过程中都需要对初值进行分析从中找出规律，这是对将来进行数学研究过程中解决未解决的数学问题的一
种必要训练.
18． 已知),2,1(8,1,01110 =-===-+n a a a a a n n n 试问：在数列}{n a 中是否有无穷多个能被
15整除的项？证明你的结论.
【解析】 数列}{n a 的特征方程为,0182
=+-x x 它的两个根为154,15421-=+=x x ， 所以n n n B A a )154()154(-++= （n=0，1，2，…）
由,15
21,15
211,010-
==
==B A a a 得 则],)154()154[(15
21n n n a --+=
取),2,1,0(2 ==k k n ，由二项式定理得
])15(42)15(421542[15
211133311----??++??+??=
n n n n n n n n C C C a
),
(1542)
15
44
(154
15
4154415
4154
4
122
1223
23
21
21
2122323212122
23
31
1为整数其中T T
k C
C C C C C C C C k k k k
k k
k k
k k k k k k k n n n
n n
n n
+?=??++?+?=??++??+?=??++??+?=-----------
由上式知当15|k ，即30|n 时，15|a n ，因此数列}{n a 中有无穷多个能被15整除的项.
第四讲 抽屉原理与存在性问题
本讲概述
本讲我们将讲述组合数学中一个非常简单却又十分重要，应用十分广泛的一个原理，即抽屉原理.
然后我们将给出与抽屉原理内涵相通的几个变形，即平均值原理与图形重叠原理.
事实上这几个原理是用来证明存在性问题的有力工具之一，当然我们还可以利用极端原理、反证法、数学归纳法、算两次、计数方法和构造法等等来加以证明.本讲我们主要讲述利用平均值原理（其在整数和图形范围内的形式分别为抽屉原理和图形重叠原理）来证明存在性问题，并略举数例说明其它方法在证明存在性问题中的应用.
第一抽屉原理：若将m 个物件放入n 个抽屉中，则必有一个抽屉内至少有1
[]1m n -+个物件. 第二抽屉原理：若将m 个物件放入n 个抽屉中，则必有一个抽屉内至多有[]m
n
个物件.
事实上这两个原理利用极端性原理与反证法极易证明，此处从略. 平均值原理1：设12,,...,n a a a 为实数，且12...n
a a a A n
+++=，则12,,...,n a a a 中必有一个不小于
A ，也必有一个不大于A
平均值原理2：设12,,...,n a a a
为正实数，且G =，则12,,...,n a a a 中必有一个不小于G ，也必有一个不大于G
图形重叠原理：把面积为12,,...,n S S S 的n 个平面图形以任意方式放入一个面积为S 的平面图形A 内，
（1） 如果12...n S S S S +++>，则必有两个图形有公共点；
（2） 如果12...n S S S S +++<，则必有一点不属于上述n 个图形中任意一个
可以发现，上述三组原理都是极端性原则在不同场合的具体表现形式. 极端性法则是处理组合数学中存在性的利器，通过对这三组原理及其解题技巧的深刻把握，我们也可以自己创造一些类似的极端性原理来解决问题.
教师备注：本节题目有些可能学生在初中接触过，教师可以适当选择其中较有新意的问题.
例题精讲
利用抽屉原理解题的关键是根据题目特点巧妙地构造“抽屉”：将题目中涉及元素按照某一性质分类，当取出足够多的元素时，即可断言必有某些元素属于同一个“抽屉”.构造抽屉的常用方法有：划分集合、分割图形、利用剩余类等等.与抽屉原理相关的试题中，联赛中的题目往往利用抽屉原理是解题的关键，但在冬令营级别的赛题中，往往抽屉原理只是其中的一小步或者利用它解决其中的小块问题而已. 【例29】 将平面上的每个点都以红、蓝两色之一着色，证明：存在这样两个相似的三角形，它们的相
似比为1995，并且每一个三角形的三个顶点同色。
【解析】 任取一点O 为圆心，以1,1995为半径作两个同心圆，在内圆上任取9点，由抽屉原理知至少
有5点同色，记为125,,...,A A A ,再设此五条半径与外圆交于125,,...,B B B ,由抽屉原理必有3
点同色，设为,,i j k B B B ，于是,i j k i j k B B B A A A ??即为所求
注 本题为1995年全国联赛第4题
【例30】 在任意给出的100个整数中，都可以找出若干个数来（可以是一个数），它们的和可被100
整除。
【解析】 设已知的整数为a 1,a 2,…a 100
考察数列a 1,a 2,…a 100的前n 项和构成的和数列S 1，S 2，…S 100。
如果S 1，S 2，…S 100中有某个数可被100整除，则命题得证。否则，就有S 1，S 2，…S 100均不能被100整除，这样，它们被100除后余数必是{1，2，…，99}中的元素。由抽屉原理I 知，S 1，S 2，…S 100中必有两个数，它们被100除后具有相同的余数。
不妨设这两个数为S i ，S j （i ＜j ），则12100|100|...J i i i j S S a a a ++-?+++.命题得证。
注 本题所采用的这种利用连续项构造和式的方法非常经典
【例31】 从1-100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个是另一个的
整数倍.
【解析】 把1-100的正整数分成如下50个抽屉（因为1-100中共有50个奇数）：
（1）{1，1×2，1×22，1×23，1×24，1×25，1×26
}；
（2）{3，3×2，3×22，3×23，3×24，3×25
}；
（3）{5，5×2，5×22，5×23，5×24
}；
（4）{7，7×2，7×22，7×23
}；
（5）{9，9×2，9×22，9×23
}；
（6）{11，11×2，11×22，11×23
}； ……
（25）{49，49×2}；
（26）{51}； ……
（50）{99}。
从这100个数中任取51个数，也即从这50个抽屉内任取51个数，根据抽屉原则，其中必定至少有两个数属于同一个抽屉，即属于（1）-（25）号中的某一个抽屉，显然，在这25个抽屉中的任何同一个抽屉内的两个数中，一个是另一个的整数倍。 注 请注意本题是按照整数奇偶性质进行了巧妙的分类
【例32】 已给一个由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个无公共
元素的非空子集合，各子集合中各数之和相等.
【解析】 一个有着10个元素的集合有210
=1024个子集，包括空集和全集在内。空集与全集显然不是考
虑的对象，所以剩下1024-2=1022个非空真子集。
再来看各个真子集中一切数字之和。用N 来记这个和数，很明显： 10≤N≤91+92+93+94+95+96+97+98+99=855
这表明N 至多只有855-9=846种不同的情况。由于非空真子集的个数是1022，1022＞846，所以一定存在两个子集A 与B ，
使得A 中各数之和=B 中各数之和。
若A∩B=φ，则命题得证，若A∩B=C≠φ，即A 与B 有公共元素，这时只要剔除A 与B 中的一切公有元素，得出两个不相交的子集A 1与B 1，很显然 A 1中各元素之和=B 1中各元素之和，因此A 1与B 1就是符合题目要求的子集。
注 本题中不论抽屉构造方法，还是最后对集合A,B 有公共情况的处理手法都非常巧妙，值得仔细体会
【例33】 试求最小的正整数,n 使得对于任何n 个连续正整数中，必有一数，其各位数字之和是7的倍
数.
【解析】 首先，我们可以指出12个连续正整数，例如994，995，...，999，1000，1001， (1005)
其中任一数的各位数字之和都不是7的倍数，因此，13n ≥。
再证，任何连续13个正整数中，必有一数，其各位数字之和是7的倍数.
对每个非负整数a ，称如下10个数所构成的集合:{10,101,109}a A a a a =++为一个“基本段”，13个连续正整数，要么属于两个基本段，要么属于三个基本段。
当13个数属于两个基本段时，据抽屉原理，其中必有连续的7个数，属于同一个基本段；当13个连续数属于三个基本段11,,a a a A A A -+时，其中必有连续10个数同属于a A .现在设1
10k k a a a a -
1
101
10(1),
(6)k k k k a a a a a a a a --++是属于同一个基本段的7个数，它们的各位数字之和分别是
,1,,6,k
k k
i i
i
i i i a a a ===++∑∑∑显然，这7个和数被7除的余数互不相同，其中必有一个是7的倍数.因
此，所求的最小值为13.n =
注 本题为2005江西省预赛题.可以看到，在很多组合问题中，我们往往需要用到包括抽屉原理在内的多种技巧才能最终解决问题.
【例34】 从前25个自然数中任意取出7个数，证明：取出的数中一定有两个数，这两个数中大数不超
过小数的1.5倍.
【解析】 把前25个自然数分成下面6组：
1； ① 2，3； ② 4，5，6； ③ 7，8，9，10； ④ 11，12，13，14，15，16； ⑤ 17，18，19，20，21，22，23， ⑥ 因为从前25个自然数中任意取出7个数，所以至少有两个数取自上面第②组到第⑥组中的某同一组，这两个数中大数就不超过小数的 1.5倍. 注 将题目中的25,7改为91,10，结论仍然成立.这就是基辅49届竞赛题，事实上我们可以按照此题的思想自己设计一些类似的问题.
【例35】 (1)任选6人，试证其中必有3人，他们互相认识或都不认识.
(2) 17名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目，而且任意两名科学家通信时只讨论一个题目，证明：其中至少有三名科学家，他们
相互通信时讨论的是同一个题目。
【解析】 (1)用A 、B 、C 、D 、E 、F 表示这6个人，首先以A 为中心考虑，他与另外五个人B 、C 、D 、E 、
F 只有两种可能的关系：认识或不认识，那么由抽屉原则，他必定与其中某三人认识或不认识，现不妨设A 认识B 、C 、D 三人，当B 、C 、D 三人都互不认识时，问题得证；当B 、C 、D 三人中有两人认识，如B 、C 认识时，则A 、B 、C 互相认识，问题也得证
(2) 视17个科学家为17个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题，若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线，若讨论第3个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。 考虑科学家A ，他要与另外的16位科学家每人通信讨论一个问题，相应于从A 出发引出16条线段，将它们染成3种颜色，而16=3×5+1，因而必有6=5+1条同色，不妨记为AB 1，AB 2，AB 3，AB 4，AB 5，AB 6同红色，若B i （i=1，2，…，6）之间有红线，则出现红色三角线，命题已成立；否则B 1，B 2，B 3，B 4，B 5，B 6之间的连线只染有黄蓝两色。
考虑从B 1引出的5条线，B 1B 2，B 1B 3，B 1B 4，B 1B 5，B 1B 6，用两种颜色染色，因为5=2×2+1，故必有3=2+1条线段同色，假设为黄色，并记它们为B 1B 2，B 1B 3，B 1B 4。这时若B 2，B 3，B 4之间有黄线，则有黄色三角形，命题也成立，若B 2，B 3，B 4，之间无黄线，则△B 2，B 3，B 4，必为蓝色三角形，命题仍然成立。
注 这是著名的图论入门问题,二染色或三染色时的处理方式其实是相同的.
【例36】 任意给定10个自然数，试证明：可以用减，乘两种运算以及括号将它们适当连结起来，其结
果可被1890整除.
【解析】
3
18902357=???,设给定自然数为1210,,...,a a a ，先按模9的剩余类来分成9个抽屉，必有两个在同一抽屉，其差可被9整除，不妨设为1099|a a -，
同理可得到8765437|,5|,3|a a a a a a ---，最后，若12,a a 中有一个为偶，那么122|a a ?，否则212|a a -，将上述5式连乘起来即可
【例37】 n 支球队要举行主客场双循环比赛（每两支球队比赛两场，各有一场主场比赛），每支球队在
一周（从周日到周六的七天）内可以进行多场客场比赛。但如果某周内该球队有主场比赛，在这一周内不能安排该球队的客场比赛。如果4周内能够完成全部比赛，求n 的最大值。
【解析】 （1）如右图所示：表格中有“*”， 表示该球队在该周有主场比赛，不能出访。 容易验证，按照表中的安排，6支球队四周 可以完成该项比赛。
（2）下面证明7支球队不能在四周 完成该项比赛。设(1,2,3,4,5,6,7)i S i =表示 i 号球队的主场比赛周次的集合。假设4周内
能完成该项比赛，则i S 是{1，2，3，4}的非空真子集。
一方面由于某周内该球队有主场比赛，在这一周内不能安排该
球队的客场比赛，所以(1,2,3,4,5,6,7)i S i =中，没有一个集是另一个的子集。
另一方面，设{}{}{}{1},{1,2},{1,2,3},{2},{2,3},{2,3,4},{3},{1,3},{1,3,4}A B C ===
{}{}{}{4},{1,4},{1,2,4},{2,4},{3,4}D E F === 由抽屉原理，一定存在
,,,,{1,2,3,4,5}i j i j i j ≠∈，,i j S S 属于同一集合A 或B 或C 或D 或E 或F ，
必有i j S S ?或j i S S ?发生.
所以，n 的最大值是6.
注 本题为第一届东南数学奥林匹克第7题. 本题是一道组合极值问题，组合极值的构造与论证难度一般都很大，而抽屉原则在组合极值的论证中常常用到.
【例38】 从4个同心圆的圆心出发的100条射线等分各圆周，分别与4个圆各有100个交点，任意给
每个圆上的点染上黑白两色之一，使每个圆上都恰有50个黑点和50个白点，证明：可将此4个圆适当旋转，使这100条射线中至少存在13条射线，它们中每一条穿过的4个点颜色都相同. 【解析】 称某个圆顺时针旋转
2100
π
为旋转一次，并由里到外称4个圆为圆1，圆2，圆3，圆4. 固定圆1，任取圆1上某点A ，有100种取法，不妨设它为黑；
此时，旋转圆2，其中有50次与点A 颜色相同，任取其中一点B,固定圆2，再旋转圆3，如此下去，一共旋转了100100100??次，共出现同色四点组(,,,)A B C D 有100505050???个，
平均每次出现100505050
12.5100100100
???=??个同色四点组，
根据平均值原理，必在某次旋转后存在12.513n n ≥?≥条射线，它们中每一条穿过四点同
色.
大显身手
19．把1到10的自然数摆成一个圆圈，证明一定存在3个相邻的数，它们的和数大于17.
【解析】设a1，a2，a3，…，a9，a10分别代表不超过10的十个自然数，它们围成一个圈，三个相邻的数的组成是（a1，a2，a3），（a2，a3，a4），（a3，a4，a5），…,（a9，a10，a1）,（a10，a1，a2）共
十组.现把它们看作十个抽屉，每个抽屉的物体数是a1+a2+a3，a2+a3+a4，a3+a4+a5，…a9+a10+a1，a10+a1+a2,由于
（a1+a2+a3）+（a2+a3+a4）+…+（a9+a10+a1）+（a10+a1+a2）
=3(a1+a2+…+a9+a10)=3×(1+2+…+9+10)
根据平均原则,至少有一个括号内的三数和不少于17,即至少有三个相邻的数的和不小于17.
20．在边长为1的等边三角形内（包括边界）有任意五个点（图1）。证明：至少有两个点之间的
距离不大于1 2 .
【解析】顺次连接三角形三边中点，即三角形的三条中位线，可以分原等边三角形为4个全等的边长
为1
2
的小等边三角形，则5个点中必有2点位于同一个小等边三角形中（包括边界），其距
离便不大于1
2
.
注 (1)事实上，严谨起见，我们还需要证明引理：
Lemma:三角形内（包括边界）任意两点间的距离不大于其最大边长
如图，设BC是△ABC的最大边，P，M是△ABC内（包括边界）任意两点，连接PM，过P分别作AB、BC边的平行线，过M作AC边的平行线，设各平行线交点为P、Q、N，那么
∠PQN=∠C，∠QNP=∠A
因为BC≥AB，所以∠A≥∠C，则∠QNP≥∠PQN，而∠QMP≥∠QNP≥∠PQN（三角形的外角大于不相邻的内角），所以PQ≥PM。显然BC≥PQ，故BC≥PM.
（2）这里是用等分三角形的方法来构造“抽屉”。类似地，还可以利用等分线段、等分正方形的
21．a，b，c，d为四个任意给定的整数，求证：以下六个差数
b-a，c-a，d-a，c-b，d-b，d-c
的乘积一定可以被12整除.
【解析】把这6个差数的乘积记为p，只须证明：3与4都可以整除p，以下分两步进行：第一步，把a，b，c，d按以3为除数的余数来分类，这样的类只有三个，故知a，b，c，d中至少有2个除以3的余数相同，例如，不妨设为a，b，这时3可整除b-a，从而3可整除p；
第二步，再把a，b，c，d按以4为除数的余数来分类，这种类至多只有四个，如果a，b，c，d 中有二数除以4的余数相同，那么与第一步类似，我们立即可作出4可整除p的结论.设a，b，c，d 四数除以4的余数不同，由此推知，a，b，c，d之中必有二个奇数（不妨设为a，b），也必有二个偶数（设为c，d），这时b-a为偶数，d-c也是偶数，故4可整除(b-a)(d-c)，自然也可得出4可整除p.
22
．平面上任作8条直线，互不平行，证明其中必有两条直线的夹角23
<
【解析】在一条直线上取点O，过O点作其它7条线的平行线，将平角分为8份，其中必有一份
180
23
8
≤<
23．15个人围着圆桌坐下，圆桌上有15个人的名牌，但是大家是随意坐的，坐下以后才发现没有一个人与桌上的名牌相对应，证明：可以转动圆桌，使得至少两个人与他们的名牌相符【解析】每个人都可以转动圆桌使得自己与名牌相符，但是转动只有14种，15个人中必有两个人的转动方式相同，从而得证.
第五讲容斥原理与极端性原理
本讲概述
本讲我们讨论组合数学中两个非常重要的原理：容斥原理与极端性原理.
注：为了让大家在寒假班能够对组合数学有一个概貌了解，本讲与下一讲都安排了两个论题，但这两个论题的联系并不大.
当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择.将整体分解为部分也就是将有限集X表示成它的一组两两互异的非空真子集A1，A2，…A n的并集，即}
,
,
,
{
.
2
1
2
1n
n
A
A
A
A
A
A
X
=
=?
集合
叫做集合X的一个覆盖.一个特殊情况是，集族?中的任意两个集合都不相交，这时我们称集族?为集合X的一个（完全）划分.如?为集合X的划分，则对集合X的计数可通过熟知的加法公式
|
|
|
|
|
|
|
||
|
3
2
1n
A
A
A
A
X+
+
+
+
=
进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事. 而容斥原理就是涉及到n个集合的计数问题最常用的解决方法；
容斥原理相关知识如下：
相对补集：称属于A而不属于B的全体元素，组成的集合为B对A的相对补集或差集，记作A-B.
容斥原理：以A 表示集合A 中元素的数目，对n 个集合12,,...,n A A A ，我们有 定理1 设则为有限集,),,2,1(n i A i =
∑∑
=≤<≤=-=-++-=
n
i n
j i i n
i n j i i
i n
i A A A A A 1
11
1
1||)
1(||||||
定理2 设),,2,1(n i A i =为有限集I 的子集，则||||||||1
1
1
i n
i i n
i i n
i A I A A ===-==
∑∑
=≤<≤=-+++
-
=n
i n
j i i n
i n
j i i
A A A A
I 1
11
||)1(||||||
实际上，容斥原理的问题我们在小学和初中曾经就多次接触过，只不过没有明确提出这个概念以及它的一般形式.
而极端性原理则是一种非常重要的数学思想. 从问题的极端情况考虑，对于数值问题来说，就是指取它的最大或最小值（例如数集中的最大值，获胜场数最多的队员，图形中的最大面积等）；对于一个动点来说，指的是线段的端点，三角形的顶点等等。极端化的假设实际上也为题目增加了一个条件，求解也就会变得容易得多；
例题精讲
板块一 容斥原理
【例39】 （热身问题）计算不超过120的合数的个数 【解析】 （1）设S1＝{a ∣1≤3≤120,2∣a}；S2＝{b ∣1≤b≤120,3∣b}；S3＝{c ∣1≤3≤120,5∣c}；S4={d
∣1≤d≤120,7∣d}，则有：
card(S1)＝[120/2]=60，card(S2)＝[120/3]＝40，card(S3)＝[120/5]＝24，card(S4)＝[120/7]＝17； ([n]表示n 的整数部分，例如[2,4]＝2，…) card(S1∩S2)＝[120/2×3]＝20，card(S1∩S3)＝[120/2×5]＝12， card(S1∩S4)＝[120/2×7]＝8，card(S2∩S3)＝[120/3×5]＝8， card(S2∩S4)＝[120/3×7]＝5，card(S3∩S4)[120/5×7]＝3， card(S1∩S2∩S3)[120/2×3×5]＝4，card(S1∩S2∩S4)＝[120/2×3×7]＝2， card(S1∩S3∩S4)＝[120/2×5×7]＝1，card(S2∩S3∩S4)＝[120/3×5×7]＝1， card(S1∩S2∩S3∩S4)＝[120/2×3×5×7]＝0
∴card(S1∪S2∪S3∪S4)＝card(S1)＋card(S2)＋card(S3)＋card(S4)－card(S1∩S2)－card(S1∩S3)－card(S1∩S4)－card(S2∩S3)－card(S2∩S4)－card(S3∩S4)＋card(S1∩S2∩S3)＋card(S1∩S2∩S4)＋card(S1∩S3∩S4)＋card(S2∩S3∩S4)－card(S1∩S2∩S3∩S4)＝(60＋40＋24＋17)-(20+12+8+8+5+3)+(4+2+1+1)-0＝141-56＋8＝93 ∵2，3，5，7是质数
即不超过120的合数共有89个。
注 card(A)就是A ，表示集合A 中元素的数目
【例40】 某班对数学、物理、化学三科总评成绩统计如下：优秀的人数：数学21个，物理19个，化
学20个，数学物理都优秀9人，物理化学都优秀7人。化学数学都优秀8人。这个班有5人任何一科都不优秀。那么确定这个班人数以及仅有一科优秀的三科分别有多少个人。
【解析】 设A={数学总评优秀的人} B={物理总评优秀的人} C={化学总评优秀的人} 则|A|=21， |B|=19， |C|=20，
这表明全班人数在41至48人之间。 仅数学优秀的人数是
可见仅数学优秀的人数在4至11人之间。 同理仅物理优秀的人数在3至10人之间。 同理仅化学优秀的人数在5至12人之间。 注 对于基础较好的同学，此题可不讲
【例41】 1992位科学家，每人至少与1329人合作过，那么，其中一定有四位数学家两两合作过。 【解析】 在与一个人A 合作的人中我们找到B 。再说明一定有人与A 和B 都合作过为C 。最后再说明
有人与A 、B 、C 都合作过为D ，那么A 、B 、C 、D 就是找的人了。
证明：一个人A 。不妨设B 与之合作。那么
.
即C 与A 和B 均合作过
，
分别表示与A 、B 合作过的人的集合。同样地
，
。
所以存在
。则A 、B 、C 、D 就是所求，证毕。
注 本题为一道典型的图论问题，我们用容斥原理的方法来解决它
【例42】 将与105互素的所有正整数从小到大排成数列，试求出这个数列的第1000项。
【解析】 首先计算{1,2,...,105}S =内与105互素的整数个数，由容斥原理，令{|,|}i A m m S i m =∈，
于
是
3
5
7105
1
053
57
A A A =--?
?， 易知每105个数里有48个与105互素，而1000482040=?+，所以100040a a =，
由4847104,103,a a ==接下来是101,97,94,92,89,88,86知100040a a ==86
注 本题为1994年联赛二试题
【例43】 一个人写了n 封不同的信及相应的n 个不同的信封，他把这n 封信都装错了信封，问这样的
装法有多少种？
【解析】 先把n 个不同的元素及相应的位置都编上序号1，2，…，n ，并且约定：在n 个不同元素的
排列中
1° 若编号为i(i=1，2，…，n)的元素排在第i 个位置，则称元素i 在原位；否则称元素i 不在原位． 2° 若所有的元素都不在原位，则称这种排列为n 个不同元素的一个错排(若每个元素都在原位则称为序排)．
按照上面约定，“装错信封问题”即为n 个不同元素的错排问题，则可构建“装错信封问题”的数学模型为：在n 个不同元素的全排列中，有多少种不同的错排？ 记S 为全排列构成的集合，j A 为j 在原位的所有排列所构成的集合， 易知|S|=n ！，|Ai|=(n －1)！，|A i∩Aj|=(n －2)！，…，
从而由容斥原理，错位排列数1
1
1||||||(1)|
|n
n n
i
i j i i i i j n
n D S A A A A ==≤<≤=-
++
+-∑∑
123!(1)!(2)!(3)!...(1)()!n n
n n n n n C n C n C n C n n =-?-+?--?-++-?-
111(1)!(1...)1!2!3!3!
n n -=-+-++
注 本题为“装错信封问题”，是由著名数学家约翰·伯努利(Johann Bernoulli ，1667－1748)的儿子丹尼
尔·伯努利(Danid Bernoulli ，1700－1782)提出来的，是一道典型的利用容斥原理或递推方法来解决的问题.
【例44】 设n 是正整数，我们说集合}2,......,
3,2,1{n 的一个排列),......,,(221n x x x 具有性质P 是指：存在i
属于集合}12,....,2,1{-n 使得n x x i i =-+||1。求证，对于任何n ，具有性质P 的排列比不具有性质P 的排列数多.
【解析】 只需要证明具有性质P 的排列数超过全排列数一半. 设A 为不具有性质P 的排列的集合，B
为具有性质P 的排列的集合，显然)!2(||||n B A =+ 为了|,|||B A <只需证得 )!.2(2
1
||n B >
利用容斥原理。设在),......,,(221n x x x 中，k 与n k + 相邻的排列的集合为k A ，n k ,...3,2,1= 可以计算出)!.12(2||-?=n A k （事实上将n k k +,这两个相邻的数放在一起则k A 中的元素可以
看成12-n 个元素的全排列，另外n k k +,可互换位置。即得)!.12(2||-?=n A k ） 同理 .,,1,)!22(2||2j k n j k n A A j k ≠≤≤-?=? 则 )!22(2)!12(2||||||22
11
-??--??=?-
≥
∑∑≤<≤=n C n n A A
A
B n j n
j k k
n
k k
)!.2(2
1
)!22(2122)!22(2)!22()1(2)!2(n n n n n n n n n n n ?=-?-?>-??=-?--= 结论得证。
板块二 极端性原理
【例45】 在一个8×8的方格棋盘的方格中，填入从1到64这64个数。问：是否一定能够找到两个相
邻的方格，它们中所填数的差大于4？
【解析】 考虑这个方格棋盘的左上角、右上角及右下角内的数A ，B ，S 。
设存在一个填数方案，使任意相邻两格中的数的差不大于4，考虑最大和最小的两个数1和64的填法，为了使相邻数的差不大于4，最小数1和最大数的“距离”越大越好，即把它们填在对角的位置上（A=1，S=64）。
然后，我们沿最上行和最右行来观察：因为相邻数不大于4，从 A →B →S 共经过14格，所以 S ≤1+4×14=57（每次都增加最大数4），与S=64矛盾。因而，1和64不能填在“最远”的位置上。显然，1和64如果填在其他任意位置，那么从1到64之间的距离更近了，更要导致如上的矛盾。因此，不存在相邻数之差都不大于4的情况，即不论怎样填数必有相邻两数的差大于4。
【例46】 有n 名（n ≥3）选手参加的一次乒乓球循环赛中，没有一个全胜的。问：是否能够找到三名
选手A ，B ，C ，使得A 胜B ，B 胜C ，C 胜A ？
【解析】 从极端情况观察入手，设B 是胜的次数最多的一个选手，但因B 没获全胜，故必有选手A 胜
B 。在败给B 的选手中，一定有一个胜A 的选手
C ，否则，A 胜的次数就比B 多一次了，这与B 是胜的次数最多的矛盾。
所以，一定能够找到三名选手A ，B ，C ，使得A 胜B ，B 胜C ，C 胜A 。
【例47】 有三所学校，每所学校有n 名学生，已知任意一名学生认识其他两所学生的总数都是n+1，
证明：每所学校都存在一名学生，使得这3名学生互相认识（假设认识是相互的）
【解析】 从3所学校的3n 名学生中选取这样一名学生A ，他认识其他两所学校中某一所学校的人数是
最多的，这个最大值为k n ≤. 不妨设A 在第一所学校，他认识第二所学校的k 名学生，于是他认识第3所学校的人数为 11n k +-≥，即A 至少认识第三所学校校的一名学生C.
如果c 认识第二所学校的某学生B ，那么A,B,C 互相认识，命题成立；否则C 认识第二所学校的学生至多为n-k ，从而c 认识第一所学校的学生人数至少为1()1n n k k +--=+，此与
k 的最大性假设相违.从而原命题得证
注 本题实际是一道图论问题 【例48】 n （n ≥3）名乒乓球选手单打比赛若干场后，任意两个选手已赛过的对手恰好都不完全相同。 试证明，总可以从中去掉一名选手，而使余下的选手中，任意两个选手已赛过的对手仍然都不完全相同. 【解析】 如果去掉选手H ，能使余下的选手中，任意两个选手已赛过的对手仍然都不完全相同，那么
我们称H 为可去选手。我们的问题就是要证明存在可去选手。
设A 是已赛过对手最多的选手。
若不存在可去选手，则A 不是可去选手，故存在选手B 和C ，使当去掉A 时，与B 赛过的选手和与C 赛过的选手相同。从而B 和C 不可能赛过，并且B 和C 中一定有一个（不妨设为B ）与A 赛过，而另一个（即C ）未与A 赛过。
又因C 不是可去选手，故存在选手D ，E ，其中D 和C 赛过，而E 和C 未赛过。
显然，D 不是A ，也不是B ，因为D 与C 赛过，所以D 也与B 赛过。又因为B 和D 赛过，所以B 也与E 赛过，但E 未与C 赛过，因而选手E 只能是选手A 。
于是，与A 赛过的对手数就是与E 赛过的对手数，他比与D 赛过的对手数少1，这与假设A 是已赛过对手最多的选手矛盾。
故一定存在可去选手。
大显身手
24． 三对夫妻站成一行，每对夫妻都不相邻的排法有多少种？ 【解析】 记{
}
3I =对夫妻的全排列．
{}i A i =第对夫妻相邻的全排列，1,2,3i =．
由容斥原理
1
2
31
2
31
2
3A A A A A A I A A A ==-
1223
33336!25!24!23!C C C =-??+??-??=240种．
25． 在不大于6
10的正整数中，有多少个数至少可被3,5,7之一整除？ 【解析】 应用容斥原理可得到
333,333200,0001428576666628571476199523542857A =++---+=
26． （2005年浙江省预赛试题）在一次实战军事演习中，红方的一条直线防线上设有20个岗位.
为了
试验5种不同新式武器，打算安排5个岗位配备这些新式武器，要求第一个和最后一个岗位不配备新式武器，且每相邻5个岗位至少有一个岗位配备新式武器，相邻两个岗位不同时配备新式武器，问共有多少种配备新式武器的方案？ 【解析】 设20个岗位按先后排序为1，2，，…，20，且设第k 种新式武器设置的序号为k a )5,4,3,2,1(=k .
令11a x =，122a a x -=，233a a x -=，344a a x -=，455a a x -=，5620a x -=，则有
20654321=+++++x x x x x x （1） 其中52≤≤k x )5,4,3,2,1(=k ，416≤≤x .
作代换1-=k k x y )5,4,3,2,1(=k ，66x y =，从而有
15654321=+++++y y y y y y （2） 其中41≤≤k y )6,5,4,3,2,1(=k .
设A 为不定方程（2）的正整数解的全体，k A )6,5,4,3,2,1(=k 为A 中满足4>k y 的解的全体.因为没有同时满足4>i y ，4>j y ，4>k y 的的正整数组满足不定方程（2），所以i j k A A A =?，根
据容斥原理，可得
6
6
6
1
1
1
k k k j
k
k j k
k k A A A A A A A =<===-
=-+∑∑580901512200265626510514=+-=+-=C C C C .
因为5种新式武器各不相同，互换位置得到不同的排列数，所以配备新式武器的方案数等于
69600!5580=?.
注 本题在计数部分做过，此处我们利用容斥原理来解决
27． 新上任的宿舍管理员拿着20把钥匙去开20个房间的门，他知道每把钥匙只能打开其中的一
个门，但不知道哪一把钥匙开哪一个门，现在要打开所有关闭的20个门，他最多要开多少次？
【解析】 从最不利的极端情况考虑：打开第一个房间要20次，打开第二个房间需要19次……共计最
多要开
20＋19＋18＋…＋1=210（次）。
28． 把1600粒花生分给100只猴子，请你说明不管怎样分，至少有4只猴子分的花生一样多。 【解析】 假设没有4只猴子分的花生一样多，那么至多3只猴子分的花生一样多。我们从所需花生最
少情况出发考虑：
得1粒、2粒、3粒……32粒的猴子各有3只，得33粒花生的猴子有1只，于是100只猴子最少需要分得花生
3×（0+1+2+…+32）+33=1617（粒），
现在只有1600粒花生，无法使得至多3只猴子分的花生一样多，故至少有4只猴子分的花生一样多。
注 本题实际上是平均原理的一个简单应用
29． 在一块平地上站着5个小朋友，每两个小朋友之间的距离都不相同，每个小朋友手上都拿着
一把水枪。当发出射击的命令后，每人用枪射击距离他最近的人。问：射击后有没有一个小
朋友身上是干的？为什么？
【解析】设A和B两人是距离最近的两个小朋友，显然他们应该互射。此时如果有其他的小朋友射向他们中的一个，即A，B中有一人挨了两枪，那么其他三人中必然有一人身上是干的。如果
没有其他的小朋友射向A或B，那么我们再考虑剩下的三个人D，E，F：若D，E的距离是
三人中最近的，则D，E互射，而F必然射向他们之间的一个，此时F身上是干的。
注本题考虑了距离最近这个极端性元素
第六讲染色问题与操作问题
本讲概述
染色问题类型多样，异彩纷呈，并没有一定的模式，它需要的知识量不多，但需要解题人具有很强的想象能力与推理能力；事实上，染色作为一种手段和工具，可以用来解决代数（例如有理点问题）、图论、方格表问题等多种形式的问题. 染色问题可分为：
1、小方格染色问题
这是最简单的染色问题，是从一种民间游戏中发展起来的方格盘上的染色问题.解决这类问题的方法后来又发展成为解决方格盘铺盖问题的重要技巧.
2．线段染色和点染色
(1)线段染色.较常见的一类染色问题是发样子组合数学中图论知识的所谓“边染色”（或称“线段染色”），主要借助抽屉原则求解.
（2）点染色.对离散的有限个点或平面上的点进行染色.
操作问题是发源于博弈论的组合趣题；有不少操作问题是以染色形式呈现；但更多的操作问题涉及到单人与双人的胜负，对推理能力要求很高.由于联赛中出现操作问题相对较少，我们只举数例简单介绍之.
例题精讲
板块一染色问题
【例49】线段AB上有1998个点（包括A，B两点），将点A染成红色，点B染成蓝色，其余各点染成红色或蓝色。这时，图中共有1997条互不重叠的线段。
问：两个端点颜色相异的小线段的条数是奇数还是偶数？为什么？
【解析】如果中间的1996个点全部染成红色，这时异色线段仅有1条，是一个奇数。将任意一个红点染
成蓝色时，这个改变颜色的点的左右两侧相邻的两个点若同色，则异色小线段的条数或者增加2条（相邻的两个点同为红色），或者减少2条（相邻的两个点同为蓝色）；这个改变颜色的点的左右两侧相邻的两个点若异色，则异色小线段的条数不变。
综上所述，改变任意个点的颜色，异色线段的条数的改变总是一个偶数，从而异色线段的条数是一个奇数。
【例50】在6×6的正方形网格中，把部分小方格涂成红色。然后任意划掉3行和3列，使得剩下的小方格中至少有1个是红色的。那么，总共至少要涂红多少小方格？
【解析】先考虑每行每列都有一格涂红，比较方便的涂法是在一条对角线上涂6格红色的，如图1。
任意划掉3行3列，可以设想划行划列的原则是：每次划掉红格的个数越多越好。对于图1，划掉3行去掉3个红格，还有3个红格恰在3列中，再划掉3列就不存在红格了。
所以，必然有一些行有一些列要涂2个红格，为了尽可能地少涂红格，那么每涂一格红色的，一定要使多出一行同时也多出一列有两格红色的。
先考虑有3行中有2格涂红，如图2。显然，同时也必然有3个列中也有2格涂红。这时，我们可以先划掉有2格红色的3行，还剩下3行，每行上只有一格涂红，每列上也只有一格涂红，那么在划掉带红格的3列就没有红格了。
为了使得至少余下一个红格，只要再涂一格。此红格要使图中再增加一行和一列有两个红格的，如图3。
结论是：至少需要涂红10个方格。
【例51】在n×n（n≥3）方格表中，任意选出n－1个方格都涂成黑色，然后将那些至少与两个已涂色的方格相邻的方格也都涂黑. 求证：不论怎样选择最初的n－1个方格，都不能按这样的法则，将表中的所有方格全涂黑。
【解析】设每个小方格的边长为1，考察黑方格区域的边界长度L。开始时，由于只有n－1个方格，∴L≤4（n－1）。在以后的涂色过程中，尽管黑方格的总体面积增加了，但其周长不变，即仍有L≤4（n－1）。如果要填满n×n的方格，就有L=4n，显然发生矛盾。命题得证。
注变与不变是数学中永恒的主体，本题抓住变化中周长这个不变量是证明的关键
【例52】平面直角坐标系中，纵横坐标都是整数的点称为整点称为整点。设计一种方法，将所有整点涂色，每一个整点染成白色、红色或黑色中的一种颜色，使得
（1）每一种颜色的点出现在无穷多条平行于横轴的直线上；
（2）对任意白点A、红点B及黑点C，总可以找到一个红点D，使得ABCD为一平行四边形。证明你设计的的方法符合上述要求。
【解析】将y轴上的整点染上黑色或白色，并且黑、白各有无穷多个（例如黑、白相间）。再将其余整点都染上红色，则这样的染色满足题设要求。
证明：不难看出到上述设计，白色点、黑色点、红色点出现在无穷多条平行于横轴的直线上，故满足条件（1）。
设A为白点，B为红点，C为黑点，显然B不在y轴上，即B不在AC上，而且□ABCD顶点D 的横（纵）坐标，所以D一定是整点。由于A，C横坐标为0，B横坐标不为0，所以D的横坐标不为0，即D为红点。满足条件（2）。
注本题为全国联赛二试问题，这种构造问题的答案总是很多，本题至少有四五种构造方法
【例53】设平面上任一点都染上红、蓝、黄三色中的一种，求证：一定存在一条端点同色且长度为1
的线段。
【解析】在平面上作有公共底边BD且边长为1的两个正△ABD和△BCD（如图01—09）。如果这五条线段有一条满足要则证毕。
否则，只有A、C同色。这时，将这两个正三角绕A旋转，使C到达F处，且|CF|=1。如果在两个正△AEG和△EFG的五边中有一条满足要求，问题也就得证，否则只有A、F同色，从而C，F同角且|CF|=1。证毕。
注本题先用涂色观点，实际上是用反证法证得A，C同色是最困难的问题，又用旋转的变换，构造了长为
1且同色的线段CF.这是组合几何中的经典问题
【例54】平面上有6点，任何三点都是一个不等边三角形的顶点，求证：这些三角形的边中一定有一条，它在一个三角形中是最长边，而在另一个三角形中是最短边.
【解析】将所有以P1，P2，…，P6中的三个为顶点的三角形，最短边都涂成红色。
如果从P1出发，所连的五条线有三条是红的，不妨设P1P2，P1P3，P1P4涂红色，在△P2P3P4必有一条是红色，又不妨设P2P3涂红色，则△P1P2P3三边均涂红色，且其中必有一条最长边，这条边即为所求。
如果从P1出发至少有三条未涂色，不妨设P1P2，P1P3，P1P4，∵△P1P2P3，△P1P2P4，△P1P3P4每个三角形至少有一边涂红色，于是△P2P3P4是红色三角形，此即符合要求。
综上所述，知命题成立。
【例55】用任意方式给平面上的每一个点染上黑色或白色.求证：一定存在一个边长为1或的正三角形，它三个顶点是同色的.
【解析】先利用下图（AB=2,C为中点，且A,C同色，图中有三个正三角形）证明＂若平面上有两个异色的点距离为２，那么必定可以找到符合题意的三角形＂．只需再找长为２端点异色的线
段．以Ｏ（白色）为圆心，４为半径作圆．如圆内皆白点，问题已证．否则圆内有一黑点Ｐ，以ＯＰ为底作腰长为２的三角形ＯＰＲ，则Ｒ至少与Ｏ、Ｐ中一点异色，这样的线段找到．
注本题为首届全国数学冬令营试题
板块二操作问题
【例56】有1987块玻璃片，每块上涂有红、黄、蓝三色之一，进行下列操作：将不同颜色的两块玻璃片擦净，然后涂上第三种颜色。
（1）求证：无论开始时红、黄、蓝色玻璃片各有多少块，总可以经过有限次操作而使所有的玻璃片涂有同一种颜色；
（2）求证：玻璃片最后变成哪种颜色，与操作顺序无关。
【解析】设红、黄、蓝玻璃片各有x，y，z块，则x，y，z被3除后余数中必有两个相等（否则x+y+z=1987是3的倍数）。
令x=3a+m，y=3b+n，z=3c+n，并设c≥b。
若c=b，结论显然成立；若c>b，可取黄、蓝各3b+n块，全变成红色，黄片为0，蓝片为3（c－b）块。
再取红、蓝各1块，产生黄片2块；再取蓝、黄各两片（∵c>b，∴3（c－b）≥3），产生红片4块，这时蓝片有[3（c－b）－1] －2=3（c－b－1）块。如果有c－b－1=0，则命题获证。如果c－b－1≠0，依次反复上述步骤，达到c－b－k=0为此（k∈N），最后全变成了红色。
由上面的过程可知，三个数除以3所得的余数中，两个相同的余数的玻璃片，最后都变成了另一个余数不同的玻璃片的颜色。因此，与操作顺序无关。
注本题充分注意到1987不是3的倍数，因而由抽屉原理得知x，y，z被3除后余数中必有两个相同，根据这一特征，还可以推广问题的结论。这是一种与整除有关的涂色问题。将1987改为2010或3n都仍然成立
【例57】（1）在黑板上写上1，2，3，…，1998。按下列规定进行“操作”：每次擦去其中的任意两个数
a和b，然后写上它们的差（大减小），直到黑板上剩下一个数为止。问：黑板上剩下的数是奇数还是偶数？为什么？
（2）有三堆石子，每堆分别有1998，998，98粒。现在对这三堆石子进行如下的“操作”：每次允许从每堆中各拿掉一个或相同个数的石子，或从任一堆中取出一些石子放入另一堆中。
按上述方式进行“操作”，能否把这三堆石子都取光？如行，请设计一种取石子的方案；如不行，请说
1 第三章 函数 一、基础知识 定义1 映射，对于任意两个集合A ，B ，依对应法则f ，若对A 中的任意一个元素x ，在B 中都有唯一一个元素与之对应，则称f : A →B 为一个映射。 定义2 单射，若f : A →B 是一个映射且对任意x , y ∈A , x ≠y , 都有f (x )≠f (y )则称之为单射。 定义3 满射，若f : A →B 是映射且对任意y ∈B ，都有一个x ∈A 使得f (x )=y ，则称f : A →B 是A 到B 上的满射。 定义4 一一映射，若f : A →B 既是单射又是满射，则叫做一一映射，只有一一映射存在逆映射，即从B 到A 由相反的对应法则f -1构成的映射，记作f -1: A →B 。 定义5 函数，映射f : A →B 中，若A ，B 都是非空数集，则这个映射为函数。A 称为它的定义域，若x ∈A , y ∈B ，且f (x )=y （即x 对应B 中的y ），则y 叫做x 的象，x 叫y 的原象。集合{f (x )|x ∈A }叫函数的值域。通常函数由解析式给出，此时函数定义域就是使解析式有意义的未知数的取值范围，如函数y =3x -1的定义域为{x |x ≥0,x ∈R}. 定义6 反函数，若函数f : A →B （通常记作y =f (x )）是一一映射，则它的逆映射f -1: A →B 叫原函数的反函数，通常写作y =f -1(x ). 这里求反函数的过程是：在解析式y =f (x )中反解x 得x =f -1(y )，然后将x , y 互换得y =f -1(x )，最后指出反函数的定义域即原函数的值域。例如：函数y =x -11的反函数是y =1-x 1(x ≠0). 定理1 互为反函数的两个函数的图象关于直线y =x 对称。 定理2 在定义域上为增（减）函数的函数，其反函数必为增（减）函数。 定义7 函数的性质。 （1）单调性：设函数f (x )在区间I 上满足对任意的x 1, x 2∈I 并且x 1< x 2，总有f (x 1)
九年级讲义目录
专题01 二次根式的化简与求值 阅读与思考 二次根式的化简与求值问题常涉及最简根式、同类根式，分母有理化等概念，常用到分解、分拆、换元等技巧. 有条件的二次根式的化简与求值问题是代数变形的重点，也是难点，这类问题包含了整式、分式、二次根式等众多知识，又联系着分解变形、整体代换、一般化等重要的思想方法，解题的基本思路是： 1、直接代入 直接将已知条件代入待化简求值的式子. 2、变形代入 适当地变条件、适当地变结论，同时变条件与结论，再代入求值. 数学思想： 数学中充满了矛盾，如正与负，加与减，乘与除，数与形，有理数与无理数，常量与变量、有理式与无理式，相等与不等，正面与反面、有限与无限，分解与合并，特殊与一般，存在与不存在等，数学就是在矛盾中产生，又在矛盾中发展. =x , y , n 都是正整数） 例题与求解 【例1】 当x = 时，代数式32003 (420052001)x x --的值是（ ） A 、0 B 、－1 C 、1 D 、2003 2- （绍兴市竞赛试题） 【例2】 化简 （1(b a b ab b -÷-- （黄冈市中考试题） （2 （五城市联赛试题）
（3 （北京市竞赛试题） （4 （陕西省竞赛试题） 解题思路：若一开始把分母有理化，则计算必定繁难，仔细观察每题中分子与分母的数字特点，通过分解、分析等方法寻找它们的联系，问题便迎刃而解. 思想精髓：因式分解是针对多项式而言的，在整式，分母中应用非常广泛，但是因式分解的思想也广泛应用于解二次根式的问题中，恰当地作类似于因式分解的变形，可降低一些二次根式问题的难度. 【例3】比6大的最小整数是多少？ （西安交大少年班入学试题） 解题思路：直接展开，计算较繁，可引入有理化因式辅助解题，即设x y == 想一想：设x=求 432 32 621823 7515 x x x x x x x --++ -++ 的值. （“祖冲之杯”邀请赛试题） 的根式为复合二次根式，常用配方，引入参数等方法来化简复合二次根式.
1 复数 一、基础知识 1．复数的定义：设i 为方程x 2=-1的根，i 称为虚数单位，由i 与实数进行加、减、乘、除 等运算。便产生形如a+bi （a,b ∈R ）的数，称为复数。所有复数构成的集合称复数集。通常用C 来表示。 2．复数的几种形式。对任意复数z=a+bi （a,b ∈R ），a 称实部记作Re(z),b 称虚部记作Im(z). z=ai 称为代数形式，它由实部、虚部两部分构成；若将(a,b)作为坐标平面内点的坐标，那么z 与坐标平面唯一一个点相对应，从而可以建立复数集与坐标平面内所有的点构成的集合之间的一一映射。因此复数可以用点来表示，表示复数的平面称为复平面，x 轴称为实轴，y 轴去掉原点称为虚轴，点称为复数的几何形式；如果将(a,b)作为向量的坐标，复数z 又对应唯一一个向量。因此坐标平面内的向量也是复数的一种表示形式，称为向量形式；另外设z 对应复平面内的点Z ，见图15-1，连接OZ ，设∠xOZ=θ,|OZ|=r ，则a=rcos θ,b=rsin θ,所以z=r(cos θ+isin θ)，这种形式叫做三角形式。若z=r(cos θ+isin θ)，则θ称为z 的辐角。若0≤θ<2π，则θ称为z 的辐角主值，记作θ=Arg(z). r 称为z 的模，也记作|z|，由勾股定理知|z|=2 2b a +.如果用e i θ表示cos θ+isin θ，则z=re i θ，称为复数的指数形式。 3．共轭与模，若z=a+bi ，（a,b ∈R ）,则=z a-bi 称为z 的共轭复数。模与共轭的性质有： （1）2121z z z z ±=±；（2）2121z z z z ?=?；（3）2||z z z =?；（4）2121z z z z =???? ??；（5）||||||2121z z z z ?=?；（6）|||||| 2121z z z z =；（7）||z 1|-|z 2||≤|z 1±z 2|≤|z 1|+|z 2|；（8）|z 1+z 2|2+|z 1-z 2|2=2|z 1|2+2|z 2|2；（9）若|z|=1，则z z 1=。 4．复数的运算法则：（1）按代数形式运算加、减、乘、除运算法则与实数范围内一致，运算结果可以通过乘以共轭复数将分母分为实数；（2）按向量形式，加、减法满足平行四边形和三角形法则；（3）按三角形式，若z 1=r 1(cos θ1+isin θ1), z 2=r 2(cos θ2+isin θ2)，则z 1??z 2=r 1r 2[cos(θ1+θ2)+isin(θ1+θ2)]；若2 1212,0r r z z z =≠[cos(θ1-θ2)+isin(θ1-θ2)]，用指数形式记为z 1z 2=r 1r 2e i(θ1+θ2),.)(2 12121θθ-=i e r r z z 5.棣莫弗定理：[r(cos θ+isin θ)]n =r n (cosn θ+isinn θ). 6.开方：若=n w r(cos θ+isin θ)，则)2s i n 2(c o s n k i n k r w n πθπθ+++=，k=0,1,2,…,n-1。 7．单位根：若w n =1，则称w 为1的一个n 次单位根，简称单位根，记Z 1=n i n ππ2sin 2cos +，则全部单位根可表示为1,1Z ,1121,,-n Z Z .单位根的基本性质有（这里记k k Z Z 1=，
§23抽屉原理 在数学问题中有一类与“存在性”有关的问题，例如：“13个人中至少有两个人出生在相同月份”；“某校400名学生中，一定存在两名学生，他们在同一天过生日”；“2003个人任意分成200个小组，一定存在一组，其成员数不少于11”；“把[0，1]内的全部有理数放到100个集合中，一定存在一个集合，它里面有无限多个有理数”。这类存在性问题中，“存在”的含义是“至少有一个”。在解决这类问题时，只要求指明存在，一般并不需要指出哪一个，也不需要确定通过什么方式把这个存在的东西找出来。这类问题相对来说涉及到的运算较少，依据的理论也不复杂，我们把这些理论称之为“抽屉原理”。 “抽屉原理”最先是由19世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问题的，所以又称“迪里赫莱原理”，也有称“鸽巢原理”的。这个原理可以简单地叙述为“把10个苹果，任意分放在9个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的，但应用它却可以解决许多有趣的问题，并且常常得到一些令人惊异的结果。抽屉原理是国际国内各级各类数学竞赛中的重要内容，本讲就来学习它的有关知识及其应用。 （一）抽屉原理的基本形式 定理1、如果把n+1个元素分成n个集合，那么不管怎么分，都存在一个集合，其中至少有两个元素。 证明：（用反证法）若不存在至少有两个元素的集合，则每个集合至多1个元素，从而n 个集合至多有n个元素，此与共有n+1个元素矛盾，故命题成立。 在定理1的叙述中，可以把“元素”改为“物件”，把“集合”改成“抽屉”，抽屉原理正是由此得名。 同样，可以把“元素”改成“鸽子”，把“分成n个集合”改成“飞进n个鸽笼中”。“鸽笼原理”由此得名。 例题讲解 1．已知在边长为1的等边三角形内（包括边界）有任意五个点（图1）。证明：至少有两个点之间的距离不大于 2．从1-100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个是另一个的整数倍。
第十三章 排列组合与概率 一、基础知识 1．加法原理：做一件事有n 类办法，在第1类办法中有m 1种不同的方法，在第2类办法中有m 2种不同的方法，……，在第n 类办法中有m n 种不同的方法，那么完成这件事一共有N=m 1+m 2+…+m n 种不同的方法。2 乘法原理：做一件事，完成它需要分n 个步骤，第1步有m 1种不同的方法，第2步有m 2种不同的方法，……，第n 步有m n 种不同的方法，那么完成这件事共有N=m 1×m 2×…×m n 种不同的方法。3．排列与排列数：从n 个不同元素中，任取m(m ≤n)个元素，按照一定顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列，从n 个不同元素中取出m 个(m ≤n)元素的所有排列个数，叫做从n 个不同元素中取出m 个元素的排列数，用m n A 表示，m n A =n(n-1)…(n-m+1)= )! (! m n n -,其中m,n ∈N,m ≤n, 注：一般地0 n A =1，0！=1，n n A =n!。 4．N 个不同元素的圆周排列数为n A n n =(n-1)!。 5．组合与组合数：一般地，从n 个不同元素中，任取m(m ≤n)个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合，即从n 个不同元素中不计顺序地取出m 个构成原集合的一个子集。从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数，用m n C 表示： .)! (!! !)1()1(m n m n m m n n n C m n -=+--= 6．组合数的基本性质：（1）m n n m n C C -=；（2）1 1--+=n n m n m n C C C ；（3） k n k n C C k n =--11；（4）n n k k n n n n n C C C C 20 10==+++∑= ；（5）111++++-=+++k m k k m k k k k k C C C C ；（6） k n m n m k k n C C C --=。 7．定理1：不定方程x 1+x 2+…+x n =r 的正整数解的个数为1 1--n r C 。
初中数学竞赛公益讲座：平行四边形和梯形 2018/4/7 一、基础知识： 1）平行四边形：平移、中点、中心对称（旋转180度）2）特殊的平行四边形：矩形、菱形、正方形 3）梯形：梯形问题转化、分割、拼接 三角形或者平行四边形问题 二、例题分析 例1、如下左图，在等腰△ABC中，延长边AB到点D，延长边CA到点E，连 接DE，恰有AD=BC=CE=DE，求∠BAC的度数。 例2、如上右图，在RT△ABC中，∠ACB是直角，CD⊥AB于D，AE平分∠ABC，交CD于K，F在BE上且BF=CE，求证：FK?AB。 例3、如下左图，△ABC内部一点P，满足∠PBA=∠PCA，作平行四边形PBQC，求证：∠QAB=∠PAC。
例4、如上右图，已知A、B是两个定点，C是位于直线AB某一侧的一个动点，分别以AC、BC为边，在△ABCDE外部作正方形CADI、CBEF，求证无论C点 在什么位置上，DE的中点M的位置不变。 例5、如下左图，梯形ABCD中，AB?CD，BC⊥CD，AB=2，CD=4，点E是BC上的一个动点，连接并延长EA到点F，使得EF:AE=2:1，连接并延长ED到点G，使得EG:ED=3:2，以EF和EG为临边作平行四边形EFHG，连接EH交AD于点P，1）求EH的最小长度；2）求证：P是定点。 例6、如上右图，四边形ABCD中，点E、F分别在边AB、CD上，连接BF、CE交于点P，连接AF、DE交于点Q，若四边形EQFP是平行四边形，求证： 四边形ABCD是梯形。 例7、如下图，等腰梯形ABCD，对角线AC与BD交于点O，M 、N分别为腰AB和CD上的点，且AM=CN，连接MN分别交BD、AC于点P、Q，求证： MP=QN。
第五章 数列 一、基础知识 定义1 数列，按顺序给出的一列数，例如1，2，3，…，n ，…. 数列分有穷数列和无穷数列两种，数列{a n }的一般形式通常记作a 1, a 2, a 3,…，a n 或a 1, a 2, a 3,…，a n …。其中a 1叫做数列的首项，a n 是关于n 的具体表达式，称为数列的通项。 定理1 若S n 表示{a n }的前n 项和，则S 1=a 1, 当n >1时，a n =S n -S n -1. 定义2 等差数列，如果对任意的正整数n ，都有a n +1-a n =d （常数），则{a n }称为等差数列，d 叫做公差。若三个数a , b , c 成等差数列，即2b =a +c ，则称b 为a 和c 的等差中项，若公差为d, 则a =b -d, c =b +d. 定理2 等差数列的性质：1）通项公式a n =a 1+(n -1)d ；2）前n 项和公式： S n =d n n na a a n n 2 )1(2)(11-+=+；3）a n -a m =(n -m)d ，其中n , m 为正整数；4）若n +m=p +q ，则a n +a m =a p +a q ；5）对任意正整数p , q ，恒有a p -a q =(p -q )(a 2-a 1)；6）若A ，B 至少有一个不为零，则{a n }是等差数列的充要条件是S n =An 2+Bn . 定义3 等比数列，若对任意的正整数n ，都有 q a a n n =+1，则{a n }称为等比数列，q 叫做公比。 定理3 等比数列的性质：1）a n =a 1q n -1 ；2）前n 项和S n ，当q ≠1时，S n =q q a n --1)1(1；当q =1时，S n =na 1；3）如果a , b , c 成等比数列，即b 2=ac (b ≠0)，则b 叫做a , c 的等比中项；4）若m+n =p +q ，则a m a n =a p a q 。 定义4 极限，给定数列{a n }和实数A ，若对任意的ε>0，存在M ，对任意的n >M(n ∈N ),都有|a n -A |<ε，则称A 为n →+∞时数列{a n }的极限，记作.lim A a n n =∞ → 定义5 无穷递缩等比数列，若等比数列{a n }的公比q 满足|q |<1，则称之为无穷递增等比数列，其前n 项和S n 的极限（即其所有项的和）为q a -11（由极限的定义可得）。 定理3 第一数学归纳法：给定命题p (n )，若：（1）p (n 0)成立；（2）当p (n )时n =k 成立时能推出p (n )对n =k +1成立，则由（1），（2）可得命题p (n )对一切自然数n ≥n 0成立。 竞赛常用定理 定理4 第二数学归纳法：给定命题p (n )，若：（1）p (n 0)成立；（2）当p (n )对一切n ≤k 的自然数n 都成立时（k ≥n 0）可推出p (k +1)成立，则由（1），（2）可得命题p (n )对一切自然数n ≥n 0成立。 定理5 对于齐次二阶线性递归数列x n =ax n -1+bx n -2，设它的特征方程x 2=ax +b 的两个根为α,β:(1)若α≠β，则x n =c 1a n -1+c 2βn -1，其中c 1, c 2由初始条件x 1, x 2的值确定；(2)若α=β，则x n =(c 1n +c 2) αn -1，其中c 1, c 2的值由x 1, x 2的值确定。 二、方法与例题 1．不完全归纳法。 这种方法是从特殊情况出发去总结更一般的规律，当然结论未必都是正确的，但却是人类探索未知世界的普遍方式。通常解题方式为：特殊→猜想→数学归纳法证明。 例1 试给出以下几个数列的通项（不要求证明）；1）0，3，8，15，24，35，…；2）1，5，19，65，…；3）-1，0，3，8，15，…。 【解】1）a n =n 2-1；2）a n =3n -2n ；3）a n =n 2-2n . 例2 已知数列{a n }满足a 1= 21,a 1+a 2+…+a n =n 2a n , n ≥1，求通项a n . 【解】 因为a 1= 2 1,又a 1+a 2=22·a 2,
数列 一、基础知识 定义1 数列，按顺序给出的一列数，例如1，2，3，…，n ，…. 数列分有穷数列和无穷数列两种，数列{a n }的一般形式通常记作a 1, a 2, a 3,…，a n 或a 1, a 2, a 3,…，a n …。其中a 1叫做数列的首项，a n 是关于n 的具体表达式，称为数列的通项。 定理1 若S n 表示{a n }的前n 项和，则S 1=a 1, 当n >1时，a n =S n -S n -1. 定义2 等差数列，如果对任意的正整数n ，都有a n +1-a n =d （常数），则{a n }称为等差数列，d 叫做公差。若三个数a , b , c 成等差数列，即2b =a +c ，则称b 为a 和c 的等差中项，若公差为d, 则a =b -d, c =b +d. 定理2 等差数列的性质：1）通项公式a n =a 1+(n -1)d ；2）前n 项和公式： S n =d n n na a a n n 2 )1(2)(11-+=+；3）a n -a m =(n -m)d ，其中n , m 为正整数；4）若n +m=p +q ，则a n +a m =a p +a q ；5）对任意正整数p , q ，恒有a p -a q =(p -q )(a 2-a 1)；6）若A ，B 至少有一个不为零，则{a n }是等差数列的充要条件是S n =An 2+Bn . 定义3 等比数列，若对任意的正整数n ，都有 q a a n n =+1，则{a n }称为等比数列，q 叫做公比。 定理3 等比数列的性质：1）a n =a 1q n -1 ；2）前n 项和S n ，当q ≠1时，S n =q q a n --1)1(1；当q =1时，S n =na 1；3）如果a , b , c 成等比数列，即b 2=ac (b ≠0)，则b 叫做a , c 的等比中项；4）若m+n =p +q ，则a m a n =a p a q 。 定义4 极限，给定数列{a n }和实数A ，若对任意的ε>0，存在M ，对任意的n >M(n ∈N ),都有|a n -A |<ε，则称A 为n →+∞时数列{a n }的极限，记作.lim A a n n =∞ → 定义5 无穷递缩等比数列，若等比数列{a n }的公比q 满足|q |<1，则称之为无穷递增等比数列，其前n 项和S n 的极限（即其所有项的和）为q a -11（由极限的定义可得）。 定理3 第一数学归纳法：给定命题p (n )，若：（1）p (n 0)成立；（2）当p (n )时n =k 成立时能推出p (n )对n =k +1成立，则由（1），（2）可得命题p (n )对一切自然数n ≥n 0成立。 竞赛常用定理 定理4 第二数学归纳法：给定命题p (n )，若：（1）p (n 0)成立；（2）当p (n )对一切n ≤k 的自然数n 都成立时（k ≥n 0）可推出p (k +1)成立，则由（1），（2）可得命题p (n )对一切自然数n ≥n 0成立。 定理5 对于齐次二阶线性递归数列x n =ax n -1+bx n -2，设它的特征方程x 2=ax +b 的两个根为α,β:(1)若α≠β，则x n =c 1a n -1+c 2βn -1，其中c 1, c 2由初始条件x 1, x 2的值确定；(2)若α=β，则x n =(c 1n +c 2) αn -1，其中c 1, c 2的值由x 1, x 2的值确定。 二、方法与例题 1．不完全归纳法。 这种方法是从特殊情况出发去总结更一般的规律，当然结论未必都是正确的，但却是人类探索未知世界的普遍方式。通常解题方式为：特殊→猜想→数学归纳法证明。 例1 试给出以下几个数列的通项（不要求证明）；1）0，3，8，15，24，35，…；2）1，5，19，65，…；3）-1，0，3，8，15，…。 【解】1）a n =n 2-1；2）a n =3n -2n ；3）a n =n 2-2n . 例2 已知数列{a n }满足a 1= 21,a 1+a 2+…+a n =n 2a n , n ≥1，求通项a n . 【解】 因为a 1= 2 1,又a 1+a 2=22·a 2,
专业资料 初中数学竞赛辅导讲义（初三） 第一讲 分式的运算 [知识点击] 1、 分部分式：真分式化为另几个真分式的和，一般先将分母分解因式，后用待定系数法进行。 2、 综合除法：多项式除以多项式可类似于是有理数的除法运算，可列竖式来进行。 3、 分式运算：实质就是分式的通分与约分。 [例题选讲] 例1．化简 2312++x x + 6512++x x + 12 712++x x 解：原式= )2)(1(1++x x + )3)(2(1++x x + ) 4)(3(1++x x = 11+x - 21+x + 21+x - 31+x + 31+x - 4 1+x =) 4)(1(3++x x 例2． 已知 z z y x -+ = y z y x +- = x z y x ++- ，且xyz ≠0，求分式xyz x z z y y x ))()((+-+的值。
专业资料 解：易知：z y x + = y z x + = x z y + =ｋ 则?? ???=+=+=+)3()2()1(kx z y ky z x kz y x （1）+（2）+（3）得：(ｋ-2)(x+y+z)=0 ｋ=2 或 x+y+z=0 若ｋ=2则原式= k 3 = 8 若 ｘ+ｙ+ｚ=0，则原式= k 3 =-1 例3．设 1 2+-mx x x =1，求 12242+-x m x x 的值。 解：显然X 0≠，由已知x mx x 12+- =1 ，则 x +x 1 = ｍ + 1 ∴ 22241x x m x +- = ｘ2 + 21x - ｍ2= (x +x 1)2-2 –ｍ2 =( ｍ +1)2-2- ｍ2= 2ｍ -1 ∴原式=1 21-m 例4．已知多项式3x 3 +ax 2 +3x +1 能被x 2 +1整除，求ａ的值。 解：
（共30套）初中数学竞赛辅导讲义及习题解答大全适合中学教师作为辅导教材使用
第一讲 走进追问求根公式 形如02=++c bx ax （0≠a ）的方程叫一元二次方程，配方法、公式法、因式分解法是解一元二次方程的基本方法. 而公式法是解一元二次方程的最普遍、最具有一般性的方法. 求根公式a ac b b x 2422 ,1-±-= 内涵丰富：它包含了初中阶段已学过的全部代数运算；它回答了一元二次方程的诸如怎样求实根、实根的个数、何时有实根等基本问题；它展示了数学的简洁美. 降次转化是解方程的基本思想，有些条件中含有(或可转化为)一元二次方程相关的问题，直接求解可能给解题带来许多不便，往往不是去解这个二次方程，而是对方程进行适当的变形来代换，从而使问题易于解决. 解题时常用到变形降次、整体代入、构造零值多项式等技巧与方法. 【例题求解】 【例1】满足1)1(22=--+n n n 的整数n 有 个. 思路点拨：从指数运算律、±1的特征人手，将问题转化为解方程. 【例2】设1x 、2x 是二次方程032=-+x x 的两个根，那么1942231+-x x 的值等于（ ） A 、一4 B 、8 C 、6 D 、0 思路点拨：求出1x 、2x 的值再代入计算，则计算繁难，解题的关键是利用根的定义及变形，使多项式降次，如1213x x -=，2223x x -=. 【例3】 解关于x 的方程02)1(2=+--a ax x a . 思路点拨：因不知晓原方程的类型，故需分01=-a 及01≠-a 两种情况讨论. 【例4】 设方程04122=---x x ，求满足该方程的所有根之和. 思路点拨：通过讨论，脱去绝对值符号，把绝对值方程转化为一般的一元二次方程求解. 【例5】 已知实数a 、b 、c 、d 互不相等，且x a d d c c b b a =+=+=+=+ 1 111， 试求x 的值. 思路点拨：运用连等式，通过迭代把b 、c 、d 用a 的代数式表示，由解方程求得x 的值. 注：一元二次方程常见的变形形式有： (1)把方程02=++c bx ax （0≠a ）直接作零值多项式代换； (2)把方程02=++c bx ax （0≠a ）变形为c bx ax --=2，代换后降次； (3)把方程02=++c bx ax （0≠a ）变形为c bx ax -=+2或bx c ax -=+2，代换后使之转化关系或整体地消去x . 解合字母系数方程02=++c bx ax 时，在未指明方程类型时，应分0=a 及0≠a 两种情况讨论；解绝对值方程需脱去绝对值符号，并用到绝对值一些性质，如222 x x x ==.
第三章 函数 一、基础知识 定义1 映射，对于任意两个集合A ，B ，依对应法则f ，若对A 中的任意一个元素x ，在B 中都有唯一一个元素与之对应，则称f : A →B 为一个映射． 定义2 单射，若f : A →B 是一个映射且对任意x ， y ∈A ， x ≠y ， 都有f (x )≠f (y )则称之为单射． 定义3 满射，若f : A →B 是映射且对任意y ∈B ，都有一个x ∈A 使得f (x )=y ，则称f : A →B 是A 到B 上的满射． 定义4 一一映射，若f : A →B 既是单射又是满射，则叫做一一映射，只有一一映射存在逆 映射，即从B 到A 由相反的对应法则f -1构成的映射，记作f -1 : A →B ． 定义5 函数，映射f : A →B 中，若A ，B 都是非空数集，则这个映射为函数．A 称为它的定义域，若x ∈A ， y ∈B ，且f (x )=y （即x 对应B 中的y 则y 叫做x 的象，x 叫y 的原象．集合{f (x )|x ∈A }叫函数的值域．通常函数由解析式给出，此时函数定义域就是使解析式有意义的未知数的取值范围，如函数y =3x -1的定义域为{x |x ≥0，x ∈R}. 定义6 反函数，若函数f : A →B （通常记作y =f (x )）是一一映射，则它的逆映射f -1 : A →B 叫原函数的反函数，通常写作y =f -1(x ). 这里求反函数的过程是：在解析式y =f (x )中反解x 得x =f -1(y )，然后将x ， y 互换得y =f -1(x )，最后指出反函数的定义域即原函数的值域．例如：函数y = x -11的反函数是y =1-x 1 (x ≠0). 定理1 互为反函数的两个函数的图象关于直线y =x 对称． 定理2 在定义域上为增（减）函数的函数，其反函数必为增（减）函数． 定义7 函数的性质． （1）单调性：设函数f (x )在区间I 上满足对任意的x 1， x 2∈I 并且x 1< x 2，总有 f (x 1)
2020年初中数学竞赛讲义：逻辑推 理 一、逻辑推理 (1) 第1 页共2 页
第 1 页 共 2 页 一、 逻辑推理 1. （1992年全国初中数学联赛2试）某个信封上的两个邮政编码M 和N 均由0， 1，2，3，5，6这六个不同数字组成，现有四个编码如下： A ．320651 B ．105263 C ．612305 D ．316250 已知编码A ，B ，C ，D 各恰有两个数字的位置与M 和N 相同．D 恰有三个数字的位置与M 和N 相同．试求：M 和N ． 【难度】 ★★★ 【解析】 对于编码M ，考虑编码A 中恰有两个数位上的数字与M 中相应数位上的数字相 同．设这两位是1x ，2x 数位．由于B ，C 中该两数位上的数字均与A 在这两数位上的数字不同，因此，B ，C 中这两位数上的数字必与M 中这两数位上的数字不同，于是B 中与M 中数字相同的数位必异于1x ，2x ．不妨设为3x ，4x ；同理C 中与M 中数字相同的数位只能是异于1x ，2x ，3x ，4x 的5x ，6x 两位．关于N 也有类似的结论．这就是说，在每个数位上，A ，B ，C 分别在该数位上的数字中，必有一个与M 在该数位上的数字相同；同样地，也必有一个与N 在该数位上的数字相同． 由此知，D 中的6，0两数字必不是M ，N 在相应数位上的数字，于是D 的3，1，2，5中只有一个数字与M 在相应数位上的数字不同，与N 相比较她有类似的结果． ⑴若3不对，则有610253，013256 ⑵若1不对，则有360251，301256 ⑶若2不对，则有312056，310652 ⑷若5不对，则有310265，315206 经检验知：该信封上编码M ，N 或者同为610253，或者同为310265．或者一个是610253，另一个是310265．
第一讲 走进追问求根公式 形如02=++c bx ax （0≠a ）的方程叫一元二次方程，配方法、公式法、因式分解法是解一元二次方程的基本方法。而公式法是解一元二次方程的最普遍、最具有一般性的方法。 求根公式a ac b b x 2422,1-±-=内涵丰富：它包含了初中阶段已学过的全部代数运算；它回答了一元二次方程的诸如怎样求实根、实根的个数、何时有实根等基本问题；它展示了数学的简洁美。 降次转化是解方程的基本思想，有些条件中含有(或可转化为)一元二次方程相关的问题，直接求解可能给解题带来许多不便，往往不是去解这个二次方程，而是对方程进行适当的变形来代换，从而使问题易于解决。解题时常用到变形降次、整体代入、构造零值多项式等技巧与方法。 【例题求解】 【例1】满足1)1(22=--+n n n 的整数n 有 个。 思路点拨：从指数运算律、±1的特征人手，将问题转化为解方程。 【例2】设1x 、2x 是二次方程032=-+x x 的两个根，那么1942231+-x x 的值等于（ ） A 、一4 B 、8 C 、6 D 、0 思路点拨：求出1x 、2x 的值再代入计算，则计算繁难，解题的关键是利用根的定义及变形，使多项式降次，如1213x x -=，2223x x -=。 【例3】 解关于x 的方程02)1(2=+--a ax x a 。 思路点拨：因不知晓原方程的类型，故需分01=-a 及01≠-a 两种情况讨论。 【例4】 设方程04122=---x x ，求满足该方程的所有根之和。 思路点拨：通过讨论，脱去绝对值符号，把绝对值方程转化为一般的一元二次方程求解。 【例5】 已知实数a 、b 、c 、d 互不相等，且x a d d c c b b a =+=+=+=+1111， 试求x 的值。 思路点拨：运用连等式，通过迭代把b 、c 、d 用a 的代数式表示，由解方程求得x 的值。 注：一元二次方程常见的变形形式有： (1)把方程02=++c bx ax （0≠a ）直接作零值多项式代换； (2)把方程02=++c bx ax （0≠a ）变形为c bx ax --=2，代换后降次； (3)把方程02=++c bx ax （0≠a ）变形为c bx ax -=+2或bx c ax -=+2，代换后使之转化关系或整体地消去x 。 解合字母系数方程02=++c bx ax 时，在未指明方程类型时，应分0=a 及0≠a 两种情况讨论；解绝对值方程需脱去绝对值符号，并用到绝对值一些性质，如222 x x x ==。
高中数学竞赛标准讲义----排列组合与概率 一、基础知识 1．加法原理：做一件事有n 类办法，在第1类办法中有m 1种不同的方法，在第2类办法中有m 2种不同的方法，……，在第n 类办法中有m n 种不同的方法，那么完成这件事一共有N=m 1+m 2+…+m n 种不同的方法。 2．乘法原理：做一件事，完成它需要分n 个步骤，第1步有m 1种不同的方法，第2步有m 2种不同的方法，……，第n 步有m n 种不同的方法，那么完成这件事共有N=m 1×m 2×…×m n 种不同的方法。 3．排列与排列数：从n 个不同元素中，任取m(m ≤n)个元素，按照一定顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列，从n 个不同元素中取出m 个(m ≤n)元素的所有排列个数，叫做从n 个不同元素中取出m 个元素的排列数，用m n A 表示，m n A =n(n-1)…(n-m+1)= )! (! m n n -,其中m,n ∈N,m ≤n, 注：一般地0n A =1，0！=1，n n A =n!。 4．N 个不同元素的圆周排列数为n A n n =(n-1)!。 5．组合与组合数：一般地，从n 个不同元素中，任取m(m ≤n)个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合，即从n 个不同元素中不计顺序地取出m 个构成原集合的一个子集。从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数，用m n C 表示： .)! (!! !)1()1(m n m n m m n n n C m n -=+--= 6．组合数的基本性质：（1）m n n m n C C -=；（2）11--+=n n m n m n C C C ；（3）k n k n C C k n =--11；（4）n n k k n n n n n C C C C 20 10==+++∑= ；（5）111++++-=+++k m k k m k k k k k C C C C ；（6）k n m n m k k n C C C --=。 7．定理1：不定方程x 1+x 2+…+x n =r 的正整数解的个数为11--n r C 。 [证明]将r 个相同的小球装入n 个不同的盒子的装法构成的集合为A ，不定方程x 1+x 2+…+x n =r 的正整数解构成的集合为B ，A 的每个装法对应B 的唯一一个解，因而构成映射，不同的装法对应的解也不同，因此为单射。反之B 中每一个解(x 1,x 2,…,x n ),将x i 作为第i 个盒子中球的个数，i=1,2,…,n ，便得到A 的一个装法，因此为满射，所以是一一映射，将r 个小球从左到右排成一列，每种装法相当于从r-1个空格中选n-1个，将球分n 份，共有11--n r C 种。故定理得证。 推论1 不定方程x 1+x 2+…+x n =r 的非负整数解的个数为.1r r n C -+
复数 一、基础知识 1．复数的定义：设i 为方程x 2 =-1的根，i 称为虚数单位，由i 与实数进行加、减、乘、除等运算。便产生形如a+bi （a,b ∈R ）的数，称为复数。所有复数构成的集合称复数集。通常用C 来表示。 2．复数的几种形式。对任意复数z=a+bi （a,b ∈R ），a 称实部记作Re(z),b 称虚部记作Im(z). z=ai 称为代数形式，它由实部、虚部两部分构成；若将(a,b)作为坐标平面内点的坐标，那么z 与坐标平面唯一一个点相对应，从而可以建立复数集与坐标平面内所有的点构成的集合之间的一一映射。因此复数可以用点来表示，表示复数的平面称为复平面，x 轴称为实轴，y 轴去掉原点称为虚轴，点称为复数的几何形式；如果将(a,b)作为向量的坐标，复数z 又对应唯一一个向量。因此坐标平面内的向量也是复数的一种表示形式，称为向量形式；另外设z 对应复平面内的点Z ，见图15-1，连接OZ ，设∠xOZ=θ,|OZ|=r ，则a=rcos θ,b=rsin θ,所以z=r(cos θ+isin θ)，这种形式叫做三角形式。若z=r(cos θ+isin θ)，则θ称为z 的辐角。若0≤θ<2π，则θ称为z 的辐角主值，记作θ=Arg(z). r 称为z 的模，也记作|z|，由勾股定理知|z|=22b a +.如果用e i θ 表示cos θ+isin θ，则z=re i θ ，称为复数的指数形 式。 3．共轭与模，若z=a+bi ，（a,b ∈R ）,则=z a-bi 称为z 的共轭复数。模与共轭的性质有：（1）2121z z z z ±=±；（2）2121z z z z ?=?；（3）2||z z z =?；（4）2 1 21z z z z =???? ??；（5）||||||2121z z z z ?=?； （6）| || |||2121z z z z = ；（7）||z 1|-|z 2||≤|z 1±z 2|≤|z 1|+|z 2|；（8）|z 1+z 2|2 +|z 1-z 2|2 =2|z 1|2 +2|z 2|2 ；（9）若|z|=1，则z z 1= 。 4．复数的运算法则：（1）按代数形式运算加、减、乘、除运算法则与实数范围内一致，运算结果可以通过乘以共轭复数将分母分为实数；（2）按向量形式，加、减法满足平行四边形和三角形法则；（3）按三角形式，若z 1=r 1(cos θ1+isin θ1), z 2=r 2(cos θ2+isin θ2)，则z 1??z 2=r 1r 2[cos(θ1+θ2)+isin(θ1+θ2)]；若2 1 212, 0r r z z z = ≠[cos(θ1-θ2)+isin(θ1-θ2)]，用指数形式记为z 1z 2=r 1r 2e i(θ1+θ2) , .) (2 12121θθ-=i e r r z z 5.棣莫弗定理：[r(cos θ+isin θ)]n =r n (cosn θ+isinn θ). 6.开方：若=n w r(cos θ+isin θ)，则)2s i n 2(c o s n k i n k r w n π θπ θ+++= ， k=0,1,2,…,n-1。 7．单位根：若w n =1，则称w 为1的一个n 次单位根，简称单位根，记Z 1=n i n π π2sin 2cos +，则全部单位根可表示为1,1Z ,1 1 21,,-n Z Z .单位根的基本性质有（这里记k k Z Z 1=，