《组合数学课件第三章习题》由会员分享，可在线阅读，更多相关《组合数学课件第三章习题（42页珍藏版）》请在金锄头文库上搜索。
1、 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个点试证其中至少有两点，期
2、间距离小于解：.第三章习题解答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个盒子中去， 试证
3、其中必有两个盒子有相同的球数。解：.第三章习题解答12. n各单位各派两名代表去出席一 会议。 位代表围一圆桌坐下。试问：（1）各单位代表并排坐着的方案 是多少？ （2）各单位的两人互不相邻的方 案数又是多少？ 解：.第三章习题解答13. 一书架有m层，分别放置m类不同 种类的书，每层n册。先将书架上的图书 全部取出清理。清理过程要求不打乱所 有的类别。试问 （1）m类书全不在各自原来层次上 的方案数有多少？ （2）每层的n本书都不在原来位置 上的方案数等于多少？ （3）m层书都不在原来层次，每层 n本书也不在原来位置上的方案数又有多 少？解：.第三章习题解答14. 行 列 的格子同种颜色着色
4、，每格赵一种颜色，其中必 有一个4角同色的矩形。解：.第三章习题解答15. 两名教师分别对6名学生同时进行两 门课程的面试（每名教师各管一门课程 ）每名学生每门面试的时间都是半个小 时，共有多少不同的面试顺序？解：.第三章习题解答16. 在平面直角坐标系中至少任去多少 个整点（两个坐标系都是整数）才能保 证其中存在3个构成三角形（包含3点在 一条直线上）的面积是整数（可以为0） 解：.第三章习题解答17. 在平面直角坐标系中至少任去多少 个整点才能保证存在3个点构成的三角形 的重心是整点？解：.第三章习题解答第三章习题解答1解 设Ai为甲与第i个朋友相遇的会议 集，i1，6则 Ai12 ( )
5、 6 ( )4 ( )3 ( )2 ( )( )28故甲参加会议数为28533 （题目）6 16 26 36 46 56 6第三章习题解答 解 设A3：被3整除的数的集合A5：被5整除的数的集合A7：被7整除的数的集合 所以 A7A5A3 A3A5 A7A5A3 33429 （题目）50035500 357第三章习题解答3 解 每个人的朋友数只能取0，1， n1但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超 过n2故这n个人的朋友数的实际取数只 有n1种可能 ，所以至少有人 的朋友数相等 （题目）n n1第三章习题解答4 解 ( a ) 从n个元素中取k个元的组合， 总
6、含指定的m个元的组合数为( )=( ) 设这m个元为a1，a2，am，Ai为不含ai的 组合(子集)，i=1，m Ai= ( ) Ai1 Ai2 Ail( )( ) Ai( ) + (1) Aij (1) ( ) ( ) n1kn lk nm nk n kmi=1ml=1llj=1i1,il(m , l) lm kn lkml=0nm kmnm nk第三章习题解答( b )令knml个相同的球放入k个不同 的盒子里每盒不空的方案数为( ) 设Ai为第i个盒子为空的方案集，i=1,2,k. | Ai |= ( ), | Ais | = ( )( )= | Ai |= ( )+ (1) Ais (
7、1) ( ) ( )l1 k1k1+l1l l1 k1kj+l1l k+l1l i1,ij(k , j)js=1js=1ki=1kj=1jkj=0jk jkj+l1l 第三章习题解答l个相同的球放入n个不同的盒子里，指定 的m个盒子为空，其他盒子不空的方案数 为( )l1 nm1 第三章习题解答( 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|
8、A1 |=N0(N1|A1|=N0N1+N2+(1) Nl (题目）m+l m+ im+l1 m+ i1m+l1m+ im+l1m+ il第三章习题解答5 证 显然，每列中必有两数字相同，共 有( )种模式，有或两种选择故共 有( )2种选择 ( )2=6现有7列， = 2即必有列在相同的两行选择相 同的数字，即有一矩形，四角的数字相等（题目）3 23 23 27 6第三章习题解答6 证 把正方形分成四个的 正方形如下图：1 21 2则这点中必有两点落在同 一个小正方形内而小正方 形内的任两点的距离都小于 21 2（题目）第三章习题解答7 证 把边长为的三角形分成四个边长 为的三角形，如下图：
9、1 2 则这点中必有两点落在 同一个小三角形中（题目）第三章习题解答8 证 整数的个位数的可能取值为， ，共种可能11个整数中必有 个数的个位数相同，即这两个数之差能 被整除（题目）第三章习题解答 证 用反证法。设存在划分P1P2P3P4P51，326，Pi中无数 是两数只差 66，则有一Pi中至少有66个数， A a1 ,a66 ，a1a2a66 ， 以下按书上174页的例题证明可得(题目)3265第三章习题解答10 解 按题意可得如下的带禁区的棋盘 其中有阴影的表示禁区 A B C 禁区的棋子多项式为： R( )=R( ) R( )=(1+x)(1+3x+x )=1+4x+4x + x 故
10、方案数3!42!+4 1!1 0!1223（题目）第三章习题解答11 证 设m个盒子的球的个数是a1,am， 各不相等，且有0a1a2am则有 a21、amm1，故ai1+2+m1m(m1) 与nm(m1)相矛盾！ 所以必有两个盒子的球数相等1 21 2i=1m（题目）第三章习题解答12 解 ( 1 ) 方案数(n1)！2n( 2 ) 设第i个单位的代表相邻的方案集为 Ai，i1,2 , ,n | Ai | (1 ) | Ai | (1) ( ) (2nk1)! 2nnni=1k=0k=0I( n ,k)iI n kkkk（题目）第三章习题解答13 解 令Dnn!(1 + ) ( 1 )方案数
11、Dm( n! )1 1!1 2!1 n!m( 2 ) ( ) Dk (n!) Dnm kkmkk=0m( 3 ) Dm Dnm（题目）第三章习题解答14 证 每列有(m+1)行，只有m种颜色，故 一列中必有两格同色同色的个格子的行 号有( )种取法有m种色，故有m( ) 种同色模式，现有m( ) +1列，必有两列的同色模式相同即由这两列的对应行上有 个格子同色，正好是一个矩形的个角上 的格子得证 (题目)m+12m+12m+12第三章习题解答15 解 第一门课的顺序有6!种第二门课的顺序有：D66! ( )265古总顺序有6!265种 （题目）1 2!1 3!1 4!1 5!1 6!第三章习题
12、解答16 解 任一点的坐标（a , b）只有如下 种可能：(奇数，偶数)、(奇数，奇数)、 (偶数，奇数)、(偶数，偶数)。因而5个点 中必有两个点模2的格式一样设 2(x1x2)，2(y1y2)即x1x22k y1y2l，则三角形面积 S1 1 1 x1 x2 x3 y1 y2 y30 1 1 x1 x2 x2 x3 y1 y2 y2 y31 21 20 1 1 k x2 x3 l y2 y3是整数（题目）第三章习题解答17 解 设(x，y)是整点，每个分量模3后有 如下表的结果：(0，0) (0，1) (0，2)(1，0) (1，1) (1，2)(2，0) (2，1) (2，2)若有个点模
13、后的结果落在上表中的同 一格中，则这个点的重心是整点第三章习题解答若有点占满一行，则点重心是整点；有点占满一列，则点重心是整点； 若存在一组均匀分布，则有3点重心是整点 由上表可知，若只有8个点，也不能保证有 点的重心是整点（因为若每个格子都有 点，则只占有个格子，无法保证上面的 要求）下面假设存在个点，其中任点的 重心都不是整点第三章习题解答则这9个点，至少占有 5个格子（因 为每格中最多有2个点，否则有3个点的重 心为整点），每行最多有格，又=3所以每行都有点 同理，每列都有点9 25 2不妨设第一行2点，第二行2点，第三行1点 前2 行有两种模式：或这样第三行的点无论在哪一列都构成占满第三章习题解答一列或构成一组均匀分布满足前面说的 三点重心是整点的情况故 9个点能保证其中存在个点的重心是 整点 （题目）第三章习题解答
