【离散数学中的数据结构与算法】九鸽巢原理

超、凢脫俗 2022-03-01 15:14 272阅读 0赞

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

### 文章目录 ###

*   *  1 简单鸽巢原理的应用
     *  2 定理（一般性鸽巢原理）
     *   *  2.1 应用
     *  3 总结

## 1 简单鸽巢原理的应用 ##

定理（鸽巢原理）

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

例1

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

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

例2

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center]  
例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 总结 ##

*  学好数学

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center]: /images/20220301/029dcf976ffa423e9415e20e32668ab4.png