组合数学习题答案

习题二

2.1 证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明：

假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少

有2个人认识的人数相同。

假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。

假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 2.2 任取11个整数，求证其中至少有两个数的差是10的整数倍。

证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。

2.3 证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 2.3证明：

有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。

2.4 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必

有100个人得到相同的结果？ 证明：

根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。

2.5 一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个

相同种类的水果？ 证明：

根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。

2.6 证明：在任意选取的n+2个正整数中存在两个正整数，其差或和能被2n整除。（书上例题2.1.3）

证明：对于任意一个整数，它除以2n的余数显然只有2n种情况，即：0，1，2，…，2n-2，2n-1。而现在有任意给定的n+2个整数，我们需要构造n+1个盒子，即对上面2n个余数进行分组，共n+1组： {0},{1，2n-1},{2，2n-2},{3,2n-3},…，{n-1,n+1}，{n}。

根据鸽巢原理，n+2个整数，必有两个整数除以2n落入上面n+1个盒子里中的一个，若是{0}或{n}则说明它们的和及差都能被2n整除；若是剩下n-1组，因为一组有两个余数，余数相同则它们的差能被2n整除，不同则它们的和能被2n整除。证明成立。

2.7 一个网站在9天中被访问了1800次，证明：存在连续的3天，这个网站的访问量超多600次。 证明：

设网站在9天中访问数分别为a1，a2，...，a9 其中a1+a2+...+a9 = 1800， 令a1+a2+a3 = b1，a4+a5+a6 = b2，a7+a8+a9 = b3

因为（b1+b2+b3）/3 >= 600 由推论2.2.2知，b1，b2，b3中至少有一个数大于等于600。 所以存在有连续的三天，访问量大于等于600次。

2.8 将一个矩形分成5行41列的网格，每个格子涂1种颜色，有4种颜色可以选择，证明：无论怎样涂色，其中必有一

个由格子构成的矩形的4个角上的格子被涂上同一种颜色。

证明：首先对一列而言，因为有5行，只有4只颜色选择，根据鸽巢原理，则必有两个单元格的颜色相同。另外，每列中两个单元格的不同位置组合有

()52=10种，这样一列中两个同色单元格的位置组合共有10*4=40种情况。

而现在共有41列，根据鸽巢原理，无论怎样涂色，则必有两列相同，也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。

2.9 将一个矩形分成(m+1)行m()m+1+1列的网格每个格子涂1种颜色，有m种颜色可以选择，证明：无论怎么涂色，2其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明：

（1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有

()m+12种，这样一列中两个同色单元格的位置组合共有

()m+1m种情况 2 （3）现在有m+1+1(m2)列，根据鸽巢原理，必有两列相同。证明结论成立。

2.10 一名实验员在50天里每天至少做一次实验，而实验总次数不超过75。证明一定存在连续的若干天，她正好做了24

次实验。

证明：令b1，b2，...，b50 分别为这50天中他每天的实验数，并做部分和 a1 = b1，a2 = b1+b2 ，。。

a50 = b1+b2+...+b50 .

由题，bi>=1(1<=i<=50)且a50<=75 所以 1<=a1

考虑数列 a1，a2，...，a50，a1+24，a2+24，a50+24，它们都在1与75+24=99之间。

由鸽巢原理知，其中必有两项相等。由（*）知，a1，a2，...，a50互不相等，从而a1+24，...a50+24 也互不相等，所以一定存在1<=i

2.11 证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明：

将S划分为{1,3,5}，{7,9,11}……,{ 595,597,599}共100组，由鸽巢原理知任意选取101个数中必存在2个数来自同一组，即其差最多为4.

2.12 证明：从1~200中任意选取70个数，总有两个数的差是4，5或9。 证明：设这70个数为 a1,a2,…,a70, a1+4,a2+4,…,a70+4, a1+9,a2+9,…,a70+9, 取值范围209，共210个数

b+bi+2+...+bj

2.13 证明：对于任意大于等于2的正整数n，都有R(2,n)=n。 2.13证明：

要证R（2，n）= n，用红蓝两色涂色Kn的边。

当n=2时，R(2,2)=2，因为不管用红还是蓝色都是完全二边形。 假设当n=k时 成立 ，即存在R(2,k)=k（没有一条红边，只有蓝边）， 当n=k+1时，R（2，k+1）

若无红边，要想有完全k+1边形，必得有k+1个点，即R（2，k+1）=k+1。证明成立。

习题三

3.1 有10名大学生被通知参加用人单位的面试，如果5个人被安排在上午面试，5个人被安排在下午面试，则有多少种

不同的安排面试的顺序？ 解：上午的5个人全排列为5！

下午的5个人全排列为5！

5所以有C10*5!*5!?10!，共14400种不同的安排方法。

3.2 某个单位内部的电话号码是4位数字，如果要求数字不能重复，那么最多可有多少个号码？如果第一位数字不能是0，

那么最多能有多少个电话号码？

解：由于数字不能重复，0-9共10个数字，所以最多有10*9*8*7=5040种号码；若第一位不能是0，则最多有9*9*8*7=4536种号码。

3.3 18名排球运动员被分成A,B,C三个组，使得每组有6名运动员，那么有多少种分法？如果是分成三个组（不可区别），

使得每组仍有6名运动员，那么有多少种分法？

666解：1)C18种 *C12*C6 2)

666/3! C18*C12*C63.4 教室有两排，每排8个座位。现有学生14人，其中的5个人总坐在前排，4个人总坐在后排，求有多少种方法将学

生安排在座位上？

5解：前排8个座位，5人固定，共C8*5!种方法；后排8个座位，4人固定，共C84*4!种方法；前排和后排还剩7个

555座位，由剩下的5人挑选5个座位，共C7*C84*C7*5!*5!*4!种安排方法。 *5!种方法；则一共有C8

3.5 将英文字母表中的26个字母排序，要求任意两个元音字母不能相邻，则有多少种排序方法？ 解：先排21个辅音字母，共有21！

再将5个元音插入到22个空隙中，P22

故所求为21!?P22 (插入法)

3.6 有6名先生和6名女士围坐一个圆桌就餐，要求男女交替就坐，则有多少种不同的排坐方式？

解：6男全排列6!；6女全排列6！；6女插入6男的前6个空或者后6个空，即女打头或男打头6!*6!*2；再除以围圈重复得(6!*6!*2)/12=6!*5! 或

55男6的圆排列为5！，对每个男的排列，女要在他们之间的6个位置，进行线性排列6！（而不是5！）。 （圆排列可以通过线性排列来解决）

3.7 15个人围坐一个圆桌开会，如果先生A拒绝和先生B和C相邻，那么有多少种排坐方式？ 解：15人圆排列14！； A与B相邻有2*14!/14=2*13!； A与C相邻有2*14!/14=2*13!； A与BC同时相邻有2*13!/13=2*12!；

于是A不与B、C相邻的坐法共14!- 2*13!- 2*13!+ 2*12!（用到了容斥原理） 3.8 确定多重集M?{3?a,4?b,5?c}的11-排列数？

解：M的11排列=[M-{a}]的11排列+[M-{b}]的11排列+[M-{c}]的11排列，即当然了，容斥原理，生成函数也可以做。 3.9 求方程x1?解：令y11!11!11!=27720

??2!4!5!3!3!5!3!4!4!x2?x3?x4?20，满足x1?2,x2?0,x3?5,x4??1的整数解的个数。

1?x1?2?0,y2?x2?0,y3?x3?5?0,y4?x4?1?0

则有y?14?4?1??17??17?，由定理3.3.3，解个数为： ?y?y?y?141234?14???14???3??680???????n?r?1??20?4?1??17?????2380 ?r????4?????4?3.10 书架上有20卷百科全书，从中选出4卷使得任意两本的卷号都不相邻的选法有多少种？ 解：n=20，r=4，

证明见38页。

3.11 确定(2x-3y)5展开式中x4y和x2y4的系数。 解：1）x4y：C54*(2x)4*(?3y)1，系数为-240

2）x

2y4：系数为0。

3.12 确定(1+x)-5展开式中x4的系数。 解：(1?x)?n?n?r?1?r，n=5，r=4，则系数为4?5?4?1???(?1)?x(?1)??70 ??r?0?r??4??r3.13 确定(x +2y+3z)8展开式中x4y2x2的系数。 解：

8!*22*32?15120

4!*2!*2!?n??n?1??n?2??n?k??n?k?1?????????????0??1??2??k?????k??，其中n,k为正整数。 ??????????解：右边?n?k?1?是（n+k+1）元集合S?{a1,a2,...,an?k?1}上k个元素子集的个数，这些子集可分为以下k+1类：

3.14 证明组合等式：???k??第1类：k元子集中不含a1的子集有 个;

?n?k???k????