组合数学第三章习题解答

1、第三章习题3.1 某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议？1解解设Ai为甲与第i个朋友相遇的会议集，i1，6则) 1 , 6(1261CAii2811245809072)6 , 6()5 , 6(2)4 , 6(3)3 , 6(4)2 , 6(6) 1 , 6(12CCCCCCAi33528共33次会议 2.求从1到500的整数中被3和5整除但不被7整除的数的个数.解解设A3：被3整除的数的集合 A5：被5整除的数的集合 A7：被

2、7整除的数的集合294337535005350035735357AAAAAAAA 3. n代表参加会议，试证其中至少有2人各自的朋友数相等。解：解：每个人的朋友数只能取0，1，n1以下分两种情况讨论。若有人的朋友数为0，即此人和其他人都不认识，则其他n-1个人的最大取数不超过n2必有两人认识人数相等。若没有人的朋友数为0，则这n个人的朋友数的实际取数只有n1种可能所以至少有人的朋友数相等。3.4 试给下列等式以组合意义milmknklnClmCknmnCa0),(),() 1(),( )(mnjjlljmnCjmnCmnlCb0), 1(),() 1() 1, 1( )(),() 1(.)2,

3、() 1,(),() 1, 1( )(lmlmCmlmCmlmCmlmCmlmCcl(a)从n个元素中取k个元素的组合，总含m个指定的元素的组合数为C(n-m,k-m),设这m个元素为a1,a2,.,am.Ai为不含ai的组合，i=1,2,.,m),(),( )(mkmnCknmnCa),(.), 1(21klnCAAAknCAiliiim1i21),)(,() 1( ),(),() 1( .), 2()2 ,(), 1() 1 ,(),(.klnlmCkmnCmmCknCmCknCmCknCAAAlmimii( b )令knml个相同的球放入k个不同的盒子里每盒不空的方案数为C(n-m+l-

4、n+m-1,l-n+m)=C(l-1,n-m-1)。设Ai为第i个盒子为空的方案集，i=1,2,k.m-n1j21), 1)(,() 1( ), 1(),() 1( .), 3()2 ,( ), 2() 1 ,(), 1(.lljmnjmnCllCmnmnCllmnCmnCllmnCmnCllmnCAAAjmnkl个相同的球放入n个不同的盒子里，指定的m个盒子为空，其他盒子不空的方案数为C(l-1,n-m-1)( c ) 设Ai为m+l个元素中取m+i个，含特定元素a的方案集；Ni为m+l个元素中取m+i个的方案数则：),(imlmCNi1), 1( ) 1, 1(),() 1, 1(iiii

5、iAimlmCimlmCimlmCANAimlmCAliANAiii,.,2 , 1, ),( .)2,() 1,(),( ) 1(. .)(21011010000lmlmCmlmCmlmCmlmCNNNNANNANANAll3.5 设有3个7位的二进制数 a1 a2 a3 a4 a5 a6 a7, b1 b2 b3 b4 b5 b6 b7, c1 c2 c3 c4 c5 c6 c7,试证存在整数i和j，1ij7，使得下列之一必然成立：ai=aj=bi=bj,ai=aj=ci=cj,bi=bj=ci=cj证明：显然，每列中必有两数字相同，共有C(3,2)种模式，有或两种选择故共有C(3,2)2

6、种选择。C(3,2)2=6现有7列，即必有列在相同的两行选择相同的数字，即有一矩形，四角的数字相等3.6 在边长为1的正方形内任取5点，试证其中至少有两点，其间距离小于 22证证把正方形分成四个相等的小正方形如下图：则这点中必有两点落在同一个小正方形内而小正方形内的任两点的距离都小于22)21()21(22证把边长为的三角形分成四个边长为的三角形，如下图：则这点中必有两点落在同一个小三角形中3.7 在边长为1的等边三角形内任取5点，试证至少有两点距离小于1/23.8 任取11个数，求证其中至少有两个数它们的差是10的倍数。证明：一个数是不是10的倍数取决于这个数的个位数是不是0，是0就是10的

7、倍数。一个数的个位数只可能是0,1,.,9十个数，任取11个数，其中必有两个个位数相同，那么这两个数的差的个位数必然是0。3.9 把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和，或是另一个数的两倍。证明：用反证法，设存在划分。326,.,154321PPPPP166,66151326P不妨设为个元素因此必存在有一子集含因为设这66个元素为a1a2a3.a66 构造b1=a2-a1, b2=a3-a1, b65=a66-a1, 令B=b1,b2,b65 这65个元素属于1到326，如果这65个元素有任何一个属于P1，则定理得证。 否则：5432ppppB

8、(2)因为。1714165因此至少有一个集合含至少B中17个元素，设这个集合为p2。设这6个元素为：1721.iiibbb11aabjjii构造：,.,11713121621iiiiiibbcbbcbbc111111111111iiiiiijaaaaaabbcjjj 设C=c1,c2,c16 否则：543pppC(3)因为。613116因此至少有一个集合含至少C中6个元素，设这个集合为p3。设这11个元素为：621.iiiccc11iiibbcjj构造：161312521,.,iiiiiiccdccdccd 如果：)(21ppC则定理得证 同样可证明d1和d2既可表示成p1中元素之差，也可表示

9、成p2p3中元素之差， 设D=d1,d2,d5 否则：54ppD(3)因为。31215因此至少有一个集合含至少D中3个元素，设这个集合为p4。设这3个元素为：321iiiddd11iiiccdjj构造：131221,iiiiddedde 如果：)(321pppD则定理得证 同样可证明ei既可表示成p1中元素之差，也可表示成p2p3p4中元素之差，否则：521,pee12ee 同样可证明e2-e1既可表示成p1中数之差，也可表示成p2p3p4中数之差。 e2-e1是1到326中的数，设f=d2-d1 4321ppppe 因此：1到326的326个整数任意分成5部分，其中必有一部分其中有一个数是另

10、两个数之差，设ai=aj-ah,那么反过来：aj=ai+ah构造：3.10 A,B,C三种材料用作产品I,II,III的原料，但要求I禁止用B和C作原料，II不能用B作原料，III不允许用A作原料，问有多少种安排方案？解解按题意可得如下的带禁区的棋盘其中有阴影的表示禁区A B C 禁区的棋子多项式为：R( ) =R( ) R( ) =(1+x)(1+3x+x2 ) =1+4x+4x2 + x3 故方案数3!42!+4 1!1 0!13.11,n个球放到m个盒子中去，nm(m-1)/2,试证其中必有两个盒子有相同的球数。证明：用反证法假如没有两个盒子的球数相同，那么m个盒子中最少需要0,1,2,

11、.(m-1)共m(m-1)/2,因此必有两个盒子有相同的球数。3.12,一年级有100名学生参加中文、英文和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中英文考试，54人通过中文和数学考试，45人通过英语和数学考试，求通过三门学科考试的学生数？3.13,试证CBACBCACAbBABAaCB )(B )(证明(a)BABAAaB ，BBAB )(因此互为余集关于与CBABACACBCAACBACBACBCACAbCC )()C(CB .)()C(CB CB )(互为余集与3.15,N=1,2,.,120,求其中被2,3,5,7,m个数除尽的数的数目

12、，m=0,1,2,3,4。求不超过120的素数的数目。解解设A2：被2整除的数的集合 A3：被3整除的数的集合 A5：被5整除的数的集合 A7：被7整除的数的集合177120,245120,403120,6021207532AAAA,375120,573120,853120872120,1252120,2032120757353725232AAAAAAAAAAAA1753120, 1752120,2732120,4532120753752732532AAAAAAAAAAAA075321207532AAAA27856141120)1124()35881220()17244060(120)0(52

13、4112141)1124(3)35881220(2)17244060()1 (2224112141)1124(3)35881220()2(8)1124()3(0)4(素数为27-1+4=303.16,求正整数n的数目，n除尽1040，2030中至少一个数。解：解：,405 ,402 ,521052)52(104040404040个的倍数有个的倍数有的倍数或的数必为因此能除尽可分解为,305 ,602 ,522052)52(2030306030230个的倍数有个的倍数有的倍数或的数必为因此能除尽可分解为1681414110,415,.,5 ,55 ,412,.,2,224040104010的数的

14、个数是因此能除尽个数可除个数可除1891316110,315,.,5 ,55 ,612,.,2,224030106010的数的个数是因此能除尽个数可除个数可除12713141,315,.,5 ,55 ,412,.,2,2230104010的个数是因此能除尽两个数的数个数可除个数可除有能同时除尽两个数的数设A1为能除尽1040的数，A2为能除尽2030的数，2301127118911681 212121AAAAAA3.17,求正整数n的数目，n除尽1060，2050，3040至少一个数。解：解：,605 ,602 ,521052)52(104060606060个的倍数有个的倍数有的倍数或的数必为

15、因此能除尽可分解为,505 ,1002 ,522052)52(20305010050250个的倍数有个的倍数有的倍数或的数必为因此能除尽可分解为3721616110,615,.,5 ,55 ,612,.,2,224060106010的数的个数是因此能除尽个数可除个数可取51515110120,515,.,5 ,55 ,1012,.,2,2250501010010的数的个数是因此能除尽个数可除个数可取689214130,415,.,5 ,55 ,413,.,3 ,33 ,412,.,2,22340401040104010的数的个数是因此能除尽个数可除个数可取个数可取,405403 ,402 ,5

16、3220,532)532(30304040404040个的倍数有个的倍数有个的倍数有的倍数或或的数必为因此能除尽可分解为31115161,515,.,5 ,55 ,612,.,2,2220,10501060105060的个数是因此能除尽两个数的数个数可除个数可取的数有能同时除尽两个数16814141,415,.,5 ,55 ,412,.,2,2230,10401040104060的个数是因此能除尽两个数的数个数可除个数可取的数有能同时除尽两个数16814141,415,.,5 ,55 ,412,.,2,2230,20401040104050的个数是因此能除尽两个数的数个数可除个数可取的数有能同

17、时除尽两个数16814141,415,.,5 ,55 ,412,.,2,2230,20,1040104010405060的个数是因此能除尽两个数的数个数可除个数可取的数有能同时除尽两个数7300116811681168131116892151513721 321323121321321AAAAAAAAAAAAAAA3.18,求下列集合中不是n2，n3，形式的数的数目。解：解：10,.,110,10)(10,.,2 , 1)(4334ba个不是的数目是个共形式的数的数目是中是10010100100,.2,110,.,2, 1422224，n个不是的数目是个共形式的数的数目是中是因为2110212

18、1,.2,110,.,2, 110648224333343，n1211010,12,21,.,11,1010,.,110,10343333433不是的数目是个共形式的数有是n6911010,69,100,.,33,3210,.,110,10342222433不是的数目是个共形式的数有是n4, 3 ,2,1，共同的是3.19,求下列集合中是4的倍数，但不是100的倍数的数的数目。3000,.,1001,1000个的倍数有个的倍数有2111002000100,50114200044802150121121AAAAA3.20,在由a,a,a,b,b,b,c,c,c组成的排列中，求满足下列条件的排列数

19、，(a)不存在相邻三元素相同。(b)相邻两元素不相同。解a,设A1为至少存在三元素aaa相邻的排列集。 A2为至少存在三元素bbb相邻的排列集。 A3为至少存在三元素ccc相邻的排列集。3 , 2, 1,140! 3 ! 3!7iAi3 , 2, 1,20! 3! 5jiAAji6! 3321AAA131463203140! 3! 3! 3!9321AAA解b,设A1为至少存在二元素aa相邻的排列集。 A2为至少存在二元素bb相邻的排列集。 A3为至少存在二元素cc相邻的排列集。3 , 2, 1,980! 3 ! 3!7! 3 ! 3! 8iAi3 , 2, 1,620! 3! 5! 3!6!

20、 3!6! 3!7jiAAji426672360720! 3!4!4!4! 5! 5! 5!6321AAA1741506168042636203980! 3 ! 3 ! 3!9321AAA3.21,求从O(0,0)点到(8,4)点的路径数，已知(2,1)到(4,1)的线路， (3,1)到(3,2)的线路被封锁。解,设过(2,1)到(4,1)的线路的路径数是A1 过(3,1)到(3,2)的线路的路径数是A2。)2,7()1 , 4()3 ,7()1 , 3()4,12(0)2,7()1 , 4(),3 ,7()1 , 3(212121CCCCCAAAACCACCA3.22,求满足条件x1+x2+

21、x3=20,3x19,0 x28,7x317,的整数解数目。解,设A1是满足x13的解， A2是满足x110的解， A3是满足x29的解， A4是满足x37的解， A5是满足x318的解，)1 , 3()2, 5()2,11(53241534152413241541341241415324154321CCCAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA1的解等价于(x1+4)+x2+x3=20,其解的数目为C(3+16-1,16)A2的解等价于(x1+10)+x2+x3=20,其解的数目为C(3+10-1,10)A3的解等价于x1+(x2+9)+x3=20,其解

22、的数目为C(3+11-1,11)A4的解等价于x1+x2+(x3+7)=20,其解的数目为C(3+13-1,13)A5的解等价于x1+x2+(x3+18)=20,其解的数目为C(3+2-1,2)A1交A4的解等价于(x1+4)+x2+(x3+7)=20,其解的数目为C(3+9-1,9)A1交A4交A2的解等价于(x1+10)+x2+(x3+7)=20,其解的数目为C(3+3-1,3)A1交A4交A3的解等价于(x1+3)+(x2+9)+(x3+7)=20,其解的数目为C(3+1-1,1)A1交A4交A5的解等价于(x1+3)+x2+(x3+18)=20,其解的数目为0A1交A4交A2交A3的解

23、等价于(x1+10)+(x2+9)+(x3+7)=20,其解的数目为0A1交A4交A2交A5的解等价于(x1+10)+x2+(x3+18)=20,其解的数目为0A1交A4交A3交A5的解等价于(x1+3)+(x2+9)+(x3+18)=20,其解的数目为0A1交A4交A2交A3交A5的解等价于(x1+10)+(x2+9)+(x3+18)=20,其解的数目为03.25,试证满足下列条件x1+.+xn=r,0 xik的整数解数目为。niinnikrCinC0)1, 1)1(),()1(设Ai是满足xik+1的整数解集合。)1, 1)1()1(, 1)1(nkrnCkrkrnCAi)1, 1)1(2

24、()1(2, 1)1(2(nkrnCkrkrnCAAji) 1, 1) 1()1(, 1) 1(.21nkhrnCkhrkhrnCAAAihii) 1, 1) 1(),(.) 1, 1) 1( 2() 2 ,() 1, 1) 1(), 1() 0 (nnknrCnnCnnkrCnCnnkrnCrnrCniinnikrCinC0)1, 1)1(),()1(3.26,试证满足下列条件x1+.+xn=r,1xik的整数解数目为。niinkirCinC0)1, 1(),()1(设Ai是满足xik+1的整数解集合。)1, 1)1()1(, 1)1(nkrCknrknrnCAi)1, 1)1(2(nkrC

25、AAji) 1, 1) 1(.21nkhrCAAAihii) 1, 1) 1(),(.) 1, 1) 1( 2() 2 ,() 1, 1) 1() 1, 1() 0 (nknrCnnCnkrCnCnkrnCnrCniinkirCinC0)1, 1(),()1(3.27,求n对夫妻排成一行，夫妻不相邻的排列数。设Ai是第i对夫妻排在一起的排列集。2)!12(nAi22)!22(nAAjihihiihnAAA2)!2(.21n0i22)!2)(,() 1( 2!),() 1(.2)!22)(2 ,(2)!12)(1 ,(!2) 0 (iinnininCnnnCnnCnnCn3.28,p,qN,p是

26、奇数，现有pq个珠子，着q种颜色，每种颜色有p个珠子。假定相同颜色的珠子无区别，试分别求满足以下条件的珠子的排列数。(a)同颜色的珠子在一起(b)同颜色的珠子处于不同的块(c)同颜色的珠子最多在两个块!q解a解b3.29,将r个相同的球放进n个有标志的盒子，无一空盒，求方案数。解,两种算法：1) 1, 1(), 1(), 1(nrCnrrCnrnrnC解2，设Ai为第i盒为空，其它盒任意的方案数。), 11(rrnCAi), 12(rrnCAAji), 1(.21rrhnCAAAihii),() 1(.), 11() 1 ,(), 1()0(1rrCrrnCnCrrnCn), 1(),() 1

27、(10rirnCinCnii3.30,由28题，两种算法应相等。3.31,设B是A的子集。,mBnA求A的子集包含B的子集的数目，设子集的元素数目为r,mrn。解：设B中元素为a1,a2,.,am。 设A1是不包含a1的A的r个元素的子集数目。 A2是不包含a2的A的r个元素的子集数目。 . Am是不包含am的A的r个元素的子集数目。), 1(rnCAi), 2(rnCAAji),)(,() 1( .), 2()(2 ,(), 1() 1 ,(),(.21rmnmmCrnCmCrnCmCrnCAAAmm另外一种算法，先从A中取出B的m个元素，然后在从剩余的n-m个元素中取出r-m,共C(n-m

28、,r-m)=C(n-m,n-r)3.32,综合3.31两种情况可得3.323.44,单位圆周上任意n+1个不相同的点至少存在两点，其间距离不超过：nsin2把圆周分成n等分，每份中的距离不超过nsin23.45,边长为1的正方形内任取9点，试证存在3个不同的点，由此构成的三角形面积不超过1/8解,将边长为1的正方形等分成四部分，由鸽鸽巢原理，必有三点落在一个小正方形内，这三点形成的三角形的面积不超过1/83.47,A是n+1个数的集合，试证其中必存在两个数，它们的差被n除尽。解,n+1个数除以n的余数为0,1,2,.,n-1。若有两个以上余数为零，那么这两个数就是答案，否则，至少有n个数的余数

29、非零，根据鸽巢原理，必有两个余数相同，这两个数便是答案。3.48,A=a1,a2,.,a2k+1,k1,ai是正整数，k=1,2,.,2k+1,试证A的任意排列：1221,.,kiiiaaa恒有121)(kjjiaaj为偶数证明：A有2k+1个数，因此A中必有不少于k+1个奇数或不少于k+1个偶数。证明：设A有k+1个奇数，那么：1221,.,kiiiaaa也有k+1个奇数。jijiiaaaaaa,.,2211共有2k+1组，其中有2k+2个奇数因此必有两个奇数在一组。有k+1个偶数时情况相同。3.49,A是1,2,.,2n中任意n+1个数，试证至少存在一对a,bA使下面结果成立： a b书中

30、例题3.50,A是1,2,.,2n中任意n+1个数，试证至少存在一对a,bA使得a与b互素。从A中任意取n+1个数，必有两个数相邻，相邻数互素3.51,A是由13个互不相等的实数组成的集合，则至少存在一对x,y属于A，使3210 xyyx3.55,令A为从等差数列 1,4,7,10,.,100中任选20个不同的数，试证其中至少存在两个数，它们的和为104。项数是1+(100-1)/3=34。去掉1和52，共32个项。任取20个不同的数，至少有18个是32项中的数，(4,100),(7,97),.,(2116118因此至少有两个数落在同一组中。也就是存在两个数它们的和为1043.56,平面上6个

31、点，不存在3点共一条直线，其中必存在3点构成一个三角形，有一内角小于等于30度平面上6个点构成一个6边形，其内角和为720度，必有一角不大于120度。从这个角出发到各顶点的连线构成4个角，这4个角度数之和是120度，因此至少有一个角的度数不大于30度。3.57,n是大于等于3的整数，则下列数的集合：2-1,22-1,23-1,.,2n-1-1中存在一数被n除尽首先这是n-1个奇数，假如n是偶数时，不可能。当n=4时，数列为1，3，7不可能被n除尽。题？3.61,n个单位各派两名代表出席一个会议，2n位代表围一圆桌坐下问：(a)各单位代表并排坐着的方案有多少？(b)各单位的两人互不相邻的方案数又

32、等于多少？nna2)!1()(并排坐着(b)各单位的两人互不相邻的方案数又等于多少？设第i个单位相邻的方案数为AititiijiitnAAAnAAnA2)!12(.2)!32(2)!22(212nnnnnCnnCn2)!1() 1(.2)!32)(2 ,(2)!22)(1 ,()!12()0(23.62,一书架有m层，分别放置m类不同种类的书，每层n册，现将书架上的图书全部取出清理，清理过程要求不打乱所在的类别，试问：(a)m类书全不在各自原来层次上的方案数有多少？(b)每层的n本书都不在原来位置上的方案数等于多少？(c)m层书都不在原来层次，每层n本书也不在原来位置上的方案数又是多少？)!1) 1(.! 21! 111 ( !mmDmmmmnDa) !()() !()(mDbmnmnmDDc)()(3.64 两名教师分别对6名学生进行面试（每位教师各负责一门课）每名学生面试时间固定，试问共有多少种面试的顺序？解解第一门课的顺序有6!种 第二门课的顺序有：265)! 61.! 21! 111 ( ! 66D共有6!2653.65 X=0,1,2,.,9,10,从X中任取7个元素，则其中必有两个元素之和等于10。分成6组0,101,9.4,6,5从