组合数学课件第三章习题.ppt

1.某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议,解：.,第三章习题解答,2.求从1到500的整数中被3和5整除但不被7整除的数的个数.,解：.,第三章习题解答,3.n代表参加会议，试证其中至少有2人各自的朋友数相等。,解：.,第三章习题解答,4.试给出下列等式的组合意义,第三章习题解答,解：.,第三章习题解答,5.设有3个7位的2进制数,解：.,试证存在整数i和j，使得下列之一必然成立。,第三章习题解答,6.在边长为1的正方形内任取5个点试证其中至少有两点，期间距离小于,解：.,第三章习题解答,7.在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于,解：.,第三章习题解答,8.任取11个整数，求证其中至少有两个数它们的差是10的倍数。,解：.,第三章习题解答,9.把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和，或是另一个数的两倍。,解：.,第三章习题解答,10.A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料，III不允许用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）,解：.,第三章习题解答,11.n个球放到m个盒子中去，试证其中必有两个盒子有相同的球数。,解：.,第三章习题解答,12.n各单位各派两名代表去出席一会议。位代表围一圆桌坐下。试问：（1）各单位代表并排坐着的方案是多少？（2）各单位的两人互不相邻的方案数又是多少？,解：.,第三章习题解答,13.一书架有m层，分别放置m类不同种类的书，每层n册。先将书架上的图书全部取出清理。清理过程要求不打乱所有的类别。试问（1）m类书全不在各自原来层次上的方案数有多少？（2）每层的n本书都不在原来位置上的方案数等于多少？（3）m层书都不在原来层次，每层n本书也不在原来位置上的方案数又有多少？,解：.,第三章习题解答,14.行 列 的格子同种颜色着色，每格赵一种颜色，其中必有一个4角同色的矩形。,解：.,第三章习题解答,15.两名教师分别对6名学生同时进行两门课程的面试（每名教师各管一门课程）每名学生每门面试的时间都是半个小时，共有多少不同的面试顺序？,解：.,第三章习题解答,16.在平面直角坐标系中至少任取多少个整点（两个坐标系都是整数）才能保证其中存在3个构成三角形（包含3点在一条直线上）的面积是整数（可以为0）,解：.,第三章习题解答,17.在平面直角坐标系中至少任取去多少个整点才能保证存在3个点构成的三角形的重心是整点？,解：.,第三章习题解答,在平面直角坐标系中任取4N-3个整点，保证存在N个点的重心是整点。N=2a3b,第三章习题解答,1解设Ai为甲与第i个朋友相遇的会议集，i1，6则Ai12()6()4()3()2()()28故甲参加会议数为28533（题目）,61,62,63,64,65,66,第三章习题解答,解设A3：被3整除的数的集合 A5：被5整除的数的集合 A7：被7整除的数的集合所以A7A5A3A3A5 A7A5A3 33429（题目）,500 35,500357,第三章习题解答,3解每个人的朋友数只能取0，1，n1但若有人的朋友数为0，即此人和其他人都不认识，则其他人的最大取数不超过n2故这n个人的朋友数的实际取数只有n1种可能，所以至少有人的朋友数相等（题目）,nn1,第三章习题解答,4 解(a)从n个元素中取k个元的组合，总含指定的m个元的组合数为()=()设这m个元为a1，a2，am，Ai为不含ai的组合(子集)，i=1，mAi=()Ai1 Ai2 Ail()()Ai()+(1)Aij(1)()(),n1 k,n l k,nmnk,nk,m,i=1,m,l=1,l,l,j=1,i1,il(m,l),l,mk,n l k,m,l=0,nmkm,nmnk,第三章习题解答,(b)令knml个相同的球放入k个不同的盒子里每盒不空的方案数为()设Ai为第i个盒子为空的方案集，i=1,2,k.|Ai|=(),|Ais|=()()=|Ai|=()+(1)Ais(1)()(),l1k1,k1+l1 l,l1k1,kj+l1 l,k+l1 l,i1,ij(k,j),j,s=1,j,s=1,k,i=1,k,j=1,j,k,j=0,j,kj,kj+l1 l,第三章习题解答,l个相同的球放入n个不同的盒子里，指定的m个盒子为空，其他盒子不空的方案数为(),l1nm1,第三章习题解答,(c)设Ai为m+l个元中取m+i个，含特定元素a的方案集；Ni为m+l个元中取m+i个的方案数则：Ni()|Ai|=()，|Ai|=()|Ai+1|=|Ai|=()|Ai|=Ni|Ai|i=0,1,l|A0|=N0|A0|=N0|A1|=N0(N1|A1|=N0N1+N2+(1)Nl(题目）,m+lm+i,m+l1m+i1,m+l1 m+i,m+l1 m+i,l,第三章习题解答,5证显然，每列中必有两数字相同，共有()种模式，有或两种选择故共有()2种选择()2=6现有7列，=2即必有列在相同的两行选择相同的数字，即有一矩形，四角的数字相等（题目）,32,32,32,76,第三章习题解答,6 证把正方形分成四个的正方形如下图：,12,12,则这点中必有两点落在同一个小正方形内而小正方形内的任两点的距离都小于2,12,（题目）,第三章习题解答,7 证把边长为的三角形分成四个边长为的三角形，如下图：,12,则这点中必有两点落在同一个小三角形中,（题目）,第三章习题解答,8 证整数的个位数的可能取值为，共种可能11个整数中必有个数的个位数相同，即这两个数之差能被整除,（题目）,第三章习题解答,证用反证法。设存在划分 P1P2P3P4P51，326，Pi中无数是两数只差 66，则有一Pi中至少有66个数，A a1,a66，a1a2a66，以下按书上174页的例题证明可得(题目),326 5,第三章习题解答,10解按题意可得如下的带禁区的棋盘其中有阴影的表示禁区,A B C,禁区的棋子多项式为：,R()=R()R()=(1+x)(1+3x+x)=1+4x+4x+x,故方案数3!42!+4 1!1 0!1,2,2,3,（题目）,第三章习题解答,11 证设m个盒子的球的个数是a1,am，各不相等，且有0a1a2am则有a21、amm1，故ai1+2+m1m(m1)与nm(m1)相矛盾！所以必有两个盒子的球数相等,12,12,i=1,m,（题目）,第三章习题解答,12 解(1)方案数(n1)！2,n,(2)设第i个单位的代表相邻的方案集为Ai，i1,2,n|Ai|(1)|Ai|(1)()(2nk1)!2,n,n,n,i=1,k=0,k=0,I(n,k),iI,nk,k,k,k,（题目）,第三章习题解答,13 解令Dnn!(1+)(1)方案数Dm(n!),11!,12!,1n!,m,(2)()Dk(n!)Dn,mk,k,mk,k=0,m,(3)Dm Dn,m,（题目）,第三章习题解答,14 证每列有(m+1)行，只有m种颜色，故一列中必有两格同色同色的个格子的行号有()种取法有m种色，故有m()种同色模式，现有m()+1列，必有两列的同色模式相同即由这两列的对应行上有个格子同色，正好是一个矩形的个角上的格子得证(题目),m+1 2,m+1 2,m+1 2,第三章习题解答,15 解第一门课的顺序有6!种 第二门课的顺序有：D66!()265古总顺序有6!265种（题目）,12!,13!,14!,15!,16!,第三章习题解答,16 解任一点的坐标（a,b）只有如下种可能：(奇数，偶数)、(奇数，奇数)、(偶数，奇数)、(偶数，偶数)。因而5个点中必有两个点模2的格式一样设2(x1x2)，2(y1y2)即x1x22ky1y2l，则三角形面积S,111x1 x2 x3y1 y2 y3,01 1x1 x2 x2x3y1 y2 y2 y3,12,12,011k x2 x3l y2 y3,是整数,（题目）,第三章习题解答,17 解设(x，y)是整点，每个分量模3后有如下表的结果：,(0，0)(0，1)(0，2),(1，0)(1，1)(1，2),(2，0)(2，1)(2，2),若有个点模后的结果落在上表中的同一格中，则这个点的重心是整点,第三章习题解答,若有点占满一行，则点重心是整点；有点占满一列，则点重心是整点；若存在一组均匀分布，则有3点重心是整点由上表可知，若只有8个点，也不能保证有点的重心是整点（因为若每个格子都有点，则只占有个格子，无法保证上面的要求）,下面假设存在个点，其中任点的重心都不是整点,第三章习题解答,则这9个点，至少占有5个格子（因为每格中最多有2个点，否则有3个点的重心为整点），每行最多有格，又=3 所以每行都有点同理，每列都有点,92,52,不妨设第一行2点，第二行2点，第三行1点前2 行有两种模式：,或,这样第三行的点无论在哪一列都构成占满,第三章习题解答,一列或构成一组均匀分布满足前面说的三点重心是整点的情况,故 9个点能保证其中存在个点的重心是整点（题目）,第三章习题解答,