组合数学课后答案

精品文档。1欢迎下载作业习题答案习题二2.1 证明：在一个至少有2 人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1 种，那么至少有2 个人认识的人数相同。假设有 1 人谁都不认识： 那么其他 n-1 人认识的人数都为[1,n-2]，由鸽巢原理知， n-1个人认识的人数有n-2 种，那么至少有2 个人认识的人数相同。2.3 证明： 平面上任取5 个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：方法一：有 5 个坐标， 每个坐标只有4 种可能的情况：（奇数， 偶数）；（奇数， 奇数）；（偶数， 偶数）；（偶数，奇数） 。由鸽巢原理知，至少有2 个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数 +奇数 = 偶数； 偶数 +偶数 =偶数。因此只需找以上2 个情况相同的点。而已证明：存在至少2 个坐标的情况相同。证明成立。方法二：对于平面上的任意整数坐标的点而言，其坐标值对2 取模后的可能取值只有4 种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5 个点中必有2 个点的坐标对2 取模后是相同类型的，那么这两点的连线中点也必为整数。2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定” ，至少有多少人参加才能保证必有100 个人得到相同的结果？证明：根据推论2.2.1 ，若将 3*（100-1 ）+1=298 个人得到 3 种结果， 必有 100 人得到相同结果。2.9 将一个矩形分成( m+1)行112mm列的网格每个格子涂1 种颜色，有m种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4 个角上的格子被涂上同一种颜色。证明：（ 1）对每一列而言，有（m+1）行， m种颜色，有鸽巢原理，则必有两个单元格颜色相同。（ 2）每列中两个单元格的不同位置组合有12m种，这样一列中两个同色单元格的位置组合共有12mm种情况精品文档。2欢迎下载（ 3）现在有112mm列，根据鸽巢原理，必有两列相同。证明结论成立。2.11 证明：从 S={1,3,5,⋯,599} 这 300 个奇数中任意选取101 个数，在所选出的数中一定存在 2 个数，它们之间最多差4。证明：将 S划分为 {1,3,5}，{7,9,11}⋯⋯ ,{ 595,597,599}共100组，由鸽巢原理知任意选取101个数中必存在 2个数来自同一组，即其差最多为4. 2....