鸽巢原理是非常著名的原理,生活正用的也很多。

1 简单鸽巢原理的应用

定理(鸽巢原理)

  • 若有 n 个鸽巢, n+1 个鸽子,则至少有一个巢内有至少两个鸽子。

例1

假设在一个盒子里面有10双黑色袜子、 12双蓝色袜子和8双红色袜子。那么拿出4只袜子一定可以保证有同色的两只。

  • 每种颜色作为抽屉
  • 拿出的袜子数目作为苹果

例2

在1到10中选取6个数,则其中必定有两个数的和是11。


例3

一次酒会上有 n 名来宾,其中一些来宾相互握手致意,已知没有人和自己握手、两人之间至多只握一次手。证明:一定有两名来宾的握手次数相同。

  • 将来宾作为“苹果”,握手的次数作为“抽屉”。
  • 每名来宾的握手次数最多为 n−1 , 最少为 0 。
    • 但是不可能既有来宾握手次数为 n−1 又有来宾握手次数为 0 ;
    • 假如有来宾握手次数为 n−1 , 则说明他与其他任何一名来宾都握过手,那么不可能有来宾没有与其它人握过手;
  • 反过来,假如有来宾握手次数为 0 , 则说明他与其他任何一名来宾都没有握过手,那么不可能有来宾与其它人都握过手。
  • 因此抽屉的个数最多为 n−1,苹果的个数为 n,必定有两个苹果在同一个抽屉中,也即必定有两名来宾的握手次数相同

例4

任意12个整数中一定存在两个整数,其差是11的倍数。

  • 任何一个整数模11的余数都只有11种:0, 1, 2, …, 10;于是任意的12个整数中必定存在两个整数模11的余数相同,它们的差就是11的倍数。

2 定理(一般性鸽巢原理)

  • 定理:

设 m1, m2, … , mn 都是正整数, 并有m1+m2+…+mn+n+ 1 只鸽子住进 n 个鸽巢,则至少对某个 i 有: 第 i 个巢中至少有 mi 个鸽子, i=1, 2, …, n。

推论:

m 只鸽子住进 n 个巢, 且 m-1=q*n+r,其中 q 和 r 是整数, 且 0≤r<n 。 则至少有一个巢里有 q+1 只鸽子。

2.1 应用

例5

  • 如果小张在15天内作了170道习题,那么他一定有某一天做了至少12道习题。

170-1 = 169 = 11*15+4

3 总结

  • 学好数学