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

SY0721129刘佳—第1页—第2章鸽巢原理2.4练习题1、关于本节中的应用4，证明对于每一个k1，2，…，21存在连续若干天，在此期间国际象棋大师将恰好下完k局棋（情形k21是在应用4中处理的情况）。能否判断：存在连续若干天，在此期间国际象棋大师将恰好下完22局棋？证明：设ia表示在前i天下棋的总数若正好有ia=k,则命题得证。若不然,如下：∵共有11周，每天至少一盘棋，每周下棋不能超过12盘∴有771i，且13217721aaa21,,2,1k有kkakakak13217721观察以下154个整数：kakakaaaa77217721,,,,,,,每一个数是1到k132之间的整数，其中153132k由鸽巢原理，这154个数中至少存在两个相等的数∵7721,,,aaa都不相等，kakaka7721,,,都不相等∴ji,，使ia=kaj即这位国际象棋大师在第1j，2j，…，i天总共下了k盘棋。综上所述，对于每一个k1，2，…，21存在连续若干天，在此期间国际象棋大师将恰好下完k局棋。□当k=22时，132+k=154，那么以下154个整数22,,22,22,,,,77217721aaaaaa在1到154之间。ⅰ）若这154个数都不相同则它们能取到1到154的所有整数，必然有一个数是22∵2222ia，771i∴等于22的数必然是某个ia，771iSY0721129刘佳—第2页—则在前i天，这位国际象棋大师总共下了22盘棋。ⅱ）若这154个数中存在相同的两个数∵7721,,,aaa都不相等，kakaka7721,,,都不相等∴ji,，使ia=kaj即这位国际象棋大师在第1j，2j，…，i天总共下了k盘棋。综上所述，存在连续若干天，在此期间国际象棋大师将恰好下完22局棋。□5、证明，如果从n3,,2,1中选择1n个整数，那么总存在两个整数，它们之间最多差2。证明：把n3,,2,1按顺序三个数字分为一组，共有n组，它们是3,2,1，6,5,4，…，nnn3,13,23由鸽巢原理，从n组整数中，选择1n个整数，至少有两个整数属于同一组且根据以上分组方式，这两个数之间最多相差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页—∴有371i，且6013721aaa我们还有：73131313143721aaa观察以下74个整数：13,,13,13,,,,37213721aaaaaa每一个数是1到73之间的整数。由鸽巢原理，这74个数中至少存在两个相等的数∵3721,,,aaa都不相等，13,,13,133721aaa都不相等∴ji,，使ia=13ja即这个学生在第1j，2j，…，i天恰好总共学习了13个小时。□14、一只袋子装了100个苹果、100个香蕉、100个橘子和100个梨。如果我每分钟从袋子里取出1种水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？答：45分钟。下面证明此结论：最坏的情况是，拿了若干次之后，还是不能拿到1打相同的水果。但是这个次数的极限是每种水果拿了11个，也就是总共拿了44次。因为若拿到第45次时，必定有一种水果拿到了12个（1打）。也就是说拿45次，肯定至少已拿出了1打相同种类的水果。□15、证明，对任意1n个整数1a，2a，…，1na存在两个整数ia和ja，ji，使得ia－ja能够被n整除。证明：任何一个整数被n除的余数是以下n个数之一0，1，2，…,1n由鸽巢原理，对于任意1n个整数1a，2a，…，1na，它们除以n的余数至少有两个相同不妨设这两个数为ia和ja（ji），ia－ja能够被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由鸽巢原理，任意选择12nmn个点，至少有2个点属于同一个小三角形即：在边长为1的等边三角形内任意选择12nmn个点，存在2个点，其间距离之多为1/n。□