组合数学作业答案

第二章作业答案

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

证明 用100分别除这52个整数，得到的余数必为0, 1,?, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，?，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a和b。若a和b被100除余数相同，则a?b能被100整除。若a和b被100除余数之和是100，则a?b能被100整除。

11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i天她共学习了ai小时。因为她每天至少学习1小时，所以

a1,a2,?,a37和a1?13,a2?13,?,a37?13都是严格单调递增序列。因为总的学习时间

不超过

60

小时，所以a37?60，a37?13?73。a1,a2,?,a37,

a1?13,a2?13,?,a37?13是1和73之间的74个整数，由鸽巢原理知道，它们中存在相

同的整数，有ai和aj?13使得ai?aj?13，ai?aj?13，从第j?1天到第i天她恰好学习了13小时。

14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？ 解 由加强形式的鸽巢原理知道，如果从袋子中取出4?(12?1)?1?45个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。

17. 证明：在一群n?1个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。

证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到n?1的整数。若有两个人的熟人的数目分别是0和n?1，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n个人的熟人的数目是n?1个整数之一，必有两个人有相同数目的熟人。

第三章作业答案

6. 有多少使下列性质同时成立的大于5400的整数？ (a) 各位数字互异。

(b) 数字2和7不出现。

解 因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。 ① 考虑8位整数。最高位不能为0，因此8位整数有7?P(7,7)个。 ② 考虑7位整数。最高位不能为0，因此8位整数有7?P(7,6)个。

③ 考虑6位整数。最高位不能为0，因此8位整数有7?P(7,5)个。 ④ 考虑5位整数。最高位不能为0，因此8位整数有7?P(7,4)个。

⑤ 考虑4位整数。若千位数字大于5，有3?P(7,3)个。若千位数字等于5，则百位数字必须大于等于4，有4?P(6,2)个。 根据加法原理，符合条件的整数的个数为

7?P(7,7)?7?P(7,6)?7?P(7,5)?7?P(7,4)?3?P(7,3)?4?P(6,2)?94830

8. 15人围坐一个圆桌。如果B拒绝挨着A坐，有多少种围坐方式？如果B只拒绝坐在A的右侧，又有多少种围坐方式？

解 15人围坐一个圆桌，有14!种围坐方式。若B固定坐在A的左侧，则可将BA看作一个整体，有13!种围坐方式。若B固定坐在A的右侧，则可将AB看作一个整体，有13!种围坐方式。因此，B不挨着A坐的围坐方式有14!?2?13!?12?13!种，B不坐在A的右侧的围坐方式有14!?13!?13?13!种。

11. 从15个球员的集合中选人组成11个球员的足球队，其中5人只能踢后卫，8人只能踢边卫，2人既能踢后卫又能踢边卫。假设足球队有7个人踢边卫4个人踢后卫，确定足球队可能的组队方法数。

解 设甲和乙既能踢后卫又能踢边卫。

?8??5?若甲和乙均不入选，组队方法数为??7????4??。

????若甲和乙均入选，组队方法数为??7????2??+??6?????????8??5??8??5??8??5???3??+??5????4??。 ???????8??5??8??5???4??。 ???8??5??8??5???4??。 ??若甲入选且乙不入选，组队方法数为??7????3??+??6????????若乙入选且甲不入选，组队方法数也为??7????3??+??6????????因此，组队方法数总共为

??8??5??8??5???8??5??8??5??8??5??8??5???7????4??+??7????2??+??6????3??+??5????4??+2???7????3?????6????4??????=1120 ??????????????????????????21. 一位秘书在距离家以东9个街区、以北7个街区的一座大楼里工作。每天他都要步行16

个街区去上班。

(a) 对他来说可能有多少不同的路线？

(b) 如果在他家以东4个街区、以北3个街区开始向东方向的街区在水下（而他又不会游泳），则有多少条不同的路线？

解 (a) 用E表示向东步行1个街区，用N表示向北步行1个街区。因为该秘书需要向东步行9个街区，向北步行7个街区，总共步行16个街区，因此他的上班路线是多重集

{9?E,7?N}的排列。这样的排列的个数为

16!?11440。 9!7!(b) 若他从水下的街区走过，则他先要走到离家以东4个街区、以北3个街区的地方，再向

东走一个街区，最后走到工作的大楼。他从家走到离家以东4个街区、以北3个街区的地方的路线的数目是多重集{4?E,3?N}的排列数，即

7!?35。他从离家以东5个街区、4!3!以北3个街区的地方走到工作的大楼的路线的数目是多重集{4?E,4?N}的排列数，即

8!?70。所以，如果他从水下的街区走过，则他可能有的路线数是35?70?2450。因4!4!此，如果他不从水下的街区走过，则他可能有的路线数是11440?2450?8990。 26. 确定多重集S?{3?a,4?b,5?c}的10-排列的个数。 解 S的有1个a ，4个b， 5个c的10-排列的个数为

10!?1260。

1!4!5!S的有3个a ，2个b， 5个c的10-排列的个数为

10!?2520。

3!2!5!10!?4200。

3!4!3!10!?2520。

3!2!5!10!?3150。

2!4!4!S的有3个a ，4个b ，3个c的10-排列的个数为

S的有2个a， 3个b， 5个c的10-排列的个数为

S的有2个a， 4个b， 4个c的10-排列的个数为

S的有3个a 3个b 4个c的10-排列的个数为

10!?4200。

3!4!3!S的10-排列的个数为1260?2?2520?2?4200?3150?17850。

31. 方程x1?x2?x3?x4?30有多少满足x1?2，x2?0，x3??5，x4?8的整数解？ 解 进行变量代换：

y1?x1?2，y2?x2，y3?x3?5，y4?x4?8

则方程变为

y1?y2?y3?y4?25

原方程满足条件的解的个数等于新方程的非负整数解的个数。新方程的非负整数解的个数为

?25?4?1??28??28?28?27?26??3276 ?25?????25?????3???3!??????第五章作业答案

8. 用二项式定理证明

2?证明 由二项式定理知道

nk?0?(?1)nnnk?n?n?k??k??3??

(x?y)?令x?3，y??1得

?n?n?kk???k??xy k?0??n?n?n?kkk?n?n?k?2?(3?(?1))???3(?1)?(?1)???k??k??3

??k?0??k?0nnn18. 求和

1?n?1?n?1?n?n1?n????????? 1????????????(?1)??2?1?3?2?4?3?n?1?n?解法1 对任意非负整数n和k，(k?1)??因此，

1?n?n?1??n?1?n?1?1?n????????，即，?(n?1)????????n?1?k?1?k?1?k??k?1??k?1?n?1?n?1?n?n1?n????????? ?????(?1)????????2?1?3?2?4?3?n?1?n?

(?1)k??k?0k?1?n?n(?1)k??k????n?1??k?0?n?1?1n?1k?1?n?1?????(?1)?k?1?n?1??k??????k?1

1n?11n?1111k?n?1?k?n?1????? ??(?1)??(?1)??0?????k??k?n?1n?1k?1n?1n?1n?1????k?0k?n?k(?1)???k??x

??k?0n解法2 由二项式定理知道

(1?x)?两边分别求积分得

n