组合数学 课后答案

习题二2.1 证明：在一个至少有 2 人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为［l,n-l］，由鸽巢原理知，n 个人认识的人数有 n-1 种，那么至少有 2 个人认识的人数相同。假设有 1 人谁都不认识：那么其他 n-1 人认识的人数都为［l,n-2］,由鸽巢原理知，n-1 个人认识的人数有 n-2 种，那么至少有 2 个人认识的人数相同假设至少有两人谁都不认识，则认识的人数为 0 的至少有两人。2.2任取 11 个整数，求证其中至少有两个数的差是 10 的整数倍。证明：对于任意的一个整数，它除以 10 的余数只能有 10 种情况：0,1,…，9。现在有 11 个整数，由鸽巢原理知，至少有 2个整数的余数相同，则这两个整数的差必是 10 的整数倍。2.3证明：平面上任取 5 个坐标为整数的点,则其中至少有两个点,由它们所连线段的中点的坐标也是整数。2.3 证明：有 5 个坐标,每个坐标只有 4 种可能的情况：（奇数,偶数）；（奇数,奇数）；（偶数,偶数）；（偶数,奇数）。由鸽巢原理知,至少有 2 个坐标的情况相同。又要想使中点的坐标也是整数,则其两点连线的坐标之和为偶数。因为奇数+奇数=偶数；偶数+偶数=偶数。因此只需找以上 2 个情况相同的点。而已证明：存在至少 2 个坐标的情况相同。证明成立。2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有 100 个人得到相同的结果？证明：根据推论 2.2.1，若将 3*（100-1）+1=298 个人得到 3 种结果，必有100 人得到相同结果。2.5 一个袋子里装了 100 个苹果、100 个香蕉、100 个橘子和100 个梨。那么至少取出多少水果后能够保证已经拿出 20个相同种类的水果？证明：根据推论 2.2.1，若将 4*（20-1）+1=77 个水果取出，必有 20 个相同种类的水果。2.6证明：在任意选取的 n+2 个正整数中存在两个正整数，其差或和能被 2n 整除。（书上例题 2.1.3）证明：对于任意一个整数，它除以 2n 的余数显然只有 2n 种情况，即:0,1,2，…，2n-2，2n-l。而现在有任意给定的 n+2 个整数，我们需要构造 n+1 个盒子，即对上面 2n 个余数进行分组，共 n+1 组：{0},{1，2n-1},{2，2n-2},{3,2n-3},...，{n-1,n+1}，{n}。根据鸽巢原理，n+2 个整数，必有两个整数除以 2n 落入上面 n+1个盒子里中的一个，若是{0}或{n}则说明它们的和...