吉林大学组合数学习题答案.pdfVIP

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