作业习题答案
习题二
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人得到相同结果。
?m?1?
mm?1
2.9将一个矩形分成(+1)行??列的网格每个格子涂1种颜色.有m种颜色可以选
?2?
择.证明：无论怎么涂色.其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种
颜色。
证明：
（1）对每一列而言.有（m+1）行.m种颜色.有鸽巢原理.则必有两个单元格颜色相同。
?m?1?
（2）每列中两个单元格的不同位置组合有??种.这样一列中两个同色单元格的位置
?2?
?m?1?
组合共有??m种情况
?2?
..
?m?1?
（3）现在有m???1.根据鸽巢原理.必有两列相同。证明结论成立。
?2?
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.12证明：从1~200中任意选取70个数.总有两个数的差是4.5或9。
设从1~200中任意选取的70个数构成一组.即
第一组：a,a,,a；
1270
第二组：a?4,a?4,,a?4；
1270
第三组：a?9,a?9,,a?9；
1270
显然.这三组数均在1~209之间.且共有3*70=210个数.根据鸽巢原理一定有两个数相等.又
因为任取的这70个数均不相同.所以这2个相等的数一定来自不同组.根据不同组的分布讨
论如下：
1）如果这两个数分别来自第一组和第二组.则有a?a?4；
ji
2）如果这两个数分别来自第一组和第三组