高一数学联赛辅导5179寒假讲义上

第一讲组合计数的学科.解决竞赛中的组合数学问题往往不需要太多专门的知识求深刻的洞察能力和强大的化归、转化能力.IMO中，最后的胜者往往是成功从本讲开，用七讲对组合学做一大的勾勒.通这七讲学习，到以下的：1掌握联赛一二试组合问题的特点与解法；2、对组合数学这门学科有一个初步的认识，为进一步学习打下基础；3七讲内容分别为：一、组合计数（1）比高考略难的基本计数问题 1n1n类分别有m1m2mnnn法，则总共完成这件事有mim1m2mn种方法n1n步分别有m1m2mnnn完成这件事有mim1m2mn种方法.易于计数2

nn(n1(n2...21nnnnmAm（部Pm，由乘法原理得到nnnAmn

(n

n(n1)...(nmnn n(n1)...(nm (nm)!Cn(nm)! nm个元素排成一列，不同的排列种数有nm有限个重复元素的全排列：设n个元素由ka1a2akn1n2nk（nn...

n，那么这n个元素的全排列数

n!n!...n nmnm（i）（ii）（iii）同或者元素虽然相同，但元间的顺序不同，才是不同的圆排列．AmAAa1a2a3an}的nmnm板块一本的加法、乘法原理，以及枚举方法来计数.这主要是考虑到有一部分参加联赛的同学并过专业的竞赛训练.虽然如此，这部分计数问题枚举起来往往分类复杂，需要仔细.【例1 C. （2）B前排中间的3个座位不能坐，有排法A2，其中相邻的分三类，排的其中的4个座位有3A2；则符合 件的排法种数中A23A23A211A2=346，故选 11A2=11011346【例2（1）36【解析】（1）900003前四位除以3余21,4,7931749630000-17496=12504个（2）显然全部子集数为2100个，不包含任何奇数的子集即{24,6,...,98,100}的子集共有250个，故所求子集个数为2100250个.(n元集合子集数为2n个)【例3ABCDEFA处，它每次可随意地跳到相邻两顶点之一．若5D5D5次也停止跳动，那么这只青蛙从开始到停止，可能出现的不同跳法共种1，2,4次到达D点，于是青蛙的跳法只有以下两种：3D253次有232种，后两次有222426种跳法注1997【例4】从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色。则不同的染色方法共有 种（注：如果我们5555种6565种颜色有C5种方法，这时必有一组对面同色.565取一种颜色染一组对面，并将它们朝上和朝下，有C14种颜色染四个侧面（45颜色的链排列）13！种方法.所以不同的染色方案有C5C113!90种 56644余两种颜色染四个侧面且使两组对面同色（应是两种不同颜色的链排列1种方法.所以不同的染色方案有C4C2190种. 6363种颜色有C3661种方法.所以不同的染色方案有C3120种.6注本题为1996年联赛试题是来一试计数问题中最复杂的一道其背景与群论计数原理有关，【例5】将24个名额分配给3个学校，则每校至少有一个名额且各校名额互不相同的分配方法共 ||43||||若把每个“”与每个“|”都视为一个位置，由于左右两端必须是“｜”，故不同的分配方法相当于24226个位置（两端不在内）2个“｜”占领的一种“占位法“每校至少有一个名额的分法”24个”232个空隙插入“｜”C2253C又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”31种．253－31＝222种． x1x2x324x1x2x321321个元素的可HCHC

又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”31种．253－31＝222种2008【例6】将2个a和2个b共4个字母填在44方格表内，每个小方格内至多填1个字母，若使相同字 b72种；2a1bC1A2=16×72722−72−16×72=396016200712【例7】设三位数nabc，若以a，b，c为三条边的长可以构成一个等腰（含等边）三角形，则这样的三位数n有（ A.45 B.81 C.165 D.216a，b，c0。即a,bc{1nnC19 99必须满足ba2ba987654321b1111203同时，每个数码组（a，b）中的二个数码填上三个数位，有C23nC2(2C2206(C210156。nnn165 2004板块二

N.N的元素个数.【例8】（1）试用对应方法证明可重组合：从n个不同元素中，任意可重复地选取m个元素，称nm（2）xx

n（k,n为正整数）的非负整数解组数为

【解析】（1）设n个元素为12n，并设取出的m个元素为1a1a2amn，于是1a10a21amm1nm1(a1a2ama10a21amm1后者为从nm1m

（2）nk-1个竖线排成一排，k-1n个圆圈依次分成k个部分：x1x2xk，n+k-1k-1个的全排列数为列数为

，故得证】【解析】任一形内交点对应两条对角线l,m;P,P（l,m）2顶点，n4顶点即可唯一确定两对角线，于P(lm)(A,B,C,D)nn注本题为组合数学一个重要分支——组合几何中的非常重要的一个结论，可以利用它解决一些高难度的n个元素排成一行依次为为12nk个元素为1i1i2ikn，显然有2ij1ij(j12k1；

1i1i21i32ikk1nk1(i1i21i32,...,ikk11,2，n-k+1中的一个严格上升的序列作对应(i1i2,...,ik)(i1i21i32,...,ikk1，易证明它为一一对应，且后者的种数为从nk1个元素中取k

16（1）100631C1C B．C1C6 6

D．D．（2）从4名男生和3名中选出4人参加某个座谈会，若这4人中必须既有男生又有，A.140 C35 【解析】（1）C3件产品有C3种方法，其中无次品有C31件次品的方法数为

C3

（2）D既有又有男生，可以分类表示，三男一女有C3C1种选法，二男二女有C2C2种 4一男三女有C1C3种选法，则总的不同的选法有C3C1C3C2C1C3=34( 由三个数字12、3组成的5位数中,1、2、3都至少出现1 【解析】在5位数中,若1只出现1

C1(C1C2C370 若1

C2(C1C260若1只出现3

C3C1

15015055对ab的个数为 D. 【答】 1b【解析】由5xa0xa；6xb0xb。要使ABN2,3,4，则 ， 4 6b20a

。所以数对ab共有C1C130

66 aT,

2005

5

6

5p p

6

1

0

1

0 【解析】用

]k位p进制数，将集合M中的每个数乘以74M{a73a72a7a|aT,i1,2,3,4}{[aaaa]|aT,i1,2,3, 1234 M中的最大数为[6666]72400]10而

,将此数除以74M1

0

4.C2005A={a1,a2,…,a100}B={b1,b2,…,b50}ABfB中每个元素

C50

50

49CC

49CCb1<b2<…<b50A中元素a1a2,a10050f：A→B，i组的元素在fbi(i=1,2,…,50)，易知这样的f满足题设要求，每个这样的分fA50组的CCA的分法数为C49，则这样的映射共有C49D 注本题为2002 联赛试在赛前，F国为了A1,A2,…,A7这七名，准备让他们在三场训练比赛(每场90分钟)A1,A2,A3,A4每人上场 7|xi(1≤i≤4)13|xj(5≤j≤7)下的正整数解的级数。 xi xj ∴m,n 在条件m≥4且n≥3下的一组正整数解 10∵7(m-4)+13(n-令m′=m n′=n3 m≥4n≥3 即 n0=203是③的整数m′=406 n′= 令 n′≥0,解得 20mn

mn

mnmn

m

mn

xi=7yi(i=1,2,3,4)，于是由不定方程y1+y2+y3+y4=33有

34960∴此时①有满足条件的C3=4960 y1+y2+y3+y4=20，有C3y5+y6+y7=10，有C2 ∴此时①有满足条件的C3C2=34884 由y1+y2+y3+y4=7，有C3组正整数解；以及y5+y6+y7=17，有C2组正整数解 40 5020028

第二讲组合计数 二项式定理(xy)nCkxnkyk(1x)nCkxk，其中nN特征方程与数列通项

k

kaaa,...为数列{a}

qan1x2pxq

（1）当有两互异实根时，数列通项为anxx （2）当有二等根时，数列通项为ann)1n1其中板块一算两次是一种非常重要的思想方法，在代数、组合、几何中都有涉及.组合问题中，组合极值、组合不等式也常常涉及到算两次.组合计数中，在直接计算非常复杂甚至无从入手时，我们常常利用算两次方我们就得到一个等式，当为估计式时，我们就得到一个不等式.事实上，数学中有相当大一部分定理就是 【例11】a1a2,…an1，2，…，nfk是集合aiaiak,ikgk是集合aiaiak,ik元素的个数（k12,…n，证明fkgk k k 【解析】考虑集合S(aiakaiak,ikS。一方面，固定k先对i求和，然后再对k

fk；另一方面，固定i先对k求和，然后再对i

gigkn kn 所以得fkgk

kk k注本题只是为了说明算两次的基本思想和方法，这里的计数是抽象的，这种方法相当于考虑各个分量对【例12】nn（1）S，Sn=8S28C2，于是猜想对一般情形总有SC2n 本题构造了一种巧妙的对应，使原来无法下手的问题变得有章可循.事实上，组合问题，特别是算两次【解析】设一共连有lk个三角形 一方面，所得k个三角形的内角和为k

个内点及

，从而算得k3k条边，另一方面，每条线段是两个三角形的公共边，1次，共2l4条边，从而2l43k，得到l3001注本题的背景是计算机图形学中著名的三角面片分划问题，这类问题在冯的有限元中也有应用.【例14】（选讲）1,1,2,2,3,3，…，1986,1986112219861986【解析】设能将上述数字排成一行满足题设，这是每一个数i(1i1986可赋予它一对有序实数(xi,yi)作为坐标，这里坐标值分别为它第一次与第二次出现的位置序号.yixii1.

k

k1986(219861i，两坐标和为2xii1 为奇数 本题为第二届冬令营的一道很难的问题,方法较多，上面给出的方法是一个很巧妙的解法，利用奇偶性板块二当所计数对象按从1到n有规律出现时，可视之为一个数列并其相邻项之间关系，得到递推关系【例15】（Fibonacci）假设一对兔子每隔一月生一对小兔，每对小兔两个月后也逐月生一对小兔，ann个月初的小兔对数，易得到a11a22a3一般地，第nn-1n个月初出生的小兔对数，即得到递推式anan1an2，由特征方程的结论及初值，可得到a13377a

5

1

( 【例16】1,2,3n1【解析】设有an个，显然a13a28141232an2个，得到递推式an2an12an2n314an

3)n2

3)n2注板块三n【例17】rst为整数，集合{a|a2r2s2t,0tsr中的数由小到大组成数列{an

2rst为整数且0tsrr2，此时符合条件的数有C223r3st可在0,1,2中取，符合条件有的数有C234r4时，符合条件有的数有C245r5时，符合条件有的数有C256r6时，符合条件有的数有C267r7时，符合条件有的数有C27a36r7

20

27注本题为2005年 预赛题，事实上此题源自2003年高考理科试卷压轴题，用二进制方法求解最 《2003年高考理科数学压轴题的一种巧妙解法及其推广》中学教研2003.12【例18】如果自然数a的各位数字之和等于7，那么称a为“吉祥数”.将所有“吉祥数”从小到大排成一列a1,a2,a3,,若an2005,则a5n .mk∵方程x1x2xkm的非负整数解的个数为Cm .而使x11,xi0(imk数为数为

m7kP(k)C6.kk∵2005是形如2abcP(1)C61P(2)C67,P(3)C6 对于四位“吉祥数”1abc，其个数为满足abc6的非负整数解个数，即∴20051+7+28+28+1＝65a652005从而n65,5n

P(4C684P(5

210而P(k5 5

k32552000，即a5n注1、本题为2005年联赛试mx1x2xnmmx1x2xnm的正整数解的组数为Cn1

nm1【例19】若四位数nabcd的各位数码a,bcd中，任三个数码皆可构成一个三角形的三条边长，则称称(a,b,c,d)为n的数码组，则a,b,c,dM{1,2, ,9}.当数码组只含一个值，为(a,a,a,a),a1, ,9，共得9个n值当数码组恰含二个值a,b（ab9①数码组为(a,a,a,b)型，则任取三个数码皆可构成三角形，对于每个a ,9}，b可取a9个值，则数码组个数为(a136(aaa,b)b4种占位方式，于是这种n364144②数码组为(a,b,b,b型（ab，据构成三角形条件，有ba2bb123456789b Ma012343210共得16个数码组，对于每组(a,b,b,ba有4种占位方式，于是这种n有164644③数码组为(aa,b,b型（abba2b，同上得16个数码组，对于每组(aa,b,b)，两个a有C26种占位方式，于是这种n有16696个．4以上共计1446496304当数码组恰含三个值a,b,c(abc①数码组为(a,b,c,c型，据构成三角形条件，则有cba2c，这种(a,b,c,c有144a,bA212种占位方式，于是这种n有141216844②数码组为(a,b,b,c)型，cbabc，此条件等价于M{1,2, 角形的方法数，有34组，每组中a,b有A212种占位方式，于是这种n有3412408个．44③数码组为(aa,bccbabc，同情况②，有34A2408个n4以上共计168408408984个na,bcddcbacd，这种a,bcd有16组，每组有4得164384个n综上，全部四位三角形数n的个数为93049843841681注教师备注 k分的有bk个（1k100Ma1a2anNb1b2b100，M,N的大小关系为？1k，于是得证.【解析】M.和为180x度，于是我们得到：180 901985又每个三角形都有三条边，共有39723条边，另一方面，每剪一次产生两条三角形的边，而四y2y+4条边，由397232y4y140？4（3S1，因此S181；另一方面，14S1141或11的个数为偶数，由于12m,8m,6种颜色的11m2都是单色的,每种颜色的地砖都足够多),要求相邻(即有公共边的)的两块地砖颜色不同,那么所有的不A.308

30257

30207

30217AB【解析】铺第一列(两块地砖)有30种方法；其次铺第二列．设第一列的两格铺了AAB两色(如图)，那么，第二列的上格不能铺A色．若铺B色，则有(6

铺B

(6

种方法.于是第二列上共有21都有21种铺法．因此，共有注2005

30

一次竞赛有n(n2名选手参加，每天选手的得分恰好组成集合{12n}k天末，52分，求出使这件事成立的所有数对(nk)nn【解析】一方面，kkl

l1kn(n125226n，从而k(n152n3对.注本题为一个简单的算两次问题

11,a

3，

na

，

， （A）100个 （B）120个 （C）160个 （D）200个【解析】设三位数为abc，对a,b,c的可能取值进行分析abccba100(ac10(bb(acac不进位，则和数的十位数必为偶数，不符合题意，所以ac11，13，15，17.2211＝9＋2＝8＋3＝7＋4＝6＋5，所以ac取值有4A2种可能；13＝9＋4＝8＋5＝7＋6，所以ac取值有3A2种可能；22215＝9＋6＝8＋7，所以ac取值有2A22217＝9＋8，所以acA22由于bb不能进位，所以b 因此，满足条件的数共有5(4A23A22A2A2)100 注本题为2007年广西预赛试题.对于新定义题准确理解概念是关键本题以ac的可能取值为突破口，

的恒等式.事实上，历史上出现过数以千计的组合恒等式，直到现在仍然有新的恒等式出现.在大小丛(a(ab)C b(n knknk

Cranrbr(0rn它是展开式的第r+1项nnnCr(0rnnn（1）CkCnk(0knnnn

Ck1(0kn 若n是偶数，有C0C1 C2,C2 Cn1Cn，即中间一项的二项式系数C2最大

若n是奇数，有C0C1 C2,C

C2,C

Cn1CnnnnC2和

n

相等且最大C0C1C2Cn C0C2C4C1C3C5 kCknCk1或

nCk

CkCmCmCkm (mk

Cn

Cn1

nkn以上组合恒等式（是指组合数Cm满足的恒等式）是证明一些较复杂的组合恒等式的基本工具n 例20】Ck2n(1)kCk02kCknknk knn【解析】由二项式定理(ab)nCkankbk(nnk

(1x)nCkxknknx【例21【例21】证明：（1）kCn nkCn

Cn1

nk 【解析】（1）由kCknCk1可 kCk nCk1n Ck1n

k

k

k

k

Cn1(Cn1C Cn1(Cn1Cn1)(Cn1Cn1) (Cn1Cn1) . CC

【例22【例22】kCnn nk【解析】首先求【解析】首先求k（k1)Cknk （n（n Cl

n(n1)2n2kn

k

nln又kCkn2n1nknn注类似地，我们还可以求得k3Cknn1)(nnnnC【例23】Ck

k22n12 k

Ckk0

Ckkn1

22nCkk

C2njC

Cnk

kn于是Ck1(22nCn22n1(n2 2k

2【例24】已知数列a0a1a2,(a00满足ai1ai12ai(i1,2,3,p(x)aC0(1x)naC1x(1x)n1aC2x2(1x)n2 Cn1xn1(1x)aCn0 1 2

n1 nx的一次多项式或零次多项式ai1ai12ai知{anaiai1da0id(i1,2,p(x表示成a0和d的表达式，再化简即可.因为ai1ai12ai(i1,2,3,,所以数列{an为等差数列，设其公差为有aia0id(i1,2,3,) 从P(x)aC0(1x)n(ad)C1x(1x)n1(a2d)C2x2(1x)n2(and)Cn0 a[C0(1x)nC1x(1x)n1Cnxn]d[1C1x(1x)n12C2x2(1x)n2nCnxn C0(1x)nC1x(1x)n1C2x2(1x)n2Cnxn[(1x)x]n n又因为kCkkn

k!(nk)!

n

(n(k1)![(n1)(k

从而C1x(1x)n12C2x21x)n2nCn nx[(1x)n1C1x(1x)n2xn1

P(x)a0当d0时P(x)为x的一次多项式，当d0时P(x)为零次多项式本题有一定的难度，运算量也很大，需要对二项式定理及常用组合恒等式相当熟练.建议选择讲授.n（1）n k （2）CkCt k(1)k(Ck)2 k【解析】考虑(1x)m1x)nxt一方面xt的系数即(1x)mn的系数，即另一方面，利用二项式定理将(1x)m1x)nxt的系数即为（2）式左边，从而（2）式得证；在此式中令mnt即得（1）式.下证（3：利用(1x)n的展开式，考虑(1x)2n1x)2nx2n的系数：一方面(1x22nx2n另一方面(1x)2n1x)2nx2n注本题使用的方法即母函数方法，但母函数方法在联赛中不要求，我们只举此两例，以供有的同学【例26】设nm，证明 Cmk

2nm kn一方面，先选定正式代表，有Cmn-m人中选列席代表，有2nmnn2nmCmnm+k人k0,12nm),k有Cmk

种选法，从而选法总数为Cmk

注本题采用了构造组合模型的方法.事实上，近年来组合恒等式内容非常浅，联赛中不会涉及到利用n 【例27】7CkCp2nn k n【解析】注意到CkCpCpCnk，于是CkCpCpCnkCp

2npCp n

np np kp kp l0【例28】（1）试求(xx2x3x46x15器，打算安排5个岗位配备这些新式，要求第一个和最后一个岗位不配备新式，且每相邻5个岗位至少有一个岗位配备新式，相邻两个岗位不同时配备新式，问共有多少种配【解析】（1）由(xx2x3x46x61xx2x36x61x)61x26，知只须求(1x)61x26x9的系数。又(1x)6(1x2)6(16x15x220x315x46x5x6(16x215x420x615x86x10x9的系数为6×15＋20×20＋6×15＝1，2，…x1a1x2a2a1x3a3a2x4a4a3x5a5a4x620a5

其中2

x1x2x3x4x5x6

ykxk1(k1,2,3,4,5y6x6y1y2y3y4y5y6

问题（**）的解数等于(xx2x3x46x152005备选题备选题 求证：(1) 2nk

nk【分析】考虑到恒等式

2解决 【证明】令

(1) (1) ,2nk，k，

(1) (1) 2nkkn)22n(1)k22n2k)

k1k (1)k22n2kCkk令rk1

(1)k22n2kCk1kn(1)k22n2kCkn

(1)r122(n1)2rCr

k

r(1)

2(n1)rr2(n1)2r2(n1)r

rn令(1)k22n2kn

b,则

a k

(1) (1) k22n (1)k22n2k

Ck

)k2(n1)2(n1)

2nk

2nk

(1)j22(n1)2jCjj04an1于是由①式得bn1an1an2,从而推知anan14an1an1an2,即anan22an1.数码a1,a2,a3 ,a2006中有奇数个9的2007位十进制数 a2006的个数2

2

102006

102006

【答 【解析】（B）9A

92003 C20059

又由于(91)2006k

92006k以及(91)2006Ckk

(1)k92006kA

92005

nCkCn1knn k【解析】考虑(1x)n1x)nxn1xn1的系数即(1x)2n的系数，即Cn1另一方面，利用二项式定理将(1x)n1x)nxn1的系数即为原式左边，从而得证；注6（2）的特例nnk

k

k C nCn(1)k k

k

Cnk数列

}

3an1(n2)，求 n的初值猜想an的特点与an2n=1时，a1=3a3a133274623a3

3273463(34

，因此

,

an4m3mN

n=k

4m3,mNn=k+1

34m3(4C

4m34T14(T1)

所以对任意正整数n，an4m3(m于是

故a2001注本题中利用初值得到规律进而猜想an4m3是问题解决的关键.已知a00a11an18anan1n

{an15【解析】数列

}x28x10

4

4

1所以anA(41

15)nB(4

a由00a

,B

则

[(4

15)n(4121212nn2k(k121212n12a12

[2C1n

4

T

本讲讲述组合数学中一个非常简单却又十分重要，应用十分广泛的一个原理，即抽屉原理.然后给出与抽屉原理内涵相通的几个变形，即平均值原理与图形原理.事实上这个原理用来证存在性题的有工之一，当我们还以利用原理反证法数学归纳法、算两次、计数方法和构造法等等来加以证明.本讲我们主要讲述利用平均值原理（其在整数和图形范内的形分别为屉原理图形原来证存在性题略举数说明其方法在证m第一抽屉原理：若将m个物件放入n个抽屉中，则必有一个抽屉内至少有 ]1个物件nm第二抽屉原理：若将m个物件放入n个抽屉中，则必有一个抽屉内至多有 ]个物件n1：设aaaAa1a2...an，则aaa中必有一个不小于 也必有一个不大于2：设a1a2an为正实数，且G也必有一个不大于

na1a2...na1a2...图 原理把面积为S1,S2,...,Sn的n个平面图形以任意方式放入一个面积为S的平面图形A内S1S2SnSS1S2SnS，则必有一点不属于上述n可以发现，上述三组原理都是性原则在不同场合的具体表现形式.性法则是处理组合数学中分割图形、利用剩余类等等.与抽屉原理相关的试题中，联赛中的题目往往利用抽屉原理是解题的关键，1995，并且每一个三角形的三个顶点同色。BiBjBk，于是BiBjBkAiAjAk即为所求注本题为1995年联赛第4Si，Sj（i＜j，则100|SJSi100|ai1ai2...aj.命题得证。注本题所采用的这种利用连续项构造和式的方法非常经典【例31】1-10051两个数属于同一个抽屉，即属于（1）-（25）25注【例32】10AB，注【例33】试求最小的正整数n使得对于任何n77n13。对每个非负整数a称如下10个数所构成的集合:Aa{10a,10a 10a9}为一“基本段akak连续数属于三个基本段Aa1AaAaakakakak

akak

a1(a06)是属于同一个基本段的7 aiai ai677

所求的最小值为n20051.5 25,791,10，49周周周周周周周1**2**3**4**5**B、C、D、E、FB、C、DB、CA、B、C 科学 2个B6之间的连线只染有黄蓝两色。B2，B3，B4，之间无黄线，则△B2，B3，B4，必为蓝色三角形，命题仍然成立。 【解析】189023357,设给定自然数为aaa99个抽屉，必有两9整除，不妨设为9|a10 同理可得到7|a8a75|a6a53|a4a3，最后，若a1a2中有一个为偶，那么2|a1a22|a2a15内不能安排该球队的客场比赛。如果4能够完成全部比赛，求n的最大值。6**容易验证，按照表中的安排，66**

E

i,发生

i

i,j{12,34,5}，SiSjABC或DEF，必有SiSjSj所以，n注本题为第一届东南数学第7题.本题是一道组合极值问题组合极值的构造与论证难度一般都

此时，旋转圆2，其中有50次与点A颜色相同，任取其中一点B,固定圆2，再旋转圆3，如此下 次，共出现同色四点组(A,B,C,D)有 50个，

12.5根据平均值原理，必在某次旋转后存在n12.5n13条射线，它们中每一条穿过四点同色（a1，2，a3a2，3，a4a3，4，a5…,（a9，10a1）,（10，1，a2）11.2121于.2(1BC△ABC，P，M△ABC（包括边界）PMPAB、BCMACP、Q、N，那么BC≥AB，所以∠A≥∠C，则∠QNP≥∠PQN，而∠QMP≥∠QNP≥∠PQN（三角形的外角大于不相邻的内角，所以PQ≥PM。显然BC≥PQBC≥PM.12整除6p，只须证明：34pa，b，c，d3a，b，c，d23a，b3b-a3a，bc，db-a为偶数，d-c4可整除(b-a)(d-c)4p.8【解析】在一条直线上取点OO78814，15

第五讲容斥原理与性原计数来实现对整体的计数是一种明智的选择.XA1，A2，…AnXA1A2An.集合A1A2,An}X全）划分.如XX的计数可通过熟知的加法|X||A1||A2||A3||An进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事.相对补集：称属于ABB对A的相对补集或差集，记作A-AAnA1A2An1Ai(i1,2,n)为有限集,nn|n

||Ai|

|Ai

i|(1)n1|Ai

n 定理 设Ai(i1,2,,n)为有限集I的子集，则|Ai||Ai||I||Ai

n|I||Ai|n

|Ai

i|(1)n|Ai

而性原理则是一种非常重要的数学思想.从问题的情况考虑，对于数值问题来说，就是指取板块一【解析】（1）设S1＝{a∣1≤3≤120,2∣a}；S2＝{b∣1≤b≤120,3∣b}；S3＝{c∣1≤3≤120,5∣c}；S4={d∣([n]n的整数部分，例如[2,4]＝2，…)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＋∵2，3，5，712089card(A)AA 则|A|=21|B|=194148人之间。411310512人之间。注对于基础较好的同学，此题可不讲ABABC。最后再说明有A、B、CDA、B、C、D就是找的人了。证明：一个人AB.即C与A和B均合作过 分别表示与A、B合作过的人的集合。同样地。所以存在。则A、B、C、D就是所求，证毕。注本题为一道典型的图论问题，我们用容斥原理的方法来解决它【解析】首先计算S12,...,105}105Aim|mSi|m}是 A7105105][是 A7105

]48 57 35710548105互素，而1000482040，所以a1000a40，a48104a47103101,97,94,92,89,88,86知a1000a40=861994【例43】一个人写了nnn封信都装错了信封，问这样的装法n1，2，…，nn个不同元素的排列1°i(i=1，2，…，n)iii2°n个不同元素的一个错排(若每个元素都在原位则称为按照上面约定，“装错信封问题”n个不同元素的错排问题，则可构建“装错信封问题”的数学模型n个不同元素的全排列中，有多少种不同的错排？SAjj在原位的所有排列所构成的集合，|S|=n|Ai|=(n－1)|Ai∩Aj|=(n－2)…，AA|j AniD|S||A|| n!C1(n1)!C2(n2)!C3(n3)!...(1)nCn( n!(1 ... 注本题为“装错信封问题”，是由著名数学家·(JohannBernoulli，1667－1748)的儿子·伯努利(DanidBernoulli，1700－1782)提出来的，是一道典型的利用容斥原理或递推方法来解决的问题. ,x2n)具有性质P是指：存在属于集合{1,2,....,2n1}使得|xixi1|n。求证，对于任何nPP的排.P的排列的集合，显然|A||B|1为了|A||B|

|B

2

(x1x2 ,x2nkk

Akk

|Ak|22n1（kknAk2n1个元素的全排列，另外kkn可互换位置。即得|Ak|22n1同理|AA|222n2)!,1k,jnkn nn则|B||Ak||n

k 【例45】8×816464个数。问：是否一定能够找到两个相邻4？【解析】考虑这个方格棋盘的左上角、右上角及右下角内的数A，B，S设存在一个填数方案，使任意相邻两格中的数的差不大于4，考虑最大和最小（A=1，S=644，的位置上。显然，164164之间的距离更近了，更要导致如上的矛44。A，B，C，使得AB，BC，C【解析】从情况观察入手，设B是胜的次数最多的一个选手，但因B没获全胜，故必有选手A胜B。BAC，否则，ABB是A，B，C，使得AB，BC，C胜A3（假设认识是相互的）33nA，他认识其他两所学校中某一所学校的人数是最多的，这个最大值为kn.Ak3

n1k1An-kc认识第一所学校的学生人数至少为n1(nk)k1，此与k的最大性假同H为可去选手。我们的问题就是要证明存在可去选手。A一个（C）A赛过。C不是可去选手，故存在选手D，E，其中DCECEEC赛过，因而选手EA。AED1A是已赛过对手最多的选手。 A3 A3 6!C125!C2224!C3233!=240 【解析 A333,333200,配备新式的方案？12…20 设置的序号为ak(k1,2,3,4,5)x1a1x2a2a1x3a3a2x4a4a3x5a5a4x620a5其中2

x1x2x3x4x5x6

y1y2y3y4y5y6

A为不定方程（2）Ak(k1,2,3,4,5,6A

yi4y

4，

（2，

Ak6 6