组合数学引论课后答案(2)

同，也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。

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

（1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。

+1种，这样一 （2）每列中两个单元格的不同位置组合有(m2)+1m种情况 列中两个同色单元格的位置组合共有 (m2)+1+1列，根据鸽巢原理，必有两列相同。证 （3）现在有m(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

24=aj-ai=(b1+b2+b3+…+bi+…+bj)-(b1+b2+…+bi)=bi+1+bi+2+...+bj

所以从第i+1天到第j天这连续j-i天中，她正好做了24次实验。

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个数

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个人总坐在后排，求有多少种方法将学生安排在座位上？

解：前排8个座位，5人固定，共C85*5!种方法；后排8个座位，4人固定，共C84*4!种方法；前排和后排还剩7个座位，由剩下的5人挑选5个座位，共C75*5!种方法；则一共有

55C8*C84*C7*5!*5!*4!种安排方法。

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库组合数学引论课后答案(2)在线全文阅读。