6
需要注意以下事实： 1、如果某台计算机不与其它机器相连，那么没有一台计算 机连接到所有其它5台机器。（取0取不到5）。 2、如果一台计算机连接到所有其它5台机器，那就没有不 与其它机器相连的计算机。（取5取不到0）。
例5的证明 的证明 证明：因为有6台计算机，连接到同一台 计算机的其它机器的数在0～5之间，但 是0和5不能同时出现。 于是1台计算机相连的机器数最多有5 种可能，由鸽巢原理知在6台计算机中至 少有两台连接的其它机器数相等。
鸽洞原理
信息安全所 明俊峰
1
3.3 鸽巢原理
组合数学中解决计数问题 计数问题的一个工具。 计数问题 假定一群鸽子飞入一组巢安歇，如果鸽子 比鸽巢多，那么一定至少有一个鸽巢里有两只 或两只以上的鸽子。 这个原理除了鸽子和鸽巢外也可用于其它 对象，因此也称为（狄利克莱，德国，19世纪） 抽屉原理、鞋盒原理 鞋盒原理等。 抽屉原理 鞋盒原理
b
f 若将 7 个点放入正三角形 bcd中， 由鸽巢原理知： 在 bcf、 cdf、 c a bdf内，至少有一个三角形中存在 三个点。 取这3个点构成的小三角形的面积一 定不会超过 ( 3 / 12 ) a 2 。
a
a d
10
例7 某比赛，在30天内总共安排了45场比 赛，每天至少赛一场。证明一定存在有 连续的若干天内一共恰好比赛了14场。
17
结
束
18
15
a
（1）a连接的5条边中一定有3条黑色或 连接的5条边中一定有3 红色的，不妨设有三条黑色的。
16
a
b d
a
b d
c c 图 1 图 2 （2）如果与a连接的三角形b c d中 有一条黑边， 那么即可构成一个黑色三角形abc ，这表明a、b、 c三人不认识，如图1。 否则b、c、d本身一定构成一个红色三角形， 这表明a、b、c三人互相认识，如图2。 证明完毕。
4
推广的鸽巢原理
表述形式一 当盒子仅有 N 个，而物体的数目大于 m×N时，则必有一个盒子中至少有 m＋1 或 多于 m＋1 个物体。 表述形式二 如果 m 个物体放入N个盒子，那么至少 有一个盒子包含了至少 m / N 个物体。
5
推广的鸽巢原理 的例题 例4：在 100 个人中至少有 100/12 = 9 个人 出生在同一个月。 例5：假定某计算机网络由6台计算机组 成。每台计算机直接连接到0台或者更多 的其它计算机。证明网络中至少有两台 计算机直接相连相同数目的其它计算机。
7
鸽巢原理的巧妙运用
难点： 构造 放入的 物体 和 存放物体的盒子 盒子。 盒子
8
例6 在边长为 a 的正三角形内，任取7个 点，证明其中必有3个点连成的小三角形 其面积不超过 ( 3 / 12 ) a 2 。
9பைடு நூலகம்
证明：将正三角形重心记为 f 。 则图中 bcf、 cdf、 bdf 面积相等。 且Sbcf＝1/3 Sbcd= ( 3 / 12 ) a 2
2
鸽巢原理
如果 K＋1 个或更多的物体放入 K 个 盒子，那么至少有一个盒子含 2 个或更多 的物体。
3
鸽巢原理例题
例1：在一组367个人中一定至少有2个人生日相同。 这是由于只有最多只有366个可能的生日。 例2：任取 27 个英文单词，一定至少有2个单词的首字 母相同。 因为英文字母表中只有26个字母。 例3：如果考试成绩是从 0 到 100 的整数，那么在102 个学生中一定至少有两个学生成绩相同。
11
证明：令 ai 是本月第 i 天前（包括第i天）所打场 数的总和。 则 a1、a2、a3 …a30 是由不同正整数构 成的一个严格递增的数列,其中 1 ≤ a i ≤ 45 构造另外一个数列： ai＋14 。 从而： a 1 + 14 、 a 2 + 14 、 a 3 + 14 a 30 + 14 也是一个严格递增的数列，并且： ≤ a i＋14 ≤ 59 15 两个数列中的60个正整数，全都小于或等于 59。因此，由鸽巢原理知：必有两个正整数相等。 又因为ai （i＝1、2… 30）都不相同，并且 ai ＋14 （i＝1、2… 30）也都不相同，因此一定存在下标 i 和 j ，满足 a j = a i + 14 。这意味着从第 i＋1 天起，到第 j 天恰好打了14 场球。 推广 12
练习题
把132个球放入到77个盒子内，盒子排成 一行，每个盒子至少放一个球。证明无 论如何怎样放，一定存在着相邻的某几 个盒子内恰好放有21个球。
13
例8 证明：在任意6个人中，要么有3个人 互相认识，要么有3个人互相不认识。
14
a
b
证明：每个人用一个点表示，如果 ， 认识 认识， 证明：每个人用一个点表示，如果a，b认识，用红线 连接，否则黑线链接。 连接，否则黑线链接。 那么就是要证明上图中存在 红色或黑色的三角形。 红色或黑色的三角形。