鸽巢原理是非常著名的原理，生活正用的也很多。
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 总结
- 学好数学
京公网安备 11010502036488号