组合数学作业答案
第二章作业答案
7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。
证明 用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a 和b 。若a 和b 被100除余数相同，则b a -能被100整除。若a 和b 被100除余数之和是100，则b a +能被100整除。
11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。
证明 设从第一天到第i 天她共学习了i a 小时。因为她每天至少学习1小时，所以3721,,,a a a 和13,,13,133721+++a a a 都是严格单调递增序列。因为总的学习时间不超过60小时，所以6037≤a ，731337≤+a 。3721,,,a a a , 13,,13,133721+++a a a 是1和73之间的74个整数，由鸽巢原理知道，它们中存在相同的整数，有i a 和13+j a 使得13+=j i a a ，13=-j i a a ，从第1+j 天到第i 天她恰好学习了13小时。
14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？ 解 由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4=+-?个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。
17. 证明：在一群1>n 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。
证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到1-n 的整数。若有两个人的熟人的数目分别是0和1-n ，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n 个人的熟人的数目是1-n 个整数之一，必有两个人有相同数目的熟人。
第三章作业答案
6. 有多少使下列性质同时成立的大于5400的整数？
(a) 各位数字互异。
(b) 数字2和7不出现。
解 因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。
① 考虑8位整数。最高位不能为0，因此8位整数有)7,7(7P ?个。
② 考虑7位整数。最高位不能为0，因此8位整数有)6,7(7P ?个。
③ 考虑6位整数。最高位不能为0，因此8位整数有)5,7(7P ?个。
④ 考虑5位整数。最高位不能为0，因此8位整数有)4,7(7P ?个。
⑤ 考虑4位整数。若千位数字大于5，有)3,7(3P ?个。若千位数字等于5，则百位数字必须大于等于4，有)2,6(4P ?个。
根据加法原理，符合条件的整数的个数为
94830)2,6(4)3,7(3)4,7(7)5,7(7)6,7(7)7,7(7=?+?+?+?+?+?P P P P P P
8. 15人围坐一个圆桌。如果B 拒绝挨着A 坐，有多少种围坐方式？如果B 只拒绝坐在A 的右侧，又有多少种围坐方式？
解 15人围坐一个圆桌，有!14种围坐方式。若B 固定坐在A 的左侧，则可将BA 看作一个整体，有!13种围坐方式。若B 固定坐在A 的右侧，则可将AB 看作一个整体，有!13种围坐方式。因此，B 不挨着A 坐的围坐方式有!1312!132!14?=?-种，B 不坐在A 的右侧的围坐方式有!1313!13!14?=-种。
11. 从15个球员的集合中选人组成11个球员的足球队，其中5人只能踢后卫，8人只能踢边卫，2人既能踢后卫又能踢边卫。假设足球队有7个人踢边卫4个人踢后卫，确定足球队可能的组队方法数。
解 设甲和乙既能踢后卫又能踢边卫。
若甲和乙均不入选，组队方法数为???? ??78???
? ??45。
若甲和乙均入选，组队方法数为???? ??78???? ??25+???? ??68???? ??35+???? ??58???
? ??45。
若甲入选且乙不入选，组队方法数为???? ??78???? ??35+???? ??68???
? ??45。
若乙入选且甲不入选，组队方法数也为???? ??78???? ??35+???
? ??68???? ??45。
因此，组队方法数总共为
???? ??78???? ??45+???? ??78???? ??25+???? ??68???? ??35+???? ??58???? ??45+???
? ?????? ?????? ??+???? ?????? ???456835782=1120 21. 一位秘书在距离家以东9个街区、以北7个街区的一座大楼里工作。每天他都要步行16个街区去上班。
(a) 对他来说可能有多少不同的路线？