第七章组合数学（二）.pptVIP

第七章 组合数学 7.4鸽巢原理 定理1 鸽巢原理 n+1或更多的物体放入n个盒子，则至少有一个盒子包含2个或更多的物体。 证明：假定n个盒子中没有一个盒子包含的物体多于1个，那么物体总数至多是n，这与至少有n+1个物体矛盾。 例 367个人中必有2个人的生日相同 例3 百分制成绩，有多少学生时必有相同成绩的学生？ 解 学生人数大于100人时。 例 边长为2的正方形中任意取5个点，必有两个点间的距离 例 边长为1的正六边形中任意取7个点，必有两个点间的距离≤1 定理2 推广的鸽巢原理 n物体放入k个盒子，则至少有一个盒子包含至少?n/k?个物体 证明: 假定没有盒子包含了比?n/k?-1多的物体，那么物体总数至多是K(?n/k?-1)k(((?n/k?)+1)-1)=N 这里用到不等式?n/k??n/k?+1。这与存在有总数n个物体矛盾。 例5 5分制成绩，有多少学生时必有6个学生的成绩相同 解 为保证至少6个学生得到相同的分数所需的最少学生数是使得?n/5?=6的最小整数n。这样的最小整数是n=5*5+1=26。于是，26是保证至少6个学生得到相同分数所需的最少学生数。 例7 一个月30天，某棒球队一天至少打一场比赛，但至多打45场。证明一定有连续的若干天内，这个队恰好打了14场。 证明： 令aj是在这个月的第j天或第j天之前所打的场数，则a1, a2,…a30是不同正整数的一个递增序列，其中1?aj?45。从而a1+14，a2+14，…，a30+14也是不同正整数的一个递增序列，其中15? aj+14?59。 60个正整数a1, a2,…a30, a1+14，a2+14，…，a30+14全都小于或等于59。因此，由鸽巢原理有两个正整数相等。因为这个整数aj(j=1,2,…,30)都不相同，并且aj+14(j=1,2,…,30)也不相同，一定存在下标i和j满足ai=aj+14。这意味着从第j+1天到第i天恰好打了14场比赛。 例10 假定任意6个人中，任意两个人或者是朋友或者是敌人，证明这组人中，或存在 3个人彼此都是朋友，或存在3个人彼此都是敌人。 证明: 令A是6个人中的一人，组里其他5个人中至少有3个人是A的朋友，或至少有3个人是A的敌人。这可从推广的鸽巢原理得出，因为当5个物体被分成两个集合时，其中的一个集合至少有?5/2?=3个元素。若是前一种情况，假定B，C，D是A的朋友。如果这三个人中有两个人也是朋友，那么这2个人和A构成彼此是朋友的3人组。否则，B，C和D构成彼此为敌人的3人组。对于后一种情况的证明，当A存在3个或更多的敌人时，可以用类似的方法来处理。 习题 1.一个碗里有10个红球和10个篮球。一个女士不看着球而随机地选取。 a)她必须选多少个球才能保证至少有3个球是同色的？ b)她必须选多少个球才能保证至少有3个球是蓝色的？ 2.证明如果f是从S到T的函数，其中S和T是有穷集，满足|S||T|，那么在S中存在元素s1和s2 使得f(s1)=f(s2),或者换句话说，f不是一对一的。 3.证明在至少2个人的聚会中，存在2个人认识人数相同的其他人。 * *