nbhkdz.com冰点文库

数学竞赛讲义组合计数


数学竞赛讲义 第一讲 组合计数
本讲概述
组合数学是竞赛中最重要的一个板块,也是变化最多,最灵活,难以掌握,至今还没有一个系统 体系的学科.解决竞赛中的组合数学问题,往往不需要太多专门的知识,而是要求深刻的洞察能力和强 大的化归、转化能力.所谓“得组合者得天下” ,在联赛一二试乃至冬令营、集训队、IMO 中,最后的 胜者往往是成功完成组合问题的同学.因此,学习

组合数学对于竞赛获奖以及数学能力的培养都有着十 分重要的意义. 从本讲开始,我们将用七讲来对组合数学做一个大致的勾勒.通过这七讲的学习,达到以下目的: 1、掌握联赛一二试组合问题的特点与解法;2、对组合数学这门学科有一个初步的认识,为进一步学 习打下基础;3、了解部分冬令营级别组合问题的难度与解题模式. 七讲内容分别为:一、组合计数(1) 比高考略难的基本计数问题 二、组合计数(2) 需要较多技巧的专门计数问题 三、组合恒等式 较为重要和有趣味的组合恒等式 四、抽屉原理与存在性问题 五、容斥原理与极端性原理 六、染色问题与操作问题 七、组合数学综合问题 本讲中,假定各位同学已经大致学完了高考难度的排列组合模块内容,对加法原理、乘法原理等 有一定的理解并能完成相关的问题. 教师备注:本讲可与下一讲打通讲述,也可本讲专门讲常规的枚举、基本的组合问题,下一讲专 门讲述一些较为高级的技巧. 首先给出一些相关的基本知识: 1、 加法原理与乘法原理 加法原理: 完成一件事的方法可分成 n 个互不相交的类, 在第 1 类到第 n 类分别有 m1 , m2 ,..., mn 种 方法,则总共完成这件事有

一个复杂的组合计数问题分解成若干个便于计数的小问题. 2、 无重排列与组合 阶乘:定义 n ! ? n ? (n ? 1) ? (n ? 2) ? ... ? 2 ?1,读作 n 的阶乘
m 无重排列: 从 n 个不同元素中任取 m 个不同元素排成一列, 不同的排列种数称为排列数, 记为 An

(部分书中记为 Pnm ) ,由乘法原理得到
m An ?

n! ? n ? (n ? 1) ??... ? (n ? m ? 1) (n ? m)!

m 无重组合:从 n 个不同元素中任取 m 个元素并为一组,不同的组合种数称为组合数,记为 Cn ,

其公式为
m An n ? (n ? 1) ??... ? (n ? m ? 1) n! C ? ? ? m! m! (n ? m)! m! m n

3、 可重排列与组合(仅给出结论,请自证之) 可重排列:从 n 个不同元素中可重复地任取 m 个元素排成一列,不同的排列种数有 n 种; 有限个重复元素的全排列:设 n 个元素由 k 个不同元素 a1 , a2 ,..., ak 组成,分别有 n1 , n2 ,..., nk 个 ( n1 ? n2 ? ... ? nk ? n ) ,那么这 n 个元素的全排列数为
m

n! n1 !? n2 !? ... ? nk !

可重组合:从 n 个不同元素中,任意可重复地选取 m 个元素,称为 n 个不同元素中取 m 个元素的
m 可重组合,其种数为 Cn ? m?1

4、 圆排列(仅给出结论,请自证之) 在 n 个不同元素中,每次取出 m 个元素排在一个圆环上,叫做一个圆排列(或叫环状排列) .圆排 列有三个特点: (i)无头无尾; (ii)按照同一方向转换后仍是同一排列; (iii)两个圆排列只有在元 素不同或者元素虽然相同,但元素之间的顺序不同,才是不同的圆排列. 在 A ? {a1 , a2 , a3 ,?, an } 的 n 个元素中, 每次取出 m 个不同的元素进行圆排列, 圆排列数为

? mi ? m1 ? m2 ? ... ? mn 种方法.
i ?1

n

应用加法原理的关键在于通过适当的分类,使得每一类都相对易于计数. 乘法原理:完成一件事的方法有 n 个步骤, ,在第 1 步到第 n 步分别有 m1 , m2 ,..., mn 种方法,则总 共完成这件事有

Anm . m

? mi ? m1 m2 ... mn 种方法. 应用乘法原理的关键在于通过适当的分步,使得每一步
i ?1

n

例题精讲
板块一 利用加法、乘法原理以及枚举方法计数
联赛一试的填空题中出现的计数问题有接近一半的问题不需要用到很高深的技巧,而是直接利用

都相对易于计数. 由上可见,加法原理与乘法原理也是化归思想的应用,通过这两个原理以及它们的组合,可以将

联赛班·第 1 讲·教师版

1

最基本的加法、乘法原理,以及枚举方法来计数.这主要是考虑到有一部分参加联赛的同学并未经过专 业的竞赛训练.虽然如此,这部分计数问题枚举起来往往分类复杂,需要小心仔细. 从往年的联赛试题来看, 枚举法解决计数问题是最主要的题型之一, 其难点在于做到 “不重不漏” , 这是加法原理的一个简单的应用.枚举过程中,采用恰当的分类、分步形式,往往会收到化难为易的效 果. 【例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
2 2 前排中间的 3 个座位不能坐,有排法 A20 ,其中相邻的分三类,在前排的其中的 4 个座位有 3 A2 ;则符 2 A20 2 ? 3A2 2 ? 3A2 2 =346,故选 ? 11A2

【例4】 从给定的六种不同颜色中选用若干种颜色, 将一个正方体的六个面染色, 每面恰染一种颜色, 每两个具有公共棱的面染成不同的颜色。则不同的染色方法共有 __________ 种。 (注:如果 我们对两个相同的正方体染色后,可以通过适当的翻转,使得两个正方体的上、下、左、右、 前、后六个对应面的染色都相同,那么,我们就说这两个正方体的染色方案相同。 ) 【解析】 因为有公共顶点的三个面互不同色,故至少要用 3 种颜色,下面分四种情形来考虑. (1)6 种颜色都用时,现将染某种固定颜色的面朝上,从剩下 5 种颜色中取一种颜色染下底面有
1 种方法,余下 4 种颜色染四个侧面(应是 4 种颜色的圆排列)有 3!种方法.所以不同的染色方案有 C5 1 C5 ? 3!? 30种. 5 (2)只用 5 种颜色时,从 6 种颜色中取 5 种颜色有 C6 种方法,这时必有一组对面同色.从 5 种颜 1 色中取一种颜色染一组对面,并将它们朝上和朝下,有 C5 种方法,其余 4 种颜色染四个侧面(应是 4

合条件的排法种数中 的)

B

(这是正难则反的思想,从总体中除去不符合要求

种不同颜色的链排列)有

1 1 1 5 ? 3!种方法.所以不同的染色方案有 C6 ? C5 ? ? 3!? 90 种. 2 2

4 (3)只用 4 种颜色时,从 6 种颜色中取 4 种颜色有 C 6 种方法,这时必有两组对面同色,另一组

另解:分三类:①两人坐在前排,按要求有 4·6+4·5=44 种坐法.
2 ②两人坐在后排,按要求有: A11 =110 种坐法.③两人分别坐在前后排,有 8×12×2=192 种

2 对面不同色,将不同色的一组对面朝上和朝下,并从 4 种颜色中取两种颜色染上、下底面,有 C 4 种方

∴共有 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 的有 8 ? 9 ? 9 ? 9 ? 3 ? 17496 个,故所求五位数有 30000-17496=12504 个 (2)显然全部子集数为 2 个,故所求子集个数为 2 个)
100

法,其余两种颜色染四个侧面且使两组对面同色(应是两种不同颜色的链排列) ,只有 1 种方法.所以
2 4 不同的染色方案有 C 6 ? C4 ?1 ? 90 种.

3 (4)只用 3 种颜色时,从 6 种颜色中取 3 种颜色有 C6 种方法,这时三组对面都同色,用三种颜 3 ? 1 ? 20 种. 色去染它们只有 1 种方法.所以不同的染色方案有 C6

个,不包含任何奇数的子集即 {2, 4, 6,...,98,100} 的子集共有 2

50

100

? 250 个.(思考:请用最简洁的方法确定为何 n 元集合子集数为 2n

综上可知,不同的染色方案共有 30+90+90+20=230 种. 注 本题为 1996 年联赛试题,是历年来一试计数问题中最复杂的一道,其背景与波利亚群论计数原理 有关,这远远超出了高中范围,此处略去 【例5】 将 24 个志愿者名额分配给 3 个学校, 则每校至少有一个名额且各校名额互不相同的分配方法 共有 222 种. 【解析】 用 4 条棍子间的空隙代表 3 个学校,而用 ? 表示名额.如

【例3】 设 ABCDEF 为正六边形, 一只青蛙开始在顶点 A 处, 它每次可随意地跳到相邻两顶点之一. 若 在 5 次之内跳到 D 点,则停止跳动;若 5 次之内不能到达 D 点,则跳完 5 次也停止跳动,那 么这只青蛙从开始到停止,可能出现的不同跳法共 种 【解析】 这是标准的联赛风格的枚举问题,所谓杀鸡焉用牛刀,用递归方法来解这类问题就太麻烦了. 显然青蛙不能跳 1,2,4 次到达 D 点,于是青蛙的跳法只有以下两种: (1)青蛙跳 3 次后到达 D 点,有 2 种跳法; (2)青蛙跳 5 次后停止,跳 3 次有 2 ? 2 种,后两次有 2 种,共计 24 种; 所以,合计有 26 种跳法 注 本题为 1997 年联赛试题
3 2

| ???? | ?

? | ?? |

表示第一、二、三个学校分别有 4,18,2 个名额. 若把每个“ ? ”与每个“ | ”都视为一个位置,由于左右两端必须是“|”,故不同的分配方法相当于

24 ? 2 ? 26 个位置(两端不在内)被 2 个“|”占领的一种“占位法”.
“每校至少有一个名额的分法”相当于在 24 个“ ? ”之间的 23 个空隙中选出 2 个空隙插入“|”,故
联赛班·第 1 讲·教师版

2

有 C2 种. 23 ? 253 又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有 31 种. 综上知,满足条件的分配方法共有 253-31=222 种. [解法二] 设分配给 3 个学校的名额数分别为 x1 , x2 , x3 ,则每校至少有一个名额的分法数为不定方程

b 共 20 种情况。

4,3 2,1

4,3 2,1

3,2 1

3,2 1

1,2

1,2

1

1

2 同时,每个数码组(a,b)中的二个数码填上三个数位,有 C3 种情况。 2 2 2 故 n2 ? C3 (2C9 ? 20) ? 6(C9 ?10) ? 156 。 综上, n ? n1 ? n2 ? 165 。

x1 ? x2 ? x3 ? 24 .
的正整数解的个数,即方程 x1 ? x2 ? x3 ? 21的非负整数解的个数,它等于 3 个不同元素中取 21 个元素 的可重组合:
21 2 . H3 ? C21 23 ? C23 ? 253

注 本题为 2004 年联赛试题

板块二

映射与对应方法

由一一映射的定义可知,若存在从集合 M 到 N 的一一映射,则 M ? N .于是在难以直接计算集合 M 中元素个数时,我们可以设法构造这样一个映射,将问题转化为计算较为容易计算的集合 N 的元素 个数.基于这种两集合元素一一对应的特点,也称为“配对法” 【例8】 (1)试用对应方法证明可重组合公式:从 n 个不同元素中,任意可重复地选取 m 个元素,
m 称为 n 个不同元素中取 m 个元素的可重组合,其种数为 Cn ? m?1 k ?1 (2)证明:不定方程 x1 ? x2 ? ... ? xk ? n (k,n 为正整数)的非负整数解组数为 Cn ?k ?1

又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有 31 种. 综上知,满足条件的分配方法共有 253-31=222 种 注 本题为 2008 年联赛试题,从近年来联赛一试组合问题来看,组合计数问题难度明显降低了.本题所 应用的插空法是一种在高考和竞赛中常用的计数方法 【例6】 将 2 个 a 和 2 个 b 共 4 个字母填在 4 ? 4 方格表内,每个小方格内至多填 1 个字母,若使相同 字母既不同行也不同列,则不同的填法共有________种(用数字作答)。 【解析】 使 2 个 a 既不同行也不同列的填法有 C42A42=72 种,同样,使 2 个 b 既不同行也不同列的填 法也有 C42A42=72 种, 故由乘法原理, 这样的填法共有 722 种, 其中不符合要求的有两种情况: 2 个 a 所在的方格内都填有 b 的情况有 72 种;2 个 a 所在的方格内仅有 1 个方格内填有 b 的 情况有 C161A92=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。即 a, b, c ?{1, 2,...,9} ( 1 )若构成等边三角形,设这样的三位数的个数为 n1 ,由于三位数中三个数码都相同,所以,
1 n1 ? C9 ? 9。

【解析】 ( 1 )设 n 个元素为 1, 2,..., n ,并设取出的 m 个元素为 1 ? a1 ? a2 ? ... ? am ? n ,于是

1 ? a1 ? 0 ? a2 ? 1 ? ... ? am ? m ?1 ? n ? m ?1 ,作对应 (a1, a2 ,..., am ) ? (a1 ? 0, a2 ?1,..., am ? m ?1) ,易证明它为一一对应
m 后者为从 n ? m ? 1 个元素中取 m 个元素的组合数 Cn ? m?1 ,故得证

(2) 将 n 个圆圈与 k-1 个竖线排成一排, k-1 个竖线将 n 个圆圈依次分成 k 个部分: x1 , x2 ,..., xk , 易见不同的排列对应不定方程不同的解,易证它为一个一一对应,而在 n+k-1 个元素中取出 k-1 个的
k ?1 全排列数为 Cn ?k ?1 ,故得证.

【例9】 凸 n 边形的任意 3 条对角线不相交于形内一点,求其对角线在形内的交点总个数. 【解析】 任一形内交点对应两条对角线 l,m; 反之, 任意两条对角线唯一确定形内一个交点 P,从而 P 与 (l,m)构成一一对应;又任一对角线对应形内 2 顶点,n 边形中任取 4 顶点即可唯一确定两 对角线,于是有如下一一对应:点 P ? (l , m) ? ( A, B, C, D)
4 于是交点总个数=四顶点组个数= Cn

注 本题为组合数学一个重要分支——组合几何中的非常重要的一个结论, 可以利用它解决一些高难度 的组合几何计数问题 【例10】 将集合 A 中的 n 个元素排成一行,若某个子集中任意两元素不相邻,则称此子集为不好的,
k 试证明:k 元的不好的子集个数为 Cn ?k ?1

(2)若构成等腰(非等边)三角形,设这样的三位数的个数为 n2 ,由于三位数中只有 2 个不同数码。 设为 a、b,注意到三角形腰与底可以置换,所以可取的数码组(a,b)共有 2C 设 a>b,必须满足 b ? a ? 2b 。此时,不能构成三角形的数码是 a 9 8 7 6 5 4 3 2 1
2 9 。但当大数为底时,

【解析】 设 n 个元素排成一行依次为为 1, 2,..., n ,并设取出的 k 个元素为 1 ? i1 ? i2 ? ... ? ik ? n , 显然有 2 ? i j ?1 ? i j ( j ? 1, 2,..., k ?1) ; 作变换

1 ? i1 ? i2 ?1 ?i3 ? 2 . . . k? i

?k ( ?1 ) ? n ? k ,并取序列: ?1

联赛班·第 1 讲·教师版

3

(i1 , i2 ?1, i3 ? 2,..., ik ? (k ?1)) ,它是 1,2,n-k+1 中的一个严格上升的序列 作对应 (i1 , i2 ,..., ik ) ? (i1, i2 ?1, i3 ? 2,..., ik ? (k ?1)) ,
k 易证明它为一一对应,且后者的种数为从 n ? k ? 1 个元素中取 k 个元素的组合数 Cn ?k ?1 ,故

注 本题为 2006 年联赛试题 记集合 T ? ?0,1,2,3,4,5,6} , M ? ?

4.

得证 注 本题为第 16 届普特南竞赛题

? a1 a2 a3 a4 ? ? 2 ? 3 ? 4 ai ? T , i ? 1,2,3,4? ,将 M 中的元素按 ?7 7 7 7 ?

从大到小顺序排列,则第 2005 个数是

大显身手
1. (1)在 100 件产品中有 6 件次品,现从中任取 3 件产品,至少有 1 件次品的不同取法的种数 是
A. C C. C
1 6

5 5 6 3 5 5 6 2 1 1 0 4 1 1 0 3 ? 2 ? 3 ? 4 B. ? 2 ? 3 ? 4 C. ? 2 ? 3 ? 4 D. ? 2 ? 3 ? 4 A. 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 4 【解析】 用 [a1a2 ?ak ] p 表示 k 位 p 进制数,将集合 M 中的每个数乘以 7 ,得

C

2 94 3 94

B. C

1 6

C

2 99

M ? ? {a1 ? 73 ? a2 ? 72 ? a3 ? 7 ? a4 | ai ?T , i ? 1, 2,3, 4} ? {[a1a2a3a4 ]7 | ai ?T , i ? 1, 2,3, 4}.
M ? 中的最大数为 [6666 ]7 ? [2400 ]10 。
在十进制数中,从 2400 起从大到小顺序排列的第 2005 个数是 2400-2004=396; 而 [396 ]10 ? [1104 ]7 , 将此数除以 7 ,便得到 M 中的数:
4

3 100

?C

D. A

3 100

?A

3 94

(2) 从 4 名男生和 3 名女生中选出 4 人参加某个座谈会, 若这 4 人中必须既有男生又有女生, 则不同的选法共有 A.140 种 B.120 种 C 35 种 D.34 种 【解析】 (1) C 任取 3
3 件产品有 C100

1 1 0 4 ? 2 ? 3 ? 4 . 故选 C。 7 7 7 7

种方法, 其中无次品有 C

3 故至少有 94 种方法,

1

3 件次品的方法数为 C100

3 ? C94 .

注 本题为 2005 年联赛试题,题目形式提示我们,要采用进制转换.事实上,这类题目在小学和初中是 极为常见的.

3 1 2 2 (2)D 既有女生又有男生,可以分类表示,三男一女有 C4 种选法,二男二女有 C4 ? C3 C4 种,

5.
3 3 1 3 2 一男三女有 C1 4 ? C5 种选法,则总的不同的选法有 C4 ? C3 ? C4 ? C3 3 ? C1 4 ? C3 =34(种)

2.

由三个数字 1 、 2 、 3 组成的 5 位数中, 1 、 2 、 3 都至少出现 1 次, 这样的 5 位数 共有多少个?
1 5 1 4 2 4 3 4

已知两个实数集合 A={a1,a2,?,a100}与 B={b1,b2,?,b50}, 若从 A 到 B 的映射 f 使得 B 中每个元 素都有原象,且 f(a1)≤f(a2)≤?≤f(a100) 则这样的映射共有

【解析】 在 5 位数中, 若 1 只出现 1 次,有 C (C ? C ? C ) ? 70 个;
2 1 2 若 1 只出现 2 次,有 C5 (C3 ? C3 ) ? 60 个;

50 50 49 49 (A) C100 (B) C99 (C) C100 (D) C99 【解析】 不妨设 b1<b2<?<b50,将 A 中元素 a1, a2, ? , a100 按顺序分为非空的 50 组,定义映射 f:A →B,使得第 i 组的元素在 f 之下的象都是 bi (i=1,2,?,50),易知这样的 f 满足题设要求,每个 这样的分组都一一对应满足条件的映射,于是满足题设要求的映射 f 的个数与 A 按足码顺序

若 1 只出现 3 次,有 C C ? 20 个. 则这样的五位数共有 150 个. 故填 150 个.
3 5 1 2

49 49 分为 50 组的分法数相等,而 A 的分法数为 C 99 ,则这样的映射共有 C 99 ,故选 D。

注 本题为 2002 年全国联赛试题 在世界杯足球赛前,F 国教练为了考察 A1,A2,?,A7 这七名,准备让他们在三场训练比赛(每场 90 分钟)都上场,假设在比赛的任何时刻,这些中有且仅有一人在场上,并且 A1,A2,A3,A4 每 人上场的总时间(以分钟为单位)均被 13 整除,如果每场换人次数不限,那么按每名队员上场 的总时间计算,共有多少种不同的情况。 【解析】 设第 i 名队员上场的时间为 xi 分钟(i=1,2,3,?,7),问题即求不定方程 x1+x2+?+x7=270 ① 在条件 7|xi (1≤i≤4)且 13|xj (5≤j≤7)下的正整数解的级数。 若(x1,x2,?,x7)是满足条件①的一组正整数解,则应有 6.

注 本题为 05 年江苏省预赛试题 3. 已知集合 A ? x 5x ? a ? 0 , B ? x 6x ? b ? 0 , a, b ? N ,且 A ? B ? N ? ?2,3, 4 ? ,则 D. 42 【答】 ( )

整数对 ?a, b ? 的个数为 A. 20 B. 25 C. 30

?

?

?

?

? b 1? ? 2 ? a b ? 6 【解析】 由 5 x ? a ? 0 ? x ? ; 6 x ? b ? 0 ? x ? 。要使 A ? B ? N ? ?2,3,4? ,则 ? , 5 6 ?4 ? a ? 5 ? 5 ? ? 6 ? b ? 12 1 1 即? 。所以数对 ?a, b ? 共有 C6C5 ? 30 。 ?20 ? a ? 25

? xi =7m
i ?1

4

?x
j ?5

7

j

=13n

m,n∈N

联赛班·第 1 讲·教师版

4

∴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 即 m0=406 n0= ?203 是③的整数解 ∴ ③的整数通解为 m′=406 ?13k n′= ?203+7k k∈Z 令 m′≥0 n′≥0,解得 29≤k≤31 ????20 分 取 k=29,30,31 得到③满足条件的三组非负整数解:

(2)
本讲概述
组合计数的方法很多,除了上一讲的枚举、对应方法之外还包括:算两次、递推方法、容斥原理、 利用恒等式、母函数方法等;容斥原理的方法将在第四讲讲述,递推方法我们在数列部分单独讲述. 本讲主要讨论利用算两次方法计数的问题以及较为简单的递推方法(因为我们暂不具备完善的递推数 列知识) ;另外,本讲还将涉及到组合计数的二试与冬令营级别难度的少数问题. 首先给出本讲问题中要用到的知识(虽然这些知识可能暂时没有学到,但本讲只需会用即可) : 二项式定理: ( x ? y )n ? 特征方程与数列通项: 记一列数 a1 , a2 ,..., an ,... 为数列 {an } , 如果它满足 an?2 ? pan?1 ? qan ,(n ? 1) , 那么称 x2 ? px ? q
n n 为此数列的特征方程, (1)当有两互异实根时,数列通项为 an ? ? ? x1 ; ? ? ? x2 n (2)当有二等根时,数列通项为 an ? (? ? ? n) ? x1

? Cnk xn?k y k ,特别地, (1 ? x)n ? ? Cnk xk ,其中 n ? N ?
k ?0 k ?0

n

n

?m? ? 29 ? ?n ? ? 0 ?m ? 33 ? ?n ? 3

?m? ? 16 ? ?n ? ? 7 ?m ? 20 ? ?n ? 10

?m? ? 3 ? ?n? ? 14 ?m ? 7 ? ?n ? 17
4?1 33?1

从而得到②满足条件的三组正整数解: ????30 分

其中 ? , ? 为根据初值确定的待定系数

1)在 m=33,n=3 时,显然 x5=x6=x7=13 仅有一种可能, 又设 xi=7yi (i=1,2,3,4),于是由不定方程 y1+y2+y3+y4=33 有 C
3 ∴此时①有满足条件的 C 32 =4960 组正整数解。

? C ? 4960组正整数解。
3 32

例题精讲
板块一 算两次
算两次是一种非常重要的思想方法,在代数、组合、几何中都有涉及.组合问题中,组合极值、组 合不等式也常常涉及到算两次.组合计数中,在直接计算非常复杂甚至无从入手时,我们常常利用算两 次方法.顾名思义,算两次是指用不同的方法或者从不同的角度对同一个量进行计算,当两次都得到精 确值时,我们就得到一个等式,当为估计式时,我们就得到一个不等式.事实上,数学中有相当大一部 分定理就是利用算两次思想对原有的问题进行剖析,得到新的内在关系式. 【例11】 设 a1 , a2 ,…, an 为 1,2,?,n 的一个排列, f k 是集合 ai ai ? ak , i ? k 元素的个数,而 gk 是集合 ai ai ? ak , i ? k 元素的个数( k ? 1, 2,…, n ) ,证明

2)在 m=20,n=10 时,设 xi=7yi (i=1,2,3,4),xj=13yj (j=5,6,7)
3 2 由 y1+y2+y3+y4=20,有 C19 组正整数解;以及 y5+y6+y7=10,有 C9 组正整数解。 3 2 ∴此时①有满足条件的 C19 =34884 组正整数解。 ? C9

3) 在 m=7,n=17 时,设 xi=7yi (i=1,2,3,4),xj=13yj (j=5,6,7)
2 3 由 y1+y2+y3+y4=7,有 C6 组正整数解;以及 y5+y6+y7=17,有 C16 组正整数解。????40 分

?

?

?

?

? f ? ?g
k ?1 k k ?1

n

n

k

综上所述,①满足条件的正整数解的组数为
3 3 3 3 2 =4960+34884+2400=42244 C32 ? C19 ? C9 ? C6 ? C16

【解析】 考虑集合 S ? (ai , ak ) ai ? ak , i ? k 的元素个数 S 。一方面,固定 k 先对 i 求和,然后再对 ????50 分

?

?

注 本题为 2002 年联赛二试最后一题, 是一道不是很难的组合数论问题.问题求解过程中多次用到了我 们的例 8 的结论.

k 求 和 , 得 S ? ? fk ; 另 一 方 面 , 固 定 i 先 对 k 求 和 , 然 后 再 对 i 求 和 , 又 得 到
k ?1

n

S ? ? gi ? ? g k ,所以得 ? f k ? ? g k 。
i ?1 k ?1 k ?1 k ?1

n

n

n

n

联赛班·第 1 讲·教师版

5

注 本题只是为了说明算两次的基本思想和方法,这里的计数是抽象的,这种方法相当于考虑各个分量 对总体的“贡献” ,因此也有人把它叫做“贡献法”.请参考习题第一题 【例12】 有 n 粒小球,任意将其分成两堆,求出两堆球数之积,再将其中一堆任意地分成两堆,求出 此两堆之积,如此下去,直至将小球分成 n 堆(每个球 1 堆)为止.记此过程中所有的乘积之 和为 S,求 S 的所有可能值.
2 2 【解析】 以 n=8 为例,不论如何分,最后总得到 S ? 28 ? C8 ,于是猜想对一般情形总有 S ? Cn ,即

n 粒小球中任取两个组成小球对的个数;另一方面,每将一些小球分成两堆,就将原来的一 些小球对(假设只有同一堆才能组成小球对)拆开,拆开的数目恰为两堆个数之积,最终的 小球对个数为 0,从而乘积之和即为最初的小球对个数,故得证. 注 本题构造了一种巧妙的对应,使原来无法下手的问题变得有章可循.事实上,组合问题,特别是算 两次问题最关键的就是寻找算两次的对象,本题中就是对小球对进行算两次,使得问题清晰明了. 【例13】 一张正方形纸片内有 1000 个点,这些点及正方形的顶点中任意 3 点不共线.在这些点及正方 形的顶点间连一些线段将正方形全部分成小三角形(它们都以所连线段及正方形的边为边, 且所连线段除端点外两两无公共点).问一共连有多少条线段,一共得到多少个三角形? 【解析】 设一共连有 l 条线段,得到 k 个三角形. 首先对角度和进行计数: 一方面,所得 k 个三角形的内角和为 k ?180 ;另一方面,计算 1000 个内点及 4 个正方形顶点处内角和为 1000 ? 360 ? 4 ? 90 ,从而算得 k=2002; 其次,对边数进行计数: k 个三角形共 3k 条边,另一方面,每条线段是两个三角形的公共 边,正方形的每条边被计算 1 次,共 2l ? 4 条边,从而 2l ? 4 ? 3k ,得到 l ? 3001 注 本题的背景是计算机图形学中著名的三角面片分划问题,这类问题在冯康先生的有限元中也有应 用. 从本题及习题 2 可以得到计算这类问题的一般方法,即对边、角乃至同色角、异色角等元素进行计 数. 【例14】 (选讲) 能否把 1,1,2,2,3,3, ?, 1986,1986 这些数排成一行, 使得两个 1 之间夹着 1 个数, 两个 2 之间夹着 2 个数,两个 1986 之间夹着 1986 个数? 【解析】 设能将上述数字排成一行满足题设,这是每一个数 i(1 ? i ? 1986) 可赋予它一对有序实数

关系式,进而利用数列知识进行求解.一般来说, 这类问题的关键在于如何得到递推关系式.对于竞赛选 手而言, 由组合问题的递推关系式得到通项总是很简单的,因为组合问题的特性决定了递推关系式不会 太过复杂. 由于我们没有详细讲述数列通项求法,所以这里只给出较为简单的问题. 注:建议教师主要讲述如何由题目条件得到递推式,至于递推式求解可以淡化或者让学生自行求 解 【例15】 (Fibonacci 数列)假设一对兔子每隔一月生一对小兔,每对小兔两个月后也逐月生一对小 兔,如年初时放一对成年兔,那么一年以后兔房中有多少只兔子? 【解析】 用 a n 表示第 n 个月初的小兔对数,易得到 a 1 ? 1, a 2 ? 2, a 3 ? 3,... 一般地,第 n 个月初的小兔分为两部分:第 n-1 个月的兔子数与第 n 个月初出生的小兔对数, 即得到递推式 a n ? a n?1 ?a n?2 ,由特征方程的结论及初值,可得到 a13 ? 377

an ?

1 1 ? 5 n?1 1 ? 5 n?1 (( ) ?( ) ) 2 2 5

注 关于斐波那契数列的进一步知识我们到数列部分再详细讲述 【例16】 用 1,2,3 来构造一个 n 位数,但不允许数位中出现两个连续的 1,问这样的数有多少个? 【解析】 设有 an 个,显然 a 1 ? 3, a 2 ? 8 ,讨论: 若 n 位数第一位不是 1,那么后面可以随便写,于是这样的有 2 an ?1 个, 若第一位是 1,第二位写 2 或 3,第三位后可以随便写,于是这样的有 2 an?2 个, 得到递推式 a n ? 2a n?1 ?2a n?2 , n ? 3 ,由特征方程的结论及初值,化简得到

an ?

1 4 3

((1 ? 3)n ? 2 ? (1 ? 3) n ? 2 )

注 一般写出原始结果即可,或者把化简结果同时写出

板块三

组合计数综合问题
r s t

( xi , yi ) 作为坐标,这里坐标值分别为它第一次与第二次出现的位置序号 . 显然有关系: yi ? xi ? i ? 1.
现用两种方法计算全体数的坐标和:
2?1986

【例17】 设 r , s , t 为整数,集合 {a | a ? 2 ? 2 ? 2 ,0 ? t ? s ? r} 中的数由小到大组成数列 {an } :

7,11,13,14,? ,则 a36 ?

131



2 【解析】 ∵ r , s , t 为整数且 0 ? t ? s ? r ,∴ r 最小取 2,此时符合条件的数有 C2 ? 1

一方面,直接从整体看,坐标和为

? k ? 1986 ? (2 ?1986 ? 1) 为偶数;
k ?1

2 r ? 3 , s , t 可在 0,1,2 中取,符合条件有的数有 C3 ?3
2 同理, r ? 4 时,符合条件有的数有 C 4 ? 6

另一方面,就某一个 i,两坐标和为 2xi ? i ? 1 ,从而所有坐标和为
1986 i ?1

? (2 x ? i ? 1) ? 2? x ? ? i ?1986 =偶数+ 993 ?1987 为奇数.
i i ?1 i i ?1

1986

1986

此两者显然矛盾

2 r ? 5 时,符合条件有的数有 C5 ? 10 2 r ? 6 时,符合条件有的数有 C6 ? 15 2 r ? 7 时,符合条件有的数有 C7 ? 21

注 本题为第二届冬令营的一道很难的问题,方法较多,上面给出的方法是一个很巧妙的解法,利用奇 偶性导出了矛盾,是命题人所没有想到的.

板块二

递推方法

当所计数对象按从 1 到 n 有规律出现时,可视之为一个数列并考察其相邻项之间关系,得到递推
联赛班·第 1 讲·教师版

6

因此, a36 是 r ? 7 中的最小值,即 a36 ? 20 ? 21 ? 27 ? 131 注 本题为 2005 年四川预赛题,事实上此题源自 2003 年全国高考理科试卷压轴题,用二进制方法求解 最为方便,可参考左晓明《2003 年高考理科数学压轴题的一种巧妙解法及其推广》中学教研 2003.12 【例18】 如果自然数 a 的各位数字之和等于 7,那么称 a 为“吉祥数”.将所有“吉祥数”从小到大排 成一列 a1 , a2 , a3 ,?, 若 an ? 2005 , 则 a5 n ? __________ . 【解析】 准确理解“吉祥数”的定义是解题的前提,根据题意,可将此计数问题转化为考虑不定方程 的非负整数解的个数. ∵方程 x1 ? x2 ? ? ? xk ? m 的非负整数解的个数为 C
m m? k ?1 .而使

(2)当数码组恰含二个值 a , b ( a ? b ) . ①数码组为 (a, a, a, b) 型,则任取三个数码皆可构成三角形,对于每个 a ?{2,
9

,9} , b 可取

a ? 1 个值,则数码组个数为 ? (a ? 1) ? 36 ,对于每组 (a, a, a, b) ,b 有 4 种占位方式,于是这种 n 有
a ?2

36 ? 4 ? 144 个.
②数码组为 (a, b, b, b) 型( a ? b ) ,据构成三角形条件,有 b ? a ? 2b ,

x1 ? 1, xi ? 0(i ? 2) 的整数解

m?1 6 m ? 7 ,可知, k 位“吉祥数”的个数为 P(k ) ? Ck 的个数为 Cm ? k ?2 .现取 ?5 .

b 的取值

1

2

3

4

5

6

7

8

9

∵ 2005

是 形 如

2abc 的 数 中 最 小 的 一 个 “ 吉 祥 数 ” , 且

?b, 2b?

M 中 a 的个数

0

1

2

3

4

3

2

1

0

6 6 6 P(1) ? C6 ? 1, P(2) ? C7 ? 7, P(3) ? C8 ? 28,
6 对于四位“吉祥数” 1abc,其个数为满足 a ? b ? c ? 6 的非负整数解个数,即 C6 ?3?1 ? 28 个.

共得 16 个数码组,对于每组 (a, b, b, b) , a 有 4 种占位方式,于是这种 n 有 16 ? 4 ? 64 个. ③数码组为 (a, a, b, b) 型( a ? b ) ,据构成三角形条件,有 b ? a ? 2b ,同上得 16 个数码组,对
2 于每组 (a, a, b, b) ,两个 a 有 C4 ? 6 种占位方式,于是这种 n 有 16 ? 6 ? 96 个.

∴2005 是第 1+7+28+28+1=65 个“吉祥数” ,即 a65 ? 2005 . 从而 n ? 65,5n ? 325. 又 P(4) ? C ? 84, P(5) ? C
6 9 6 10

? 210, 而 ? P(k ) ? 330.
k ?1

5

以上共计 144 ? 64 ? 96 ? 304 个. (3)当数码组恰含三个值 a, b, c (a ? b ? c) . ①数码组为 (a, b, c, c) 型,据构成三角形条件,则有 c ? b ? a ? 2c ,这种 (a, b, c, c) 有 14 组,每
2 组中 a , b 有 A4 ? 12 种占位方式,于是这种 n 有 14 ? 12 ? 168 个.

∵从大到小排列的最后六个五位“吉祥数”依次是:70000,61000,60100,60010,60001,52000. ∴第 325 个“吉祥数”是 52000,即 a5n ? 52000 . 注 1、本题为 2005 年全国联赛试题 2、很多计数问题都可以转化为求不定方程的解的组数,一般地,有 (1)不定方程 x1 ? x2 ? ? ? xn ? m 的非负整数解的组数为 C (2)不定方程 x1 ? x2 ? ? ? xn ? m 的正整数解的组数为 C
n?1 n? m?1

②数码组为 (a, b, b, c) 型, c ? b ? a ? b ? c ,此条件等价于 M ? {1, 2,

,9} 中取三个不同的数构

?C

m n? m?1 ;

n ?1 m?1 .

成三角形的方法数,有 34 组,每组中 a , b 有 A4 ? 12 种占位方式,于是这种 n 有 34 ?12 ? 408 个.
2 2 ③数码组为 (a, a, b, c) 型, c ? b ? a ? b ? c ,同情况②,有 34 A4 ? 408 个 n 值.

【例19】 若四位数 n ? abcd 的各位数码 a, b, c, d 中,任三个数码皆可构成一个三角形的三条边长,则 称 n 为四位三角形数,试求所有四位三角形数的个数. 【解析】 三个数构成三角形的三条边长的充要条件是任意两个数之和大于第三个数.本题需要根据四 个数码的各种可能情况分类进行分析,按照四个数码取值个数的不同进行分类比较容易入手 一些. 称 (a, b, c, d ) 为 n 的数码组,则 a, b, c, d ? M ? {1, 2, (1)当数码组只含一个值,为 (a, a, a, a), a ? 1, 2,

以上共计 168 ? 408 ? 408 ? 984 个 n 值. (4) a, b, c, d 互不相同,则有 d ? c ? b ? a ? c ? d ,这种 a, b, c, d 有16 组,每组有 4! 种排法, 共得 16 ? 4! ? 384 个 n 值. 综上,全部四位三角形数 n 的个数为 9 ? 304 ? 984 ? 384 ? 1681 个. 注 本题为 2007 年江西省预赛试题.本题的情况非常多,一定要注意分类的合理性和计数的准确性.

,9} .

,9 ,共得 9 个 n 值.
联赛班·第 1 讲·教师版

7

教师备注:

若例题不够可适当选择习题讲授

11. 一次竞赛有 n(n ? 2) 名选手参加,每天选手的得分恰好组成集合 {1, 2,..., n} ,如果在第 k 天 末,每两名选手的得分之和均为 52 分,求出使这件事成立的所有数对 ( n, k ) 【解析】 一方面,k 天末所有选手得分总和为 k ?

大显身手
7. 在一次测验中满分 100 分,所有同学得分都是非负整数,设 n 位同学的的得分分别为 ,记 M ? a1 ? a2 ? ... ? an , a1 , a2 ,..., an ,其中得分至少为 k 分的有 bk 个( 1 ? k ? 100)

? l ? 2 kn(n ? 1) ,另一方面,由每两名选手的得分
l ?1

n

1

N ? b1 ? b2 ? ... ? b100 ,那么 M,N 的大小关系为?
【解析】 M=N.一方面,得分为 k 的同学对 M 的贡献为 k,另一方面他在 b1 , b2 ,..., bk 中各被计算了一次, 每次为 1,共计为 k,于是得证. 注 本题为典型的算两次方法 在一张正方形纸片的内部给出了 1985 个点,现用 M 记这纸片的 4 个顶点与内部 1985 个点构 成的集合,并按下述规则将这张纸剪成一些三角形: (1) 每个三角形的三个顶点都是 M 中的点; (2) 除顶点外,每个三角形中不再含有 M 中的点. 问:可剪出多少个三角形,共需剪多少刀?(剪出一条边需要剪一刀) 【解析】 M 中每个点都是若干三角形的公共顶点,不论怎样剪,纸的四个顶点处各三角形内角和均为 90 度, 其余 1985 个点处所有三角形内角和则为 360 度. 设剪出了 x 个三角形, 那么全体三角 形内角和为 180x 度,于是我们得到: 180 ? x ? 4 ? 90 ? 1985 ? 360 ? x ? 3972 又每个三角形都有三条边,共有 3972 ? 3 条边,另一方面,每剪一次产生两条三角形的边, 而四边形的四条边不用剪,设共剪了 y 刀,于是所有三角形共有 2y+4 条边, 由 3972 ? 3 ? 2 y ? 4 ? y ? 5956 注 考虑计算“角度”是问题的突破口.请注意比较例 3 一个立方体的顶点标上+1 或 ?1 ,面上标一个数,它等于这个面的 4 个顶点处的数的乘积.这 样所标的 14 个数的和能否为 0? 【解析】 考虑这 14 个数的乘积 S: 将每个面所标的数写成 4 个顶点处的数的乘积,这样,在 S 中,每个顶点所标的数将作为乘 9. 数出现 4 次(其中面上乘积中出现 3 次) ,从而它对 S 的贡献为 1,因此 S ? 1 ? 1 ; 另一方面, 14 个数的积 S 为 1, 故这 14 个为 1 或 ?1 的数中,?1 的个数为偶数, 由于 ?1 的个数不为 7, 故和必不为 0.
8

之和均为 52 分知总分为 26n, 从而 k (n ? 1) ? 52 ? (n, k ) ? (51,1),(25, 2),(12, 4),(3,13) , 经 检验,除第一组外其他都满足,从而共有 3 对. 注 本题为一个简单的算两次问题 12. 某人有 n 元钱, 去买三种物品: 甲物品 1 元, 乙丙均为 2 元, 求花完这 n 元钱有多少种方式? 【解析】 a 1 ? 1, a 2 ? 3 , a n ? a n?1 ?2a n?2 , an ?

1 n ?1 (2 ? (?1) n ) 3

8.

13. 将一个三位数的三个数字顺序颠倒, 将所得到的数与原数相加, 若和中没有一个数字是偶数, 则称这个数是“奇和数” ,那么,所有的三位数中,奇和数有 ( ) (A)100 个. (B)120 个. (C)160 个. (D)200 个. 【解析】 设三位数为 abc ,对 a, b, c 的可能取值进行分析.

abc ? cba ? 100(a ? c) ? 10(b ? b) ? (a ? c) ,若 a ? c 不进位,则和数的十位数必为偶数,不
符合题意,所以 a ? c 只能是 11,13,15,17.
2 因为 11=9+2=8+3=7+4=6+5,所以 a , c 取值有 4 A2 种可能; 2 因为 13=9+4=8+5=7+6,所以 a , c 取值有 3 A2 种可能; 2 因为 15=9+6=8+7,所以 a , c 取值有 2 A2 种可能; 2 因为 17=9+8,所以 a , c 取值有 A2 种可能;

由于 b ? b 不能进位,所以 b 只能取 0,1,2,3,4.
2 2 2 2 因此,满足条件的数共有 5(4 A2 ? 3A2 ? 2 A2 ? A2 ) ? 100 个,故选(A).

10. 一条走廊宽 2 m, 长 8 m, 用 6 种颜色的 1 ? 1 m 的整块地砖来铺设(每块地砖 都是单色的, 每种颜色的地砖都足够多), 要求相邻(即有公共边的)的两块地砖颜色不同, 那么所有 的不同拼色方法有
2

注 本题为 2007 年广西预赛试题. 对于新定义题,准确理解概念是关键,本题以 a ? c 的可能取值为突 破口,使得计数变得简单. 这种题型在小学和初中非常常见

A. 308 个

B. 30 ? 257 个

C. 30 ? 207 个

D. 30 ? 217 个
A B

【解析】 铺第一列(两块地砖)有 30 种方法;其次铺第二列.设第一列的两格铺了 A 、 B 两色(如图),那么,第二列的上格不能铺 A 色.若铺 B 色,则有 (6 ? 1) 种铺法;若不

第三讲 二项式定理与组合恒等式
本讲概述
本讲将涉及到组合学的一个重要内容:组合恒等式.从组合数和二项式定理开始,可以得到很多有

2 铺 B 色,则有 (6 ? 2) 种方法. 于是第二列上共有 21 种铺法. 同理, 若前一列铺好,则其后

一列都有 21 种铺法.因此,共有 30 ? 21 种铺法. 故选 D. 注 本题为 2005 江苏预赛题.
7

联赛班·第 1 讲·教师版

8

趣的恒等式.事实上,历史上出现过数以千计的组合恒等式,直到现在仍然有新的恒等式出现.在中科 大小丛书《组合恒等式》中,史济怀教授给出了两百多个组合恒等式. 由于现在各级竞赛中对组合恒等式要求大为降低,因此本讲只涉及比较简单的恒等式,以及利用 这些恒等式来解决问题 以下给出一些基础知识: 1.二项式定理
k n?k k ( a ? b) n ? ? C n a b (n ? N*) k ?0 n

(1)公式法,利用上述基本组合恒等式进行证明. (2)利用二项式定理,通过赋值法或构造法用二项式定理于解题中. (3)利用数学归纳法. (4)构造组合问题模型,将证明方法划归为组合应用问题的解决方法. (5)母函数法,此方法仅在冬令营以上级别要求

例题精讲
【例20】 试证明恒等式:

?C
k ?0

n

k n

k ? 2 , ? (?1) C ? 0, ? 2k Cn ? 3n n k k ?0 k n k ?0

n

n

2.二项展开式的通项
r n ?r r Tr ?1 ? Cn a b (0 ? r ? n) 它是展开式的第 r+1 项.

【解析】 由二项式定理 (a ? b) n ?

? Cnk a n?k b k (n ? N*) ? (1 ? x)n ? ? Cnk xk ,
k ?0
k ?0

n

n

3.二项式系数
r Cn (0 ? r ? n).

上式中取 x ? 1, ?1, 2 即得到上述恒等式 注 可见取不同的 x 还可以得到一系列恒等式 【例21】 证明: (1)

4.二项式系数的性质 (1) C ? C
k n k n n ?k n k n?1

? kC
k ?1 n n

n

k n

? n ? 2n ?1

(0 ? k ? n). ?C
k ?1 n?1

n n n n?1 (2) C ? Cn ?1 ? ?Cn? 2 ? ? ? Cn?k ? Cn? k ?1 .
k k ?1 【解析】 (1)由 kCn ? nCn ?1 可得

(2) C ? C

(0 ? k ? n ? 1).
0 n 1 n

? kC ? ? nC
k ?1 k n k ?1

n

n

k ?1 n ?1

k ?1 k n ?1 ? n ? ? Cn ?1 ? n ? ? Cn ?1 ?n ? 2 k ?1 k ?0

n

n ?1

(3)若 n 是偶数,有 C ? C ? 若 n 是奇数,有 C ? C ?
0 n 1 n

? C ,C ? ?C
n ?1 2 n

n 2 n

n 2 n

?C
n ?1 2 n

n ?1 n

?C ?

n n ,即中间一项的二项式系数

C 最大.

n 2 n

(2)由 C ? C
k n

n n n Cn ? Cn ?1 ? ?Cn?2 ?
n

?C
2 k n

k n?1 n n?k

?C

k ?1 n?1

(0 ? k ? n ?1) 得到
n?1 n?1 n?1 ? (Cn ?k ?1 ? Cn?k ) ? Cn?k ?1.

n?1 n?1 n?1 n?1 n?1 ? Cn ?1 ? (Cn?2 ? Cn?1 ) ? (Cn?3 ? Cn?2 ) ?

,C

n ?1 2 n

?C

,C

n ?1 2 n

n ?1 n ,即中项二项的二项式系 ? Cn ? Cn

数 C 和C
0 n 1 n

n 2 n

n ?1 2 相等且最大. n

【例22】 证明: 【解析】 首先求
n

?k C
k ?0 n

? n ? (n ? 1)2n?2
k n

(4) C ? C ? C ? ? ? C ? 2 .
2 n n n n 0 2 4 1 3 5 (5) Cn ? Cn ? Cn ? ? ? Cn ? Cn ? Cn ? ? ? 2n?1.

(k ? 1)C ?k
k ?0


n n?2 l ?0

k k ?2 l n?2 , (k ? 1)Cn ? ?n (n ? 1)Cn (n ? 1)? Cn ?k ?2 ? n ? 2 ? n ? (n ? 1)2 k ?0 k ?2

(6) kC n ? nC n ?1 或C n ?
k k

k ?1

n k ?1 C n ?1 . k


m n ?k ? m

? kC
k ?1

n

k n

? n ? 2n ?1 ,相加即得原式

(7) C ? C
k n

m k

? C ?C
m n

k ?m n ?m

?C

k ?m n

C

(m ? k ? n).

注 类似地,我们还可以求得

?k C
3 k ?0

n

k n

? n ? (n ? 1)(n ? 3)2n?3 ,....

n n n n n?1 (8) Cn ? Cn ?1 ? ?Cn? 2 ? ? ? Cn? k ? Cn? k ?1 . m 以上组合恒等式(是指组合数 C n 满足的恒等式)是证明一些较复杂的组合恒等式的基本工具.

【例23】 证明:
n

?C
k ?0

n

k 2n

? 22 n?1 ?

(2n)! 2 ? (n!)2
k ? n ?1

(1)——(6)请自证.(7)和(8)的证明将在后面给出. 5.证明组合恒等式的方法常用的有

【解析】

? C2kn ? ? C2kn ?
k ?0 k ?0

2n

k ? n ?1

?

2n

k 2n C2 ? n ?2

?C

2n

k 2n



联赛班·第 1 讲·教师版

9

其中令 k=2n-j,
n

k ? n ?1

?

2n

k 2n? j k n C2 ? ? C2jn ? ? C2 n ? ? C2 n n ? C2 n , j ?0 j ?0 k ?0

n ?1

n ?1

n

【解析】 考虑 (1 ? x)m ? (1 ? x)n 中 x 的系数:
t

t 一方面 x 的系数即 (1 ? x)m? n 的系数,即 Cm ?n ,
t

于是

1 2n (2n)! k n 2 n ?1 C2 (2 ? C2 ? ? n ? n) ? 2 2 2 ? (n !)2 k ?0

另一方面,利用二项式定理将 (1 ? x)m ? (1 ? x)n 展开并相乘,得到 x 的系数即为(2)式左边, 从而(2)式得证;在此式中令 m ? n ? t 即得(1)式.
t

【例24】 已知数列 a0 , a1 , a2 ,?(a0 ? 0) 满足 ai ?1 ?a i ?1 ? 2ai (i ? 1,2,3,?), 求证: 对于任何自然数 n,

下证(3) :利用 (1 ? x) n 的展开式, 考虑 (1 ? x)2n ? (1 ? x)2n 中 x 的系数:
2n

p( x) ? a0C (1 ? x) ? a1C x(1 ? x)
0 n n 1 n

n?1

? a2C x (1 ? x)
2 n 2

n ?2

? ? ? an?1C

n?1 n

x

n?1

(1 ? x) ? an C x
n n

n

一方面 (1 ? x 2 )2 n 展开式中 x 的系数即为右端;
2n

是 x 的一次多项式或零次多项式. 【解析】 由 ai ?1 ? ai ?1 ? 2ai 知 则 ai ? ai ?1 ? d ? a0 ? id (i ? 1,2,?), 从而可将 p ( x) {an } 是等差数列, 表示成 a0 和d 的表达式,再化简即可. 因为 ai ?1 ? ai ?1 ? 2ai (i ? 1,2,3,?) ,所以数列 {an } 为等差数列,设其公差为 d. 有 ai ? a0 ? id (i ? 1,2,3,?) . 从而

另一方面 (1 ? x)2n ? (1 ? x)2n 分别用二项式展开后乘开, x 的系数即为左式,故得证 注 本题使用的方法即母函数方法,但母函数方法在联赛中不要求,我们只举此两例,以供有兴趣的同 学了解一下
2n

【例26】 设 n ? m ,证明:

n?m k ?0

?C

m? k n

m n?m m ? Cm Cn ?k ? 2

0 1 2 2 n n P( x) ? a0Cn (1 ? x) n ? (a0 ? d )Cn x(1 ? x) n?1 ? (a0 ? 2d )Cn x (1 ? x) n?2 ? ? ? (a0 ? nd)Cn x
0 1 n n 1 2 2 n n ? a0 [Cn (1 ? x) n ? Cn x(1 ? x) n?1 ? ?? Cn x ] ? d[1? Cn x(1 ? x) n?1 ? 2Cn x (1 ? x) n?2 ? ?? nCn x ],

【解析】 考虑从 n 个人中选出 m 名正式代表及若干名列席代表(列席代表不限,可为 0)
m 一方面,先选定正式代表,有 Cn 种方法,从余下 n-m 人中选列席代表,有 2 m 共有 2n?m Cn 种方法;
n?m

种方法,一

另一方面,可先选出包括正式代表和列席代表共 m+k 人( k ? 0,1, 2,..., n ? m ),然后再从中选
m? k m 出 m 名正式代表,对每一个 k 有 Cn ? Cm ? k 种选法,从而选法总数为
n?m k ?0

由二项式定理,知

C (1 ? x) ? C x(1 ? x)
0 n n 1 n
k n

n?1

? C x (1 ? x)
2 n 2

n ?2

? ? ? C x ? [(1 ? x) ? x] ? 1,
n n n n

?C

m?k n

m ? Cm ? k 种,故

n! (n ? 1)! k ?1 又因为 kC ? k ? ? n? ? nCn ?1 , k!(n ? k )! (k ? 1)![(n ? 1) ? (k ? 1)]!
1 2 2 n n 从而 Cn x(1 ? x) n?1 ? 2Cn x (1 ? x) n?2 ? ? ? nCn x

得证 注 本题采用了构造组合模型的方法.事实上,近年来组合恒等式考察内容非常浅,联赛中不会涉及到 利用母函数、递推方法、组合模型的复杂恒等式证明,因此,我们仅各举一例说明方法. 【例27】 试用恒等变形方法证明例 7 的等价形式:

1 n ?2 ? nx[(1 ? x) n?1 ? Cn ? ? ? x n?1 ] ?1 x(1 ? x)

?C
k? p

n

k n

? Ckp ? 2n? p Cnp
n n? p l ?0

? nx[(1 ? x) ? x]n?1 ? nx.

所以 P( x) ? a0 ? ndx.

【解析】 注意到 Cn ? Ck ? Cn ? Cn? p ,于是
k p p

n ?k

? Cnk ? Ckp ? ? Cnp ? Cnn??pk ? Cnp ? ?Cnl ? p ? 2n? p Cnp
k? p k? p
15

n

当 d ? 0时, P( x)为x 的一次多项式,当 d ? 0时, P( x)为零次多项式. 注 本题有一定的难度,运算量也很大,需要对二项式定理及常用组合恒等式相当熟练.建议选择讲授. 本题亦可用递推方法来解 【例25】 证明: (1)

注 本题重点是前面的变形 【例28】 (1)试求 ( x ? x ? x ? x ) 展开式中 x 的系数; (2)在一次实战军事演习中,红方的一条直线防线上设有 20 个岗位。为了试验 5 种不同新 式武器, 打算安排 5 个岗位配备这些新式武器, 要求第一个和最后一个岗位不配备新式武器, 且每相邻 5 个岗位至少有一个岗位配备新式武器,相邻两个岗位不同时配备新式武器,问共 有多少种配备新式武器的方案?
2 3 4 6

? (C
k ?0

n

k 2 n

n ) ? C2 n

(2)

?C ? C ? C (3) ? (?1) (C ) ? (?1) C
k n t ?k m t m? n k k k 2 2n n k

【解析】 (1)由 ( x ? x ? x ? x ) ? x (1 ? x ? x ? x ) ? x (1 ? x) (1 ? x ) ,
2 3 4 6 6 6 2 3 6 6 6 2 6

n 2n

知只须求 (1 ? x) (1 ? x ) 展开式中 x 的系数。又
2 6
9

联赛班·第 1 讲·教师版

10

(1 ? x) 6 (1 ? x 2 ) 6 ? (1 ? 6 x ? 15x 2 ? 20x 3 ? 15x 4 ? 6 x 5 ? x 6 ) ? (1 ? 6 x 2 ? 15x 4 ? 20x 6 ? 15x 8 ? 6 x10 ? x12 )
因此 x 的系数为 6×15+20×20+6×15 = 580 (2) 设 20 个岗位按先后排序为 1, 2, , ? , 20, 且设第 k 种新式武器设置的序号为 ak (k ? 1,2,3,4,5) 。 令 x1 ? a1 , x2 ? a2 ? a1 , x3 ? a3 ? a2 , x4 ? a4 ? a3 , x5 ? a5 ? a4 ,
9

k 所以a n ? 2 2 n ? ? (?1) k ? 2 2 n ? 2 k C 2 n ? k ?1 k ?1 k k ?1 ? 2 2 n ? ? (?1) k ? 2 2 n ? 2 k (C 2 n ? k ?C 2 n ? k ) k ?1 k k 2n?2k k ?1 ? ? (?1) k ? 2 2 n ? 2 k C 2 C2 n ? k ? ? ( ?1) ? 2 n?k . k ?0 k ?1 n n n

n

令r ? k ? 1, 则

? (?1)
k ?1

n

k

k ?1 r ?1 r ? 2 2n?2k C 2 ? 2 2( n ?1) ? 2 r C 2 n ? k ? ? ( ?1) ( n ?1) ? r ?1 r ?0 r ? ? ? (?1) r 2 2( n ?1) ? 2 r C 2 ( n ?1) ? r ?1 ? ? a n ?1 . n ?1

n ?1

x6 ? 20 ? a5 ,则有
x1 ? x2 ? x3 ? x4 ? x5 ? x6 ? 20
其中 2 ? xk ? 5 (k ? 1,2,3,4,5) , 1 ? x6 ? 4 。 作代换 yk ? xk ? 1 (k ? 1,2,3,4,5) , y6 ? x6 ,从而有 (*)

r ?0



? (?1)
k ?0

n

k

k ? 2 2 n?2 k C 2 n ? k ? bn , 则bn ? a n ? a n ?1
n ?1



k n 又bn ? 2 2 n ? ? (?1) k ? 2 2 n ? 2 k C 2 n ? k ? ( ?1) k ?1

y1 ? y2 ? y3 ? y4 ? y5 ? y6 ? 15
其中 1 ? y k ? 4 (k ? 1,2,3,4,5,6) 。

(**)

k k ?1 n ? 2 2 n ? ? (?1) k ? 2 2 n ? 2 k (C 2 n ? k ?1 ?C 2 n ? k ?1 ) ? ( ?1) k ?1

n ?1

? 4a n ?1 ? ? (?1) j ? 2 2 ( n ?1) ? 2 j C 2j( n ?1) ? j
4 6
j ?0

n ?1

问题(**)的解数等于 ( x ? x ? x ? x ) 展开式中 x 15 的系数,由第一问知它等于 580
2 3

? 4a n ?1 ? bn ?1 .
于是由①式得 bn?1 ? an?1 ? an?2 , 从而推知an ? an?1 ? 4an?1 ? an?1 ? an?2 ,即an ? an?2 ? 2an?1 . 这说明{an}为等差数列,而 a0=1,a1=2,故公差 d=1,且 an=n+1 . 【说明】此题运用变换求和指标的方法,找出了 an,an-1,an-2 之间的线性关系式,再由 初始条件求 得 an.这种利用递推关系求组合数的方法,在解决较复杂的计算或证明组合恒等式时经常用到.

因为 5 种新式武器各不相同,互换位置得到不同的排列数,所以配备新式武器的方案数等于 580 ? 5!? 69600 。 注 本题为 2005 年浙江省预赛题改编 教师备注:由于本讲内容近年来考察较少,因此不安排过多题目,如内容不够可从习题中选择或适当 自行增加例题

大显身手
备选题: 求证:

? (?1)
k ?0

n

k

k ? 2 2 n?2 k C2 n ? k ?1 ? n ? 1.

k k k ?1 【分析】考虑到恒等式 C2 n?k ?1 ? C2 n?k ? C2 n?k ,仿例 2 解决.
n

, a2006 中有奇数个 9 的 2007 位十进制数 2a1a2a3 a2006 的个数为 1 1 2006 ? 82006 ) B. (10 2006 ? 82006 ) C. 102006 ? 82006 D. 102006 ? 82006 【答】 A. (10 ( 2 2 1 3 2005 【解析】 ( B )出现奇数个 9 的十进制数个数有 A ? C2006 92005 ? C2006 92003 ? ? C2006 9,
又由于 (9 ? 1)
2006 k k ? ? C2006 92006?k 以及 (9 ? 1)2006 ? ? C2006 (?1)k 92006?k ,从而得 k ?0 k ?0 2006 2006

14. 数码 a1 , a2 , a3 ,



【证明】令 a n ?

? (?1)
k ?0

k

k ? 2 2 n?2 k ? C 2 n ? k ?1 ,

k k k ?1 因为, C2 n?k ?1 ? C2 n?k ? C2 n?k ,

1 3 A ? C2006 92005 ? C2006 92003 ?

1 2005 ? C2006 9 ? (102006 ? 82006 ) 2

联赛班·第 1 讲·教师版

11

15. 证明:

?C C
k ?1 k n
n ?1

n

n ?1? k n

n ?1 ? C2 n
n ?1

由 a0 ? 0, a1 ? 1得A ? 的系数:
n ?1

1 2 15

,B ? ?

1 2 15

,

则 an ?

1 2 15

[(4 ? 15) n ? (4 ? 15) n ],

【解析】 考虑 (1 ? x)n ? (1 ? x)n 中 x 一方面 x

取 n ? 2k (k ? 0,1,2,?) ,由二项式定理得 的系数即为原式左边, 从而得证;

n?1 的系数即 (1 ? x) 的系数,即 C2 n ,
2n

另一方面, 利用二项式定理将 (1 ? x)n ? (1 ? x)n 展开并相乘, 得到 x 注 本题为例 6(2)的特例
n

an ?

1 2 15
1 n

1 3 n ?1 [2C n ? 4 n?1 ? 15 ? 2C n ? 4 n?3 ? ( 15) 3 ? ? ? 2C n ? 4 ? ( 15) n ?1 ]
n?2 2

(?1)k ?1 k n 16. 证明: ? Cn ? n ?1 k ?1 k ? 1 k ?1 n n n ?1 (?1) (?1)k ?1 k ?1 1 n?1 1 n k k k 1 k 【解析】 ? Cn ?? Cn?1 ? ( ? 1) C ? [ ? 1 ? C ? (?1)k Cn ? ? n ?1 n ?1 ?1 ] ? n ? 1 k ?2 n ?1 n ?1 k ?1 k ? 1 k ?1 n ? 1 k ?0
17. 数列 {an } 中, a1

? C ?4
1 2k

n ?1

?C ?4
3 n 3 2k

n ?3

? 15 ? ? ? C ? 4 ? 15
n n 2 k ?3

? C ?4

2 k ?1

?C ?4

2k k ?1 ? 15 ? ? ? C 2 k ? 4 ? 15

1 2 k ?1 3 2 k ?3 2 k ?1 ? C2 ? 15(C 2 ? ? ? C2 ? 4 ? 15k ?2 ) k ?4 k ?4 k

? 2k ? 4 2 k ?1 ? 15T

(其中T为整数),

? 3, an ? 3an?1 (n ? 2) ,求 a2001 的末位数字是多少?

由上式知当 15|k,即 30|n 时,15|an,因此数列 {an } 中有无穷多个能被 15 整除的项.

【解析】 先利用 n 的初值猜想 an 的特点与 an 的末位数字: 当 n=1 时,a1=3, a2 ? 3 1 ? 33 ? 27 ? 4 ? 6 ? 3
a

第四讲 抽屉原理与存在性问题
本讲概述
本讲我们将讲述组合数学中一个非常简单却又十分重要,应用十分广泛的一个原理,即抽屉原理. 然后我们将给出与抽屉原理内涵相通的几个变形,即平均值原理与图形重叠原理. 事实上这几个原理是用来证明存在性问题的有力工具之一,当然我们还可以利用极端原理、反证 法、数学归纳法、算两次、计数方法和构造法等等来加以证明.本讲我们主要讲述利用平均值原理(其 在整数和图形范围内的形式分别为抽屉原理和图形重叠原理)来证明存在性问题,并略举数例说明其 它方法在证明存在性问题中的应用.

a3 ? 3a2 ? 327 ? 34?6?3 ? (34 ) 6 ? 33 ? (81) 6 ? 33 ? (81) 6 ? 27 ,因此 a2 , a3 的末位数字都是 7,
猜想, an ? 4m ? 3, m ? N * . 当 n=k+1 时, ak ?1 ? 3
ak

现假设 n=k 时, ak ? 4m ? 3, m ? N * .

? 34m?3 ? (4 ? 1) 4m?3

0 4m?3 1 4m?2 4m?2 1 4m?3 0 ? C4 ? (?1) 0 ? C4 ? (?1)1 ? ? ? C4 ) 4m?2 ? C4 ) 4m?3 m?3 4 m?3 ? 4 m?3 ? 4 ? (?1 m?3 ? 4 ? (?1

? 4T ? 1 ? 4(T ? 1) ? 3, 从而完成了归纳论证. 所以对任意正整数 n, an ? 4m ? 3(m ? N*)
于是 an?1 ? 3
an

? 34m?3 ? (81) m ? 27. 故 a2001 的末位数字是 7.

m ?1 ] ? 1 个物件. n m 第二抽屉原理:若将 m 个物件放入 n 个抽屉中,则必有一个抽屉内至多有 [ ] 个物件. n
第一抽屉原理:若将 m 个物件放入 n 个抽屉中,则必有一个抽屉内至少有 [ 事实上这两个原理利用极端性原理与反证法极易证明,此处从略. 平均值原理 1:设 a1 , a2 ,..., an 为实数,且 A ? A,也必有一个不大于 A 平均值原理 2:设 a1 , a2 ,..., an 为正实数,且 G ? n a1 ? a2 ? ... ? an ,则 a1 , a2 ,..., an 中必有一个不小 于 G,也必有一个不大于 G 图形重叠原理: 把面积为 S1 , S2 ,..., Sn 的 n 个平面图形以任意方式放入一个面积为 S 的平面图形 A 内, (1) 如果 S1 ? S2 ? ... ? Sn ? S ,则必有两个图形有公共点;

注 本题中利用初值得到规律进而猜想 an ? 4m ? 3 是问题解决的关键. 在很多数学竞赛问题解决过程 中都需要对初值进行分析从中找出规律,这是对将来进行数学研究过程中解决未解决的数学问题的一 种必要训练. 18. 已知 a0 ? 0, a1 ? 1, an?1 ? 8an ? an?1 (n ? 1,2,?) 试问:在数列 {an } 中是否有无穷多个能被 15 整除的项?证明你的结论. 【解析】 数列 {an } 的特征方程为 x ? 8x ? 1 ? 0, 它的两个根为 x1 ? 4 ? 15, x2 ? 4 ? 15 ,
2

a1 ? a2 ? ... ? an ,则 a1 , a2 ,..., an 中必有一个不小于 n

所以 an ? A(4 ? 15) n ? B(4 ? 15) n

(n=0,1,2,?)

联赛班·第 1 讲·教师版

12

(2) 如果 S1 ? S2 ? ... ? Sn ? S ,则必有一点不属于上述 n 个图形中任意一个 可以发现,上述三组原理都是极端性原则在不同场合的具体表现形式 . 极端性法则是处理组合数 学中存在性的利器,通过对这三组原理及其解题技巧的深刻把握,我们也可以自己创造一些类似的极 端性原理来解决问题. 教师备注:本节题目有些可能学生在初中接触过,教师可以适当选择其中较有新意的问题.

(26){51}; ?? (50){99}。 从这 100 个数中任取 51 个数,也即从这 50 个抽屉内任取 51 个数,根据抽屉原则,其中必定至少 有两个数属于同一个抽屉,即属于(1)-(25)号中的某一个抽屉,显然,在这 25 个抽屉中的任何同 一个抽屉内的两个数中,一个是另一个的整数倍。 注 请注意本题是按照整数奇偶性质进行了巧妙的分类 【例32】 已给一个由 10 个互不相等的两位十进制正整数组成的集合。 求证: 这个集合必有两个无公共 元素的非空子集合,各子集合中各数之和相等. 10 【解析】 一个有着 10 个元素的集合有 2 =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 中的一切 公有元素,得出两个不相交的子集 A1 与 B1,很显然 A1 中各元素之和=B1 中各元素之和,因此 A1 与 B1 就 是符合题目要求的子集。 注 本题中不论抽屉构造方法,还是最后对集合 A,B 有公共情况的处理手法都非常巧妙,值得仔细体会 【例33】 试求最小的正整数 n, 使得对于任何 n 个连续正整数中,必有一数,其各位数字之和是 7 的倍 数. 【解析】 首先,我们可以指出 12 个连续正整数,例如 994,995,?,999,1000,1001,?,1005, 其中任一数的各位数字之和都不是 7 的倍数,因此, n ? 13 。 再证,任何连续 13 个正整数中,必有一数,其各位数字之和是 7 的倍数. 对每个非负整数 a ,称如下 10 个数所构成的集合: Aa ? {10a,10a ? 1, 10a ? 9}为一个“基 本段” ,13 个连续正整数,要么属于两个基本段,要么属于三个基本段。 当 13 个数属于两个基本段时,据抽屉原理,其中必有连续的 7 个数,属于同一个基本段;当 13 个连续数属于三个基本段 Aa ?1 , Aa , Aa ?1 时,其中必有连续 10 个数同属于 Aa . 现在设 ak ak ?1

例题精讲
利用抽屉原理解题的关键是根据题目特点巧妙地构造“抽屉” :将题目中涉及元素按照某一性质分 类,当取出足够多的元素时,即可断言必有某些元素属于同一个“抽屉”.构造抽屉的常用方法有:划 分集合、分割图形、利用剩余类等等.与抽屉原理相关的试题中,联赛中的题目往往利用抽屉原理是解 题的关键,但在冬令营级别的赛题中,往往抽屉原理只是其中的一小步或者利用它解决其中的小块问 题而已. 【例29】 将平面上的每个点都以红、蓝两色之一着色,证明:存在这样两个相似的三角形,它们的相 似比为 1995,并且每一个三角形的三个顶点同色。 【解析】 任取一点 O 为圆心,以 1,1995 为半径作两个同心圆,在内圆上任取 9 点,由抽屉原理知至少 有 5 点同色,记为 A 1 , A2 ,..., A 5 ,再设此五条半径与外圆交于 B 1 , B2 ,..., B5 ,由抽屉原理必有 3 点同色,设为 Bi , B j , Bk ,于是 ?Bi B j Bk , ?Ai Aj Ak 即为所求 注 本题为 1995 年全国联赛第 4 题 【例30】 在任意给出的 100 个整数中,都可以找出若干个数来(可以是一个数) ,它们的和可被 100 整除。 【解析】 设已知的整数为 a1,a2,?a100 考察数列 a1,a2,?a100 的前 n 项和构成的和数列 S1,S2,?S100。 如果 S1,S2,?S100 中有某个数可被 100 整除,则命题得证。否则,就有 S1,S2,?S100 均不能 被 100 整除,这样,它们被 100 除后余数必是{1,2,?,99}中的元素。由抽屉原理 I 知,S1,S2,?S100 中必有两个数,它们被 100 除后具有相同的余数。 不妨设这两个数为 Si,Sj(i<j) ,则 100 | SJ ? Si ? 100 | ai ?1 ? ai ?2 ? ... ? a j .命题得证。 注 本题所采用的这种利用连续项构造和式的方法非常经典 【例31】 从 1-100 的自然数中,任意取出 51 个数,证明其中一定有两个数,它们中的一个是另一个的 整数倍. 【解析】 把 1-100 的正整数分成如下 50 个抽屉(因为 1-100 中共有 50 个奇数) : 2 3 4 5 6 (1){1,1×2,1×2 ,1×2 ,1×2 ,1×2 ,1×2 }; 2 3 4 5 (2){3,3×2,3×2 ,3×2 ,3×2 ,3×2 }; 2 3 4 (3){5,5×2,5×2 ,5×2 ,5×2 }; 2 3 (4){7,7×2,7×2 ,7×2 }; 2 3 (5){9,9×2,9×2 ,9×2 }; 2 3 (6){11,11×2,11×2 ,11×2 }; ?? (25){49,49×2};

a1a0

ak ak ?1
k k i ?0 i i ?0

a1 (a0 ?1),
k i i ?0

ak ak ?1
i

a1 (a0 ? 6) 是属于同一个基本段的 7 个数,它们的各位数字之和分别是

? a , ? a ? 1, , ? a ? 6, 显然,这 7 个和数被 7 除的余数互不相同,其中必有一个是 7 的倍数.因
此,所求的最小值为 n ? 13. 注 本题为 2005 江西省预赛题.可以看到,在很多组合问题中,我们往往需要用到包括抽屉原理在内的 多种技巧才能最终解决问题. 【例34】 从前 25 个自然数中任意取出 7 个数,证明:取出的数中一定有两个数,这两个数中大数不超 过小数的 1.5 倍. 【解析】 把前 25 个自然数分成下面 6 组:

联赛班·第 1 讲·教师版

13

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 个数, 所以至少有两个数取 面第②组到第⑥组中的某同一组,这两个数中大数就不超过小数的 倍. 注 将题目中的 25,7 改为 91,10, 结论仍然成立.这就是基辅 49 届竞 事实上我们可以按照此题的思想自己设计一些类似的问题.

球 队 1

第 一 周 *

第 二 周 *

第 三 周

第 四 周

自 上 1.5 赛题,

【例37】 n 支球队要举行主客场双循环比赛(每两支球队比赛两场,各有一场主场比赛) ,每支球队在 一周(从周日到周六的七天)内可以进行多场客场比赛。但如果某周内该球队有主场比赛, 在这一周内不能安排该球队的客场比赛。如果 4 周内能够完成全部比赛,求 n 的最大值。 【解析】 (1)如右图所示:表格中有“*” , 表示该球队在该周有主场比赛,不能出访。 容易验证,按照表中的安排,6 支球队四周 可以完成该项比赛。 (2)下面证明 7 支球队不能在四周 完成该项比赛。设 Si (i ? 1, 2,3, 4,5,6,7) 表示 i 号球队的主场比赛周次的集合。假设 4 周内 能完成该项比赛,则 S i 是{1,2,3,4}的非空真子集。 一方面由于某周内该球队有主场比赛,在这一周内不能安排该 球队的客场比赛,所以 Si (i ? 1, 2,3, 4,5,6,7) 中,没有一个集是另一个的子集。 另一方面,设 A ? ?{1},{1,2},{1,2,3}?, B ? ?{2},{2,3},{2,3,4}?, C ? ?{3},{1,3},{1,3,4}?

* * 【例35】 (1)任选 6 人,试证其中必有 3 人,他们互相认识或都不认 2 3 * * 识. (2) 17 名科学家中每两名科学家都和其他科学家通信,在 4 * * 他们通信时,只讨论三个题目,而且任意两名科学家通信 5 * * 时只讨论一个题目,证明:其中至少有三名科学家,他们 6 * * 相互通信时讨论的是同一个题目。 【解析】 (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 条同色,不妨记为 AB1,AB2,AB3,AB4,AB5, AB6 同红色,若 Bi(i=1,2,?,6)之间有红线,则出现红色三角线,命题已成立;否则 B1,B2,B3, B4,B5,B6 之间的连线只染有黄蓝两色。 考虑从 B1 引出的 5 条线,B1B2,B1B3,B1B4,B1B5,B1B6,用两种颜色染色,因为 5=2×2+1,故必有 3=2+1 条线段同色,假设为黄色,并记它们为 B1B2,B1B3,B1B4。这时若 B2,B3,B4 之间有黄线,则有黄 色三角形,命题也成立,若 B2,B3,B4,之间无黄线,则△B2,B3,B4,必为蓝色三角形,命题仍然成 立。 注 这是著名的图论入门问题,二染色或三染色时的处理方式其实是相同的. 【例36】 任意给定 10 个自然数,试证明:可以用减,乘两种运算以及括号将它们适当连结起来,其结 果可被 1890 整除. 【解析】 1890 ? 2 ? 3 ? 5 ? 7 ,设给定自然数为 a1 , a2 ,..., a10 ,先按模 9 的剩余类来分成 9 个抽屉,必
3

D ? ?{4},{1,4},{1,2,4}?, E ? ?{2,4}?, F ? ?{3,4}? 由抽屉原理,一定存在
i, j, i ? j, i, j ?{1, 2,3, 4,5} , 必有 Si ? S j 或 S j ? Si Si , S j 属于同一集合 A 或 B 或 C 或 D 或 E 或 F,
发生. 所以,n 的最大值是 6. 注 本题为第一届东南数学奥林匹克第 7 题. 本题是一道组合极值问题,组合极值的构造与论证难度一 般都很大,而抽屉原则在组合极值的论证中常常用到. 【例38】 从 4 个同心圆的圆心出发的 100 条射线等分各圆周,分别与 4 个圆各有 100 个交点,任意给 每个圆上的点染上黑白两色之一,使每个圆上都恰有 50 个黑点和 50 个白点,证明:可将此 4 个圆适当旋转,使这 100 条射线中至少存在 13 条射线,它们中每一条穿过的 4 个点颜色都 相同. 【解析】 称某个圆顺时针旋转

2? 为旋转一次,并由里到外称 4 个圆为圆 1,圆 2,圆 3,圆 4. 100

有两个在同一抽屉,其差可被 9 整除,不妨设为 9 | a10 ? a9 , 同理可得到 7 | a8 ? a7 ,5 | a6 ? a5 ,3| a4 ? a3 ,最后,若 a1 , a2 中有一个为偶,那么 2 | a1 ? a2 , 否则 2 | a2 ? a1 ,将上述 5 式连乘起来即可
联赛班·第 1 讲·教师版

固定圆 1,任取圆 1 上某点 A,有 100 种取法,不妨设它为黑; 此时,旋转圆 2,其中有 50 次与点 A 颜色相同,任取其中一点 B,固定圆 2,再旋转圆 3,如 此下去,一共旋转了 100 ?100 ?100 次, 共出现同色四点组 ( A, B, C , D) 有100 ? 50 ? 50 ? 50 个,

100 ? 50 ? 50 ? 50 ? 12.5 个同色四点组, 100 ?100 ?100 根据平均值原理,必在某次旋转后存在 n ? 12.5 ? n ? 13 条射线,它们中每一条穿过四点同
平均每次出现 色.

14

大显身手
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)

方法来构造“抽屉” 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 份,其中必有一份

?
根据平均原则,至少有一个括号内的三数和不少于 17,即至少有三个相邻的数的和不小于 17. 20. 在边长为 1 的等边三角形内(包括边界)有任意五个点(图 1) 。证明:至少有两个点之间的 距离不大于

180 ? 23 8

23. 15 个人围着圆桌坐下,圆桌上有 15 个人的名牌,但是大家是随意坐的,坐下以后才发现没 有一个人与桌上的名牌相对应,证明:可以转动圆桌,使得至少两个人与他们的名牌相符 【解析】 每个人都可以转动圆桌使得自己与名牌相符,但是转动只有 14 种,15 个人中必有两个人的 转动方式相同,从而得证.

1 . 2

【解析】 顺次连接三角形三边中点,即三角形的三条中位线,可以分原等边三角形为 4 个全等的边长

1 为 的小等边三角形,则 5 个点中必有 2 点位于同一个小等边三角形中(包括边界) ,其距 2 1 离便不大于 . 2

第五讲 容斥原理与极端性原理
本讲概述
本讲我们讨论组合数学中两个非常重要的原理:容斥原理与极端性原理. 注:为了让大家在寒假班能够对组合数学有一个概貌了解,本讲与下一讲都安排了两个论题,但 这两个论题的联系并不大. 当我们试图对某些对象的数目从整体上计数碰到困难时,考虑将整体分解为部分,通过对每个部 分的计数来实现对整体的计数是一种明智的选择.将整体分解为部分也就是将有限集 X 表示成它的一 组两两互异的非空真子集 A1,A2,?An 的并集,即 X ? A1 ? A2 ? ? ? An .集合? ? {A1 , A2 ,?, An } 叫做集合 X 的一个覆盖.一个特殊情况是,集族 ? 中的任意两个集合都不相交,这时我们称集族 ? 为集 合 X 的一个(完全)划分.如 ? 为集合 X 的划分,则对集合 X 的计数可通过熟知的加法公式

注 (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)这里是用等分三角形的方法来构造“抽屉”。类似地,还可以利用等分线段、等分正方形的

| X |?| A1 | ? | A2 | ? | A3 | ??? | An |
进行,但是,要找到一个划分并且其中所有子集易于计数的有时并非易事. 而容斥原理就是涉及 到 n 个集合的计数问题最常用的解决方法; 容斥原理相关知识如下: 相对补集:称属于 A 而不属于 B 的全体元素,组成的集合为 B 对 A 的相对补集或差集,记作 A-B.

联赛班·第 1 讲·教师版

15

容斥原理:以 A 表示集合 A 中元素的数目,对 n 个集合 A 1 , A2 ,..., An ,我们有 定理 1 设 Ai (i ? 1,2,?, n)为有限集 ,则

∴93-4=89 即不超过 120 的合数共有 89 个。 注 card(A)就是 A ,表示集合 A 中元素的数目

| ? Ai |? ?| Ai | ?
i ?1 i ?1

n

n

1?i ? j ? n

?

| Ai ? A j | ? ? ? (?1) n?1 | ? Ai |
i ?1
n n n

n

定理 2 设 Ai (i ? 1,2,?, n) 为有限集 I 的子集,则 | ? Ai |?| ? Ai |?| I | ? | ? Ai |
i ?1 i ?1 i ?1

【例40】 某班对数学、物理、化学三科总评成绩统计如下:优秀的人数:数学 21 个,物理 19 个,化 学 20 个,数学物理都优秀 9 人,物理化学都优秀 7 人。化学数学都优秀 8 人。这个班有 5 人任何一科都不优秀。那么确定这个班人数以及仅有一科优秀的三科分别有多少个人。 【解析】 设 A={数学总评优秀的人} B={物理总评优秀的人} C={化学总评优秀的人} 则|A|=21, |B|=19, |C|=20,

?| I | ?? | Ai | ?
i ?1

n

1?i ? j ? n

?

| Ai ? A j | ? ? ? (?1) n | ? Ai |
i ?1

n

实际上,容斥原理的问题我们在小学和初中曾经就多次接触过,只不过没有明确提出这个概念以 及它的一般形式. 而极端性原理则是一种非常重要的数学思想. 从问题的极端情况考虑,对于数值问题来说,就是 指取它的最大或最小值(例如数集中的最大值,获胜场数最多的队员,图形中的最大面积等) ;对于一 个动点来说,指的是线段的端点,三角形的顶点等等。极端化的假设实际上也为题目增加了一个条件, 求解也就会变得容易得多;

这表明全班人数在 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 合作过的人的集合。同样地,

【例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 是质数

。 所以存在 。则 A、B、C、D 就是所求,证毕。

注 本题为一道典型的图论问题,我们用容斥原理的方法来解决它 【例42】 将与 105 互素的所有正整数从小到大排成数列,试求出这个数列的第 1000 项。

联赛班·第 1 讲·教师版

16

【解析】 首先计算 S ? {1, 2,...,105} 内与 105 互素的整数个数, 由容斥原理, 令 Ai ? {m | m ? S , i | m} , 于 是

利用容斥原理。设在 ( x1 , x2 ,......,x2 n ) 中, k 与 k ? n 相邻的排列的集合为 Ak , k ? 1,2,3,...n

? 易知每 105 个数里有 48 个与 105 互素,而 1000 ? 48 ? 20 ? 40 ,所以 a1000 ? a40 , 3
由 a48 ? 104, a47 ? 103, 接下来是 101,97,94,92,89,88,86 知 a1000 ? a40 =86 注 本题为 1994 年联赛二试题

A3

?1

1



A5

可以计算出 (事实上将 k , k ? n 这两个相邻的数放在一起则 A | Ak |? 2 ? (2n ? 1)!. 0 ? A 5 ? k7 中的元素可以

0

5

5

?

7

看成 2n ? 1 个元素的全排列,另外 k , k ? n 可互换位置。即得 | Ak |? 2 ? (2n ? 1)!. ) 同理 | Ak ? Aj |? 22 ? (2n ? 2)!,1 ? k , j ? n, k ? j. 则 | B |?

【例43】 一个人写了 n 封不同的信及相应的 n 个不同的信封,他把这 n 封信都装错了信封,问这样的 装法有多少种? 【解析】 先把 n 个不同的元素及相应的位置都编上序号 1,2,…,n,并且约定:在 n 个不同元素的 排列中 1° 若编号为 i(i=1,2,…,n)的元素排在第 i 个位置,则称元素 i 在原位;否则称元素 i 不在原位. 2° 若所有的元素都不在原位,则称这种排列为 n 个不同元素的一个错排(若每个元素都在原位则 称为序排). 按照上面约定,“装错信封问题”即为 n 个不同元素的错排问题,则可构建“装错信封问题”的数学 模型为:在 n 个不同元素的全排列中,有多少种不同的错排? 记 S 为全排列构成的集合, Aj 为 j 在原位的所有排列所构成的集合, 易知|S|=n! ,|Ai|=(n-1)! ,|Ai∩Aj|=(n-2)! ,…, 从而由容斥原理,错位排列数 Dn ?| S | ?

?| A
k ?1

n

k

|?

1? k ? j ? n

?| A

k

2 ? A j |? n ? 2 ? (2n ? 1)!?Cn ? 2 2 ? (2n ? 2)!

? (2n)!?2n(n ? 1) ? (2n ? 2)! ? 2n ? n ? (2n ? 2)! ? 2n ?
结论得证。

2n ? 1 1 ? (2n ? 2)! ? ? (2n)!. 2 2

板块二

极端性原理

?| Ai | ?
i ?1

n

1?i ? j ? n

?

| Ai

Aj | ?

? (?1)n |

n i ?1

Ai |

1 2 3 n ? n!? Cn ? (n ?1)!? Cn ? (n ? 2)!? Cn ? (n ? 3)!? ... ? (?1)n Cn ? (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。

? n !(1 ?

1 1 1 (?1) n ? ? ? ... ? ) 1! 2! 3! 3!

注 本题为“装错信封问题”,是由著名数学家约翰· 伯努利(Johann Bernoulli,1667-1748)的儿子丹尼 尔· 伯努利(Danid Bernoulli,1700-1782)提出来的,是一道典型的利用容斥原理或递推方法来解决的问 题.

2n} 的一个排列 ( x1 , x2 ,......,x2n ) 具有性质 P 是指:存 【例44】 设 n 是正整数,我们说集合 {1,2,3,......,
在i 属于集合 {1,2,....,2n ? 1}使得 | xi ? xi ?1 |? n 。求证,对于任何 n ,具有性质 P 的排列比不具有性质 P 的排列数多. 【解析】 只需要证明具有性质 P 的排列数超过全排列数一半. 设 A 为不具有性质 P 的排列的集合,B 为具有性质 P 的排列的集合,显然 | A | ? | B |? (2n)! 为了 | A |?| B |, 只需证得 | B |?

【例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 所学校的人数为 n ? 1 ? k ? 1 ,即 A 至少认识第三所学校校的一名学生 C. 如果 c 认识第二所学校的某学生 B,那么 A,B,C 互相认识,命题成立;否则 C 认识第二 所学校的学生至多为 n-k,从而 c 认识第一所学校的学生人数至少为 n ? 1 ? (n ? k ) ? k ? 1 ,此与 k 的 最大性假设相违.从而原命题得证

1 (2n)!. 2

联赛班·第 1 讲·教师版

17

注 本题实际是一道图论问题 【例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 是已 赛过对手最多的选手矛盾。 故一定存在可去选手。

x1 ? x2 ? x3 ? x4 ? x5 ? x6 ? 20
其中 2 ? xk ? 5 (k ? 1,2,3,4,5) , 1 ? x6 ? 4 . 作代换 yk ? xk ? 1 (k ? 1,2,3,4,5) , y6 ? x6 ,从而有

(1)

y1 ? y2 ? y3 ? y4 ? y5 ? y6 ? 15
其中 1 ? y k ? 4 (k ? 1,2,3,4,5,6) .

(2)

设 A 为不定方程(2)的正整数解的全体, Ak (k ? 1,2,3,4,5,6) 为 A 中满足 y k ? 4 的解的全体.因为没 有同时满足 yi ? 4 , y j ? 4 , y k ? 4 的的正整数组满足不定方程(2) ,所以 Ai 据容斥原理,可得
6

Aj

Ak ? ? ,根

大显身手
24. 三对夫妻站成一行,每对夫妻都不相邻的排法有多少种? 【解析】 记 I ? 3对夫妻的全排列 .

Ak ? A ?

6 k ?1

k ?1

Ak ? A ? ? Ak ? ? Aj
k ?1 j ?k

6

Ak

? Ai ? ?第i对夫妻相邻的全排列? , i ? 1, 2,3 .
A1 A2 A3 ? A1 A2 A3 ? I ? A1 A2

?

5 5 2 5 ? C14 ? 6C10 ? C6 C6 ? 2002? 1512? 90 ? 580 .

由容斥原理

因为 5 种新式武器各不相同,互换位置得到不同的排列数,所以配备新式武器的方案数等于 580 ? 5!? 69600 . 注 本题在计数部分做过,此处我们利用容斥原理来解决 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 个小朋友,每两个小朋友之间的距离都不相同,每个小朋友手上都拿着 一把水枪。当发出射击的命令后,每人用枪射击距离他最近的人。问:射击后有没有一个小
联赛班·第 1 讲·教师版

A3

1 2 3 ? 6!? C3 ? 2 ? 5!? C3 ? 22 ? 4!? C3 ? 23 ? 3!=240 种.

25. 在不大于 10 的正整数中,有多少个数至少可被 3,5,7 之一整除? 【解析】 应用容斥原理可得到

6

A ? 333,333 ? 200,000 ?142857 ? 66666 ? 28571 ? 47619 ? 9523 ? 542857
26. (2005 年浙江省预赛试题)在一次实战军事演习中,红方的一条直线防线上设有 20 个岗位. 为了 试验 5 种不同新式武器,打算安排 5 个岗位配备这些新式武器,要求第一个和最后一个岗位不配备新 式武器,且每相邻 5 个岗位至少有一个岗位配备新式武器,相邻两个岗位不同时配备新式武器,问共 有多少种配备新式武器的方案? 【解析】 设 20 个岗位按先后排序为 1, 2, , ?, 20, 且设第 k 种新式武器设置的序号为 ak (k ? 1,2,3,4,5) . 令 x1 ? a1 , x2 ? a2 ? a1 , x3 ? a3 ? a2 , x4 ? a4 ? a3 , x5 ? a5 ? a4 , x6 ? 20 ? a5 ,则 有

18

朋友身上是干的?为什么? 【解析】 设 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 的线段。

联赛班·第 1 讲·教师版

19

【解析】 在平面上作有公共底边 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 同色,图中有三个正三角形)证明"若平面上有两个 异色的点距离为2,那么必定可以找到符合题意的三角形".只需再找长为2端点异色的线 段.以O(白色)为圆心,4为半径作圆.如圆内皆白点,问题已证.否则圆内有一黑点P, 以OP为底作腰长为2的三角形OPR,则R至少与O、P中一点异色,这样的线段找到.

【例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 讲·教师版

20

明理由。 【解析】 (1)奇数. 黑板上开始时所有数的和为 S=1+2+3+?+1998=1997001, 是一个奇数, 而每一次 “操作” , 将 (a+b) 变成了(a-b) ,实际上减少了 2b,即减少了一个偶数.因为从整体上看,总和减少了一个偶数,其奇偶 性不变,所以最后黑板上剩下一个奇数. 注:另一个不变量:奇数的个数之奇偶性不变,也可以完 成本题 (2)要把三堆石子都取光是不可能的。 按“操作”规则,每次拿掉的石子数的总和是 3 的倍数,即不改变石子总数被 3 除时的余数。而 1998+998+98=3094,被 3 除余 1,三堆石子被取光时总和被 3 除余 0。所以,三堆石子都被取光是办 不到的。 注 本题为操作问题的一个非常重要的解决方法:寻找不变量,以什么量为不变量是问题的关键 【例58】 已知三个数 2, 2,

个 1?1 的瓷砖即可铺满整个地板,同学们不妨自行构造之 2、按照本题的思想来对方格表染色可以证明很多高难度的 IMO 组合问题,同学们可自行查阅相关资 料 31. 中国象棋棋盘上的马按日字型跳动,试证明:它跳回原处一定经过了偶数步. 【解析】 将棋盘上交叉点按照黑白相间染色,则马每次必调到异色点上,故必经偶数步才能跳回同色 点上. 32. 由 4 个 1x1 的正方形组成一个 L 形,用若干个这样的 L 形无重叠地拼成一个 m ? n 的矩形, 试证明 8 | mn 【解析】 显然 4 | mn ,不妨设 m 为偶,并将 m ? n 矩形横置,从左到右共 m 列间隔地染成红色列与蓝 色列,注意到不论 L 形如何放置,总可以归结成两大类:3 红 1 蓝或者 3 蓝 1 红;设两类分 别为 a,b 个,由于红蓝方格数恰相等,即有 3a ? b ? 3b ? a ? a ? b 这说明矩形中共 8a 个方格,证毕 33. 已知两人坐在一张长方形桌子旁,相继轮流在桌子上放入同样大小的硬币。条件是硬币一定 要平 放在桌子上,后放的硬币不能压在先放的硬币上,直到桌子上再也放不下一枚硬币为止。谁放入了最 后一枚硬币谁获胜。问:先放的人有没有必定取胜的策略? 【解析】 如果桌子大小只能容纳一枚硬币,那么先放的人当然能够取胜。然后设想桌面变大,注意到 长方 形有一个对称中心,先放者将第一枚硬币放在桌子的中心,继而把硬币放在后放者所放位置的对称位 置上,这样进行下去,必然轮到先放者放最后一枚硬币。 34. 是否在平面上存在这样的 40 条直线,它们共有 365 个交点? 【解析】 先考虑一种特殊的图形:围棋盘。它有 38 条直线、361 个交点。我们就从这种特殊的图形出 发,然后进行局部的调整。

1 a ?b a ?b ,任取其中两数 a,b(a>b),并用 代替 a,b,问能否经过有限 , 2, 2, 2,

步,使三个数变成 1, 2,1 ? 2 ? 【解析】 我们发现在操作过程中三数平方和是不变量,而前后平方和不等,故不可能. 【例59】 正 25 边形的顶点上顺时针放置数字 a1 , a2 ,..., a25 ,其中

a1 ? a2 ? ... ? a13 ? 1, a14 ? a15 ? ... ? a25 ? ?1 ,
做变换 (a1 , a2 ,..., a25 ) ? (a1 ? a2 , a2 ? a3 ,..., a25 ? a1 ) ,如此 100 次之后,证明必出现一个大于 10 的
20

数 【解析】 考 察 和 S ? a1 ? a 2 ? ... ? a 2 5, 第 一 次 操 作 后 S ? 24 , 以 后 每 次 增 大 一 倍 , 第 100 次 后

S ? 24 ? 299 , 24 ? 299 ? 1020 于是必有一个数 ai ? 25
【例60】 设圆周上放若干堆小球, 每堆中小球都是 3 的倍数, 但各堆小球数不必相等.现按如下规则调 整各堆球数:把各堆小球 3 等分,本堆留一份,其余两份分别放入左右两堆中,如某堆不是 3 的倍数,则从袋子中取出一球或两球放入使得该堆球数保持为 3 的倍数,如此进行下去, 问能否经过有限次调整使得各堆球数相等? 【解析】 设某次调整前球数最多的为 3m 个,最少的为 3n 个,且 m>n,那么易证如下结论: (1)调整后各堆球数仍在 3m 到 3n 之间; (2)原来球数>3n 的,调整后仍然>3n; (3)原来球数=3n 的,调整后至少其中一堆球数>3n, 取目标函数 f = 3m – 3n, 显然 f 将严格递减,这个差数将在有限步内减少到 0

大显身手
30. 可否只用 2 ? 2,3 ? 3 的瓷砖铺满 23 ? 23 的地板(不允许重叠,也不留缝隙). 【解析】 将 23 ? 23 的地板中第 1,4,7,…,19,22 列中的小方格染成黑色,其余各列染成白色,易知这样 的染法下每块瓷砖覆盖的白色方格数总是偶数,但白色方格总数为奇数,这就导致了矛盾. 注 1、可以构造一种方法,使得用 2 ? 2,3 ? 3 的瓷砖可铺满 12 ? 11 的地块,再用 4 个这样的地块和一

先加上 2 条对角线,这样就有 40 条直线了,但交点仍然是 361 个。再将最右边的 1 条直线向右平 移 1 段,正好增加了 4 个交点(见上图) 。于是,我们就得到了有 365 个交点的 40 条直线。 注 解这类问题的方法是首先给出一个尽量接近要求数量的构造,然后再逐步调整. 35. 在黑板上写上 3 个整数,然后将其中一个擦去写上另外两数之和与 1 的差,如此进行下去最 后得到了 (17,1999, 2105) ,问一开始黑板上的数可否为(1) (2, 2, 2) (2) (3,3,3) 【解析】 (1) (偶,偶,偶)->(偶,偶,奇)->(偶,偶,奇)->?,而不能变到(奇,奇,奇) ,所 以不可能. (2) 有可能,由 (17, a, a ? 16) ? (17, a ? 16, a ? 2 ?16) 知只需

(17,31, 47) ? (15,17,31) ? (3,15,17) ? (3,13,15) ? (3,11,13) ? (3,9,11) ? (3,7,9) ? (3,5,7) ? (3,3,5) ? (3,3,3)

联赛班·第 1 讲·教师版

21

联赛班·第 1 讲·教师版

22


数学竞赛讲义组合计数

数学竞赛讲义组合计数_学科竞赛_高中教育_教育专区。数竞必备,组合计数 数学竞赛讲义 第一讲 组合计数本讲概述组合数学是竞赛中最重要的一个板块,也是变化最多,最...

数学竞赛讲义:排列与组合

数学竞赛讲义:排列与组合【赛点直击】一、两个基本原理 加法原理 设 A 为完成...×mn;使用乘法原理的关键在于对所计数的对象进行完全分步. 二、相异元素的排列...

高二数学竞赛班讲义 第一讲 组合计数

高二数学竞赛讲义 第一讲 组合计数_学科竞赛_高中教育_教育专区。高二数学竞赛班二试 第一讲一、知识要点: 组合计数与极端原理班级 姓名 1.定理 1(容斥原理)...

数学竞赛讲义组合7-21

数学竞赛讲义组合7-21_学科竞赛_高中教育_教育专区。第七讲 组合综合问题本讲概述...i ,记数 高一·联赛班·寒假第 7 讲·教师版 4 a2 ?a1 表? ? f (a1...

数学竞赛讲义组合1-6

数学竞赛讲义组合1-6_学科竞赛_高中教育_教育专区。全国高中数学联赛组合讲义数学竞赛讲义 1-6 讲 第一讲 组合计数(1)本讲概述组合数学是竞赛中最重要的一个板块...

高中数学竞赛讲义(十三)──排列组合与概率

高中数学竞赛讲义(十三) ──排列组合与概率 一、基础知识 1.加法原理:做一件事有 n 类办法,在第 1 类办法中有 m1 种不同的方法,在第 2 类办 法中有 ...

高中数学竞赛讲义(13)排列组合与概率

高中数学竞赛讲义(13)排列组合与概率_学科竞赛_高中教育_教育专区。高中数学竞赛讲义(十三) ──排列组合与概率 一、基础知识 1.加法原理:做一件事有 n 类办法...

计数问题竞赛讲义一

初中数学竞赛辅导资料(25)... 4页 免费喜欢...计数问题竞赛讲义一一.分类加法计数原理与分步乘法计数...B 图2-1 图2-2 A 图2-3 1 二.排列与组合 ...

数学竞赛教案讲义(18)——组合

数学竞赛教案讲义(18)——组合 暂无评价|0人阅读|0次下载|举报文档 第十八章 组合 一、方法与例题 1.抽屉原理。 例 1 设整数 n≥4,a1,a2,?,an 是区间(...