组合数学引论课后答案(部分) 下载本文

内容发布更新时间 : 2024/6/18 1:25:56星期一 下面是文章的全部内容请认真阅读。

1.12 证明:对任意的整数N,存在着N的一个倍数,使得它仅有数字0和7组成。(例如,

N=3,我们有3?259=777;N=4,有4?1952=7700;N=5,有5?14=70;……)

1.13

(1) 在一边长为1的等边三角形中任取5个点,则其中必有两个点,该两点的距离至多为

12;

(2) 在一边长为1的等边三角形中任取10个点,则其中必有两个点,该两点的距离至多

1为3;

(3) 确定

mn,使得在一边长为1的等边三角形中任取mn个点,则其中必有两个点,该两

1点的距离至多为n;

1.14 一位学生有37天时间准备考试,根据以往的经验,她知道至多只需要60个小时的复

习时间,她决定每天至少复习1小时,证明:无论她的复习计划怎样,在此期间都存在一些天,她正好复习了13个小时。

1.15 从1,2,…,2n中任选n+1个整数,则其中必有两个数,它们的最大公约数为1

出的数属于同一个鸽巢,即它们的最大公约数为1

1.16 针对1.1节的例6,当m,n不是互素的两个整数时,举例说明例中的结论不一定成立

习题二

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个坐标为整数的点,则其中至少有两个点,由它们所连线段的中点的

坐标也是整数。 证明:

有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只颜色选择,根据鸽巢原理,则必有两个单元格的

颜色相同。另外,每列中两个单元格的不同位置组合有5=10种,这样一列中两个同色单元格

2的位置组合共有10*4=40种情况。

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

2.9 将一个矩形分成(m+1)行mm+1+1列的网格每个格子涂1种颜色,有m种颜色可以选择,

2证明:无论怎么涂色,其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明:

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

2共有 m+1m种情况

2(3)现在有mm+1+1列,根据鸽巢原理,必有两列相同。证明结论成立。

22.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

所以从第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。 证明:

要证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*C66662) C18/3! *C12*C63.4 教室有两排,每排8个座位。现有学生14人,其中的5个人总坐在前排,4个人总坐在

后排,求有多少种方法将学生安排在座位上?

5解:前排8个座位,5人固定,共C8*5!种方法;后排8个座位,4人固定,共C84*4!种方法;5前排和后排还剩7个座位,由剩下的5人挑选5个座位,共C7*5!种方法;则一共有55C8*C84*C7*5!*5!*4!种安排方法。