组合数学(第四版)课后习题答案.pdf

组合数学(第四版)课后习题答案.pdf

《组合数学(第四版)课后习题答案.pdf》由会员分享，可在线阅读，更多相关《组合数学(第四版)课后习题答案.pdf（4页珍藏版）》请在冰点文库上搜索。

SY0721129刘佳第1页第2章第2章鸽巢原理鸽巢原理2.4练习题1、关于本节中的应用4，证明对于每一个k1，2，21存在连续若干天，在此期间国际象棋大师将恰好下完k局棋（情形k21是在应用4中处理的情况）。

能否判断：

存在连续若干天，在此期间国际象棋大师将恰好下完22局棋？

证明：

证明：

设ia表示在前i天下棋的总数若正好有ia=k,则命题得证。

若不然,如下：

共有11周，每天至少一盘棋，每周下棋不能超过12盘有771i，且13217721aaa21,2,1k有kkakakak13217721观察以下154个整数：

kakakaaaa77217721,每一个数是1到k132之间的整数，其中153132k由鸽巢原理，这154个数中至少存在两个相等的数7721,aaa都不相等，kakaka7721,都不相等ji,，使ia=kaj即这位国际象棋大师在第1j，2j，i天总共下了k盘棋。

综上所述，对于每一个k1，2，21存在连续若干天，在此期间国际象棋大师将恰好下完k局棋。

当k=22时，132+k=154，那么以下154个整数22,22,22,77217721aaaaaa在1到154之间。

）若这154个数都不相同则它们能取到1到154的所有整数，必然有一个数是222222ia，771i等于22的数必然是某个ia，771iSY0721129刘佳第2页则在前i天，这位国际象棋大师总共下了22盘棋。

）若这154个数中存在相同的两个数7721,aaa都不相等，kakaka7721,都不相等ji,，使ia=kaj即这位国际象棋大师在第1j，2j，i天总共下了k盘棋。

综上所述，存在连续若干天，在此期间国际象棋大师将恰好下完22局棋。

5、证明，如果从n3,2,1中选择1n个整数，那么总存在两个整数，它们之间最多差2。

证明：

证明：

把n3,2,1按顺序三个数字分为一组，共有n组，它们是3,2,1，6,5,4，nnn3,13,23由鸽巢原理，从n组整数中，选择1n个整数，至少有两个整数属于同一组且根据以上分组方式，这两个数之间最多相差2即总存在两个整数，它们之间最多差2。

*7、证明，对任意给定的52个整数，存在其中的两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

证明：

证明：

任何一个整数的后两位，都是00，01，02，03，,99之一现在对所有整数按照后两位数的不同分组如下：

00，99,01，98,02，51,49，50，共有51个组。

由鸽巢原理，对于任意给定的52个整数，至少存在两个整数属于同一组。

属于同一组的两个数，要么后两位数相同，要么后两位数相加等于100若这两个数后两位相同，那么这两者的差能被100整除；若这两个数后两位相加等于100，那么两者的和能被100整除。

11、一个学生有37天用来准备考试。

根据过去的经验，她知道她需要不超过60小时的学习时间。

她还希望每天至少学习1个小时。

证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13个小时。

证明：

证明：

设ia表示在前i天学习的小时数。

有37天准备考试，每天至少学习1小时，总学习时间不超过60小时SY0721129刘佳第3页有371i，且6013721aaa我们还有：

73131313143721aaa观察以下74个整数：

13,13,13,37213721aaaaaa每一个数是1到73之间的整数。

由鸽巢原理，这74个数中至少存在两个相等的数3721,aaa都不相等，13,13,133721aaa都不相等ji,，使ia=13ja即这个学生在第1j，2j，i天恰好总共学习了13个小时。

14、一只袋子装了100个苹果、100个香蕉、100个橘子和100个梨。

如果我每分钟从袋子里取出1种水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？

答：

答：

45分钟。

下面证明此结论：

最坏的情况是，拿了若干次之后，还是不能拿到1打相同的水果。

但是这个次数的极限是每种水果拿了11个，也就是总共拿了44次。

因为若拿到第45次时，必定有一种水果拿到了12个（1打）。

也就是说拿45次，肯定至少已拿出了1打相同种类的水果。

15、证明，对任意1n个整数1a，2a，1na存在两个整数ia和ja，ji，使得iaja能够被n整除。

证明：

证明：

任何一个整数被n除的余数是以下n个数之一0，1，2，,1n由鸽巢原理，对于任意1n个整数1a，2a，1na，它们除以n的余数至少有两个相同不妨设这两个数为ia和ja（ji），iaja能够被n整除。

19、）证明，在边长为1的等边三角形内任意选择5个点，存在2个点，其间距离之多为1/2。

证明：

证明：

把边长为1的等边三角形按照右图方式分割为4部分SY0721129刘佳第4页每一部分都是边长为1/2的等边三角形在同一个小三角形中相距最远的2个点距离为1/2由鸽巢原理，任意选择5个点，至少有2个点属于同一个小三角形即：

在边长为1的等边三角形内任意选择5个点，存在2个点，其间距离之多为1/2。

）证明，在边长为1的等边三角形内任意选择10个点，存在2个点，其间距离之多为1/3。

证明：

证明：

把边长为1的等边三角形按照右图方式分割为9部分每一部分都是边长为1/3的等边三角形在同一个小三角形中相距最远的2个点距离为1/3由鸽巢原理，任意选择10个点，至少有2个点属于同一个小三角形即：

在边长为1的等边三角形内任意选择10个点，存在2个点，其间距离之多为1/2。

）确定一个整数nm，使得如果在边长为1的等边三角形内任意选择nm个点，则存在2个点，其间距离之多为1/n。

证明：

证明：

由等边三角形分割成小等边三角形的变化规律：

1，4，9，16，25，2n可知：

边长为1的等边三角形，可以分割为2n个边长为1/n的等边三角形。

边长为1/n的等边三角形内部，相距最远的2个点距离为1/n由鸽巢原理，任意选择12nmn个点，至少有2个点属于同一个小三角形即：

在边长为1的等边三角形内任意选择12nmn个点，存在2个点，其间距离之多为1/n。