组合数学第三章答案

3.1题（宗传玉）某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议解:设Ai为甲与第i个朋友相遇的会议集，i＝1，…，6．则故甲参加的会议数为:28+5=33.3.2题（宗传玉）求从1到500的整数中被3和5整除但不被7整除的数的个数.解:设A3：被3整除的数的集合A5：被5整除的数的集合A7：被7整除的数的集合所以3.3.题（宗传玉）n个代表参加会议，试证其中至少有2人各自的朋友数相等。解:每个人的朋友数只能取0，1，…，n－1．但若有人的朋友数为0，即此人和其他人都不认识，则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只有n－1种可能．，所以至少有２人的朋友数相等．3.4题（宗传玉）试给出下列等式的组合意义.解:(a)从n个元素中取k个元素的组合，总含有指定的m个元素的组合数为)()(knmnmkmn。设这m个元素为a1,a2,…,am,Ai为不含ai的组合（子集），i=1,…,m.mllmllmiiljilklnkmAknknmnklnlj01),(),...,(1m1iiiii1)1(AAAA111213.5题（宗传玉）设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7，c1c2c3c4c5c6c7．试证存在整数i和j，1≤i≤j≤7，使得下列之一必定成立：ai=aj=bi=bj，ai=aj=ci=cj，bi=bj=ci=cj．证：显然，每列中必有两数字相同，共有种模式，有０或１两种选择．故共有·2种选择．·2=6．现有7列，．即必有２列在相同的两行选择相同的数字，即有一矩形，四角的数字相等．3.6题（宗传玉）在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于证：把１×１正方形分成四个(1/2)×(1/2)的正方形．如上图.则这５点中必有两点落在同一个小正方形内．而小正方形内的任两点的距离都小于．3.7题（王星）在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2．证：把边长为１的三角形分成四个边长为1/2的三角形，如上图：则这５点中必有两点落在同一个小三角形中．小三角形中任意两点间的距离都小于1/2．3.8题（王星）任取11个整数，求证其中至少有两个数它们的差是10的倍数。证：整数的个位数的可能取值为０，１，…，９．共１０种可能．11个整数中必有２个数的个位数相同，即这两个数之差能被１０整除．3.9题（王星）把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和，或是另一个数的两倍。证：用反证法。设存在划分P1∪P2∪P3∪P4∪P5＝[1，326]，Pi中没有数是两数之差．，则有一Pi中至少有66个数，A＝{a1,…,a66}，a1＜a2＜•••＜a66，以下按书上174页的例题证明可得．3.10题（王星）A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料，III不允许用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）解：按题意可得如下的带禁区的棋盘,其中有阴影的表示禁区．棋盘多项式为：R()=R()R()=(1+x)(1+3x+x2)=1+4x+4x2+x3故方案数＝3!－4•2!+4•1!－1•0!＝13.11题（王星）n个球放到m个盒子中去，n＜(m/2)(m－1)，试证其中必有两个盒子有相同的球数。解：设m个盒子的球的个数是a1,…,am，各不相等，且有0≤a1＜a2＜•••＜am．则有a2≥1、am≥m－1，故≥1+2+…+m－1＝(m/2)(m－1)，与n＜(m/2)(m－1)相矛盾！所以必有两个盒子的球数相等．3.12题（王星）一年级有100名学生参加中文、英语和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中、英文考试，54人通过中文和数学考试，45人通过英语和数学考试，求通过3门学科考试的学生数。解：设：通过中文考试的92人为集合A，通过英语考试的75人为集合B，通过数学考试的65人为集合C则∣A∩B∣=65，∣A∩C∣=54，∣B∩C∣=45由∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣A∩C∣-∣B∩C∣+∣A∩B∩C∣故∣A∩B∩C∣=∣A∪B∪C∣-∣A∣-∣B∣-∣C∣+∣A∩B∣+∣A∩C∣+∣B∩C∣=100-92-75-65+65+54+45=32通过3门学科考试的学生数为32。3.13题（王丹竹）试证(1)||||||BABBA(2)||||||||CBABACCBA证明：(1)ABABBAB=BABABBABA=BABBAB=所以ABBAB成立(2)ABCABCABABABABAB=CACBCABC又因为由（a）得原式=()()()CABCCACBC3.14题（王丹竹）}1000,,2,1{N，求其中不被5和7除尽，但被3除尽的数的数目。解：设3A为被3除尽的集合5A为被5除尽的集合7A为被7除尽的集合所以由题意得：357335357AAAAAAAAA-应该少了一个吧？=100010001000100033537357=333-66-47+9=2293.15题（王丹竹）}120,,2,1{N,求其中被2，3，5，7中m个数除尽的数的数目，m=0，1，2，3，4。求不超过120的素数的数目。素数？解：(1)m=0时不被2，3，5，7除尽的数为2357AAAA=120-2357232527AAAAAAAAAA+533757AAAAAA-235237AAAAAA-257357AAAAAA+2357AAAA=120-（60+40+24+17）+（20+12+8+8+8）-（4+2+1+1）=27m=0时231202023AA251201225AA27120827AA37120537AA57120357AAM=3时2351204235AAA2371202237AAA2571201257AAA3571201357AAAM=4时235712002357AAAA(2)因为212111，故不超过120的合数必然是2，3，5，7的倍数而且不超过120的合数的因子不可能超过11设iA为不超过120的数的倍数集合，i=2，3，5，7排除2，3，5，7这四个数又包含1这个非素数2，3，5，7本身是素数，故所求不超过120的素数个数应该为27+4-1=303.16题（王丹竹）求正整数n的数目，n除尽4010，3020中的至少一个数。这道题是这样做吗？解：N为正整数设4010A为被4010除尽3020A为被3020除尽4010A=4010n3020A=3020n4030403010201020nAA3.17题和3.18题（未完成）（王丹竹）3.19题（孔令琪）{1000，1001，。。。，3000}，求其中是4的倍数但不是100的倍数的数目。此题下面的解法，我个人认为是不正确的。解：设A，B分是4，100的倍数。45055005100*410003000500410003000BAABABAA3．20题（孔令琪）在由a,a,a,b,b,b,c,c,c,组成的排列中，求满足下列条件的排列数，（1）不存在相邻3元素相同；解：A，B，C分别表示aaa,bbb,ccc则：1!3!5*3!3!7*3!3!9!3!91!3!5!3!72332CBACBCABACBASCBASCBACBCABACBA（2）相邻两元素不相同。这个怎么做？3．21题（孔令琪）求从O（0，0）点到（8，4）点的路径数。已知（2，1）到（4，1）的线段，（3，1）到（3，2）的线段被封锁解：设A点坐标（2，1），B点坐标（4，1），C点坐标（3，1），D点坐标（3，2）令a为从O点到M点经过ACb为从O点到M点经过CBc为从O点到M点经过CD271)()(006310584)2,7(*)1,4(140)3,7(*)1,4(168)3,8(*)1,3()4,12(cbacbcabacbascbacbacbcabacccccbccacs3．22题（孔令琪）求满足下列条件下面对于此题的解法正确，但是答案算错了。x1+x2+x3=20,1737,820,913xxx解：令y1=x1-3,y2=x2,y3=x3-721)321(41)321(313172816321,31730,2820,1610xxxyyyyyyzzzyzyzyz则所求整数解的数目：c(23,21)=c(23,2)=2533．23题（孔令琪）此题解法与上题一样，所以不在求解，如有凝问请与我联系！3.24题（周英华）求满足下列条件的整数解数目：x1+x2+x3+x4=201≤x1≤5,0≤x2≤7,4≤x3≤8,2≤x4≤6解：设y1=x1-1,y2=x2,y3=x3-4,y4=x4-2,y1+y2+y3+y4=130≤y1≤4,0≤y2≤7,0≤y3≤4,0≤y4≤4,若不附加上界条件的解根据公式应为1341161656013133对于有上界的问题要作变换ε1=4-y1,ε2=7-y2,ε3=4-y3,ε4=4-y4,ε1≥0,ε2≥0,ε3≥0,ε4≥0,于是问题变为ε1+ε2+ε3+ε4=6整数解的数目64199846633.25题（周英华）证明满足下列条件：x1+x2+……+xn=r0≤xi≤k,i=1,2,……，n的整数解数目为0(1)1(1)1niinrkinir解：S,|S|=rrn1令S中具有x1≥k+1的子集A1，……，xi≥k+1的子集Ai,问题转化为求|A1∩A2∩…∩An||A1|=|A1∩A2|=241rnkr……|A1∩A2∩…∩An|=0(1)1(1)1niinrkinir3.26题（周英华）证明满足下列条件：x1+x2+……+xn=r1≤xi≤k,i=1,2,……，n的整数解数目为01(1)1niinrkiir证明：令yi=xi-1则y1+y2+……+yn=r-n21rnkr0≤yi≤k,i=1,2,……，n由上题知0(1)1(1)1niinrkinir代入得整数解数目为01(1)1niinrkiir3.27题（周英华）求n对夫妻排成一行，夫妻不相邻的排列数。这道题可不可以用递推关系试试？解：(1)n个人排成一行方案数为n!N对夫妻排成一行方案数为n!2n令Ai第i对夫妻相邻而坐的集合，i=1,2,……，n(2)2n个人排成一行方案数为(2n)!|Ai|相当于将第i对夫妻作为一个对象排列一行然后换位