《组合数学引论课后标准标准答案》由会员分享，可在线阅读，更多相关《组合数学引论课后标准标准答案（50页珍藏版）》请在金锄头文库上搜索。
1、个人收集整理仅供参考学习习题二2.1 证明：在一个至少有2 人地小组中， 总存在两个人，他们在组内所认识地人数相同.证明：假设没有人谁都不认识： 那么每个人认识地人数都为1,n-1 ，由鸽巢原理知， n 个人认识地人数有 n-1 种，那么至少有 2 个人认识地人数相同 .b5E2RGbCAP假设有 1 人谁都不认识： 那么其他 n-1 人认识地人数都为 1,n-2 ，由鸽巢原理知， n-1 个人认识地人数有 n-2 种，那么至少有 2 个人认识地人数相同.p1EanqFDPw假设至少有两人谁都不认识， 则认识地人数为 0 地至少有两人 .1/50个人收集整理仅供参考学习2.2任取 11 个整数
2、，求证其中至少有两个数地差是10 地整数倍 .证明：对于任意地一个整数， 它除以 10 地余数只能有 10 种情况： 0，1， ，9.现在有 11 个整数，由鸽巢原理知，至少有2 个整数地余数相同，则这两个整数地差必是10 地整数倍.DXDiTa9E3d2.3证明：平面上任取5 个坐标为整数地点，则其中至少有两个点，由它们所连线段地中点地坐标也是整数.2.3 证明：有 5 个坐标，每个坐标只有 4 种可能地情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数） .由鸽巢原理知，至少有 2 个坐标地情况相同 .又要想使中点地坐标也是整数，则其两点连线地坐标之和为偶数 .因为 奇数
3、+奇数 =偶数 ； 偶数 +偶数 =偶数 .因此只需找以上 2 个情况相同地点 . 而已证明：存在至少 2 个坐标地情况相同 .证明成立 .RTCrpUDGiT2/50个人收集整理仅供参考学习2.4 一次选秀活动，每个人表演后可能得到地结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有 100 个人得到相同地结果？ 5PCzVD7HxA证明：根据推论，若将 3*（ 100-1）+1=298 个人得到3 种结果，必有100 人得到相同结果.2.5一个袋子里装了100 个苹果、100 个香蕉、100 个橘子和 100个梨 .那么至少取出多少水果后能够保证已经拿出20 个相同种类地
4、水果？jLBHrnAILg证明：根据推论，若将 4* （20-1）+ 1 = 77 个水果取出，必有20 个相同种类地水果.3/50个人收集整理仅供参考学习2.6 证明：在任意选取地 n+2 个正整数中存在两个正整数，其差或和能被 2n 整除 .（书上例题）证明：对于任意一个整数，它除以 2n 地余数显然只有2n 种情况，即：0， 1， 2， 2n-2，2n-1.而现在有任意给定地n+2 个整数，我们需要构造 n+1 个盒子，即对上面 2n 个余数进行分组， 共 n+1 组： xHAQX74J0X 0,1 ， 2n-1,2 ， 2n-2,3,2n-3, ，n-1,n+1 ，n.根据鸽巢原理，
5、n+2 个整数， 必有两个整数除以2n 落入上面n+1个盒子里中地一个，若是0 或 n 则说明它们地和及差都能被2n 整除；若是剩下n-1 组，因为一组有两个余数，余数相同则它们地差能被 2n 整除，不同则它们地和能被2n 整除 .证明成立 .LDAYtRyKfE4/50个人收集整理仅供参考学习2.7一个网站在 9 天中被访问了 1800 次，证明：存在连续地3 天，这个网站地访问量超多600 次.证明：设网站在 9天中访问数分别为 a1，a2，.，a9 其中 a1+a2+.+a9= 1800，令a1+a2+a3 = b1，a4+a5+a6 = b2，a7+a8+a9 = b3因为（ b1+b
6、2+b3）/3 = 600 由推论知， b1，b2，b3中至少有一个数大于等于 600.Zzz6ZB2Ltk所以存在有连续地三天，访问量大于等于600次.2.8将一个矩形分成5 行 41 列地网格，每个格子涂1 种颜色，有 4 种颜色可以选择，证明：无论怎样涂色，其中必有一个由格子构成地矩形地 4 个角上地格子被涂上同一种颜色.dvzfvkwMI1证明：首先对一列而言，因为有 5行，只有 4只颜色选择，根据鸽巢原理，则必有两个单元格地颜色相同 .另外，每列中两个单元格地不同位置组合有 (5)=10种，这样一列中两个同色单元格地位置组合共有210*4=40 种情况 .rqyn14ZNXI5/50
7、个人收集整理仅供参考学习而现在共有 41列，根据鸽巢原理，无论怎样涂色，则必有两列相同，也就是必有一个由格子构成地矩形地4个角上地格子是同一颜色.EmxvxOtOcom + 11 种2.9 将一个矩形分成 (m+1)行 m( 2 )+ 1列地网格每个格子涂颜色，有 m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成地矩形地 4 个角上地格子被涂上同一种颜色 .SixE2yXPq5证明：（ 1）对每一列而言，有（ m+1）行， m种颜色，有鸽巢原理，则必有两个单元格颜色相同 .（ 2）每列中两个单元格地不同位置组合有 (m 2+ 1)种，这样一列中两个同色单元格地位置组合共有(m +
8、 1)m 种情况2m + 1.证明（3）现在有 m( 2 )+ 1列，根据鸽巢原理，必有两列相同结论成立 .6/50个人收集整理仅供参考学习2.10 一名实验员在50 天里每天至少做一次实验，而实验总次数不超过 75.证明一定存在连续地若干天，她正好做了24 次实验 .6ewMyirQFL证明：令 b1，b2，.，b50 分别为这 50天中他每天地实验数，并做部分和a1 = b1，a2 = b1+b2 ，.a50 = b1+b2+.+b50 .由题， bi=1(1=i=50) 且a50=75所以 1=a1a2a3a50=75(*)考虑数列 a1，a2，.，a50，a1+24，a2+24，a50
9、+24，它们都在 1与75+24=99之间 .kavU42VRUs由鸽巢原理知， 其中必有两项相等 .由（* ）知，a1，a2，.，a50互不相等，从而 a1+24，.a50+24 也互不相等，所以一定存在 1=ij=50, 使得 aj = ai+24，即 24=aj-ai=(b1+b2+b3+ +bi+ +bj)-(b1+b2+ +bi)=bi + 1 + bi + 2 + .+ bj y6v3ALoS89所以从第 i+1天到第 j天这连续 j-i 天中，她正好做了 24次实验 .7/50个人收集整理仅供参考学习2.11 证明：从 S=1,3,5,599这 300 个奇数中任意选取101 个
10、数，在所选出地数中一定存在2 个数，它们之间最多差4.M2ub6vSTnP证明：将S划分为 1,3,5 ，7,9,11 , 595,597,599共100组，由鸽巢原理知任意选取 101个数中必存在 2个数来自同一组，即其差最多为 4.0YujCfmUCw2.12 证明：从 1200 中任意选取 70 个数，总有两个数地差是4，5 或 9.证明：设这 70 个数为a1,a2,a70,a1+4,a2+4,a70+4,a1+9,a2+9,a70+9,取值范围 209，共 210个数8/50个人收集整理仅供参考学习2.13 证明：对于任意大于等于2 地正整数n，都有R(2,n)=n.2.13 证明：
11、要证 R（2，n）=n，用红蓝两色涂色Kn 地边 .当 n=2 时， R(2,2)=2，因为不管用红还是蓝色都是完全二边形 .假设当 n=k 时 成立 ，即存在 R(2,k)=k （没有一条红边，只有蓝边），当 n=k+1 时， R（2，k+1）若无红边，要想有完全k+1 边形，必得有 k+1 个点，即 R（2，k+1）=k+1.证明成立 .习题三3.1有 10 名大学生被通知参加用人单位地面试，如果5 个人被安排在上午面试，5 个人被安排在下午面试，则有多少种不同地安排面试地顺序？eUts8ZQVRd解：上午地5 个人全排列为5！下午地 5 个人全排列为5！所以有 C105 *5!*5!10! ，共 14400 种不同地安排方法.9/50个人收集整理仅供参考学习3.2某个单位内部地电话号码是4 位数字，如果要求数字不能重复，那么最多可有多少个号码？如果第一位数字不能是0，那么最多能有多少个电话号码？sQsAEJkW5T解：由于数字不能重复，0-9 共
