v1
v6
v5 v4
证明
现考察边v3v4， 如果边v3v4是红色 边,则三角形v1v3v4 v 的三条边颜色相同 （红色） 问题得解
v1
v2
Hale Waihona Puke v6v3 v4v5
证明
如果v3v4是白色边 再考察边v4v6 如果v4v6是红色边， 则三角v1v4v6形的三 条边颜色相同， 问题得解
v1
v2
鸽巢原理例 2
某人步行10小时，共走45公里， 已知他第一小时走了6公里， 最后一个小时只走了2公里， 证明必须存在连续的两小时，在这2小时 内他至少走了10公里。
鸽巢原理例 2
证明：设第i小时走了ai公里， 连续两小时所走的里程为：a1+a2，a2+a3，…， a9+a10，共9种； 因为(a1+a2)+(a2+a3)+…+(a9+a10)=2*45-62=82， 所以必有连续两个小时所走里程大于10。 （9*9=81）
v6
v3 v4
v5
证明
如果v4v6是白色边 再考察边v3v6 如果边v3v6是红色边，则 三角形v1v3v6的三条边颜 色是相同的，问题得解 如果边v3v6是白色边，则 三角形v3v4v6都是白色边， 问题得解
v1
v2
v6
v3 v4
v5
练习：
习题1： 个球放入77个盒子内 习题 ： 132个球放入 个盒子内，盒子排成一行， 个球放入 个盒子内，盒子排成一行， 每盒至少放一个。证明无论如何怎样放， 每盒至少放一个。证明无论如何怎样放，一定存 在相邻的某几个盒子内放有21个球 个球。 在相邻的某几个盒子内放有 个球。 习题2：证明在任意 个人中 要么有3个人互相认 个人中， 习题 ：证明在任意6个人中，要么有 个人互相认 要么有3个人互相不认识 个人互相不认识。 识，要么有 个人互相不认识。
鸽巢原理
如果某人造了n个鸽巢（洞） 养了多于n只的鸽子 则必有一个鸽巢（洞）住2只或2只以上 的鸽子
鸽巢原理2
当鸽巢为n个 鸽子数大于n×m只时 必有一个鸽巢住m+1只或大于m+1只鸽 子
鸽巢原理3
A、B是有限集合 f是A到B的函数 如果|A|>|B|，则A中至少有2个元素，其 函数值相等
鸽巢原理4
A、B是有限集合 f是A到B的函数 如果|A|>n×m，|B|=n，则在A中至少有 m+1个元素，其函数值相等
鸽巢原理例 1
任意n+1个正整数，其中必有两个数之 差能被n整除。 解：由于任意正整数被n整除后，其余数 n 只能是0,1, …n-1共n种， 所以在n+1个正整数中，必有两个数被n 整除后余数相同， 这两个数之差必能被n整除。
鸽巢原理例 3
在平面上有6个点 任意两点都用一条边相连， 所得的图称为完全图 现在在每条边上涂色，可以 随意涂红色或白色 证明在这个完全图中，必存 在一个三角形，其三条边的 颜色相同
证明
设在平面上的6个点为 v1,v2,v3,v4,v5,v6 先画出与v1相连的5条边 把这5条边分别涂上红或白两 v2 种颜色 由鸽巢原理知，必有3条边颜 色相同 v3 设v1v3、v1v4 、v1v6颜色相同： 红色