目录

浅谈鸽巢原理及其应用

目录

鸽巢原理:如果 $k+1$ 个或更多的物体放入 $k$ 个盒子,那么至少有一个盒子包含了 $2$ 个或更多的物体。

有时候鸽巢原理也被称为抽屉原理,更准确地说应该叫做“狄利克雷抽屉原理”。至于狄利克雷这个名字,还有有趣的函数也是用他的名字命名的。它就是大名鼎鼎的狄利克雷函数 $$f\left(x\right)=\begin{cases}1,&x\in\mathbf{Q}\\ 0,&x\not\in\mathbf{Q}\end{cases}$$ 这个函数的有趣之处就在于它没有对应的图像。扯远了。

下面给出鸽巢原理的证明:假定 $k$ 个盒子中没有一个盒子包含的物体多余 $1$ 个,那么物体总数至多是 $k$,这与至少有 $k+1$ 物体矛盾。证毕。

例1:在一组 $367$ 个人中一定至少有 $2$ 个人有相同的生日,这是由于只有 $366$ 个可能的生日。

例2:在 $27$ 个英文单词中一定至少有 $2$ 个单词以同一个字母开始,因为英文字母表中只有 $26$ 个字母。

例3:证明对每个整数 $n$,存在一个数是 $n$ 的倍数,且在它的是进制表示中只出现 $0$ 和 $1$。

证明:令 $n$ 为正整数。考虑 $n$ 个整数 $1,11,111,\cdots,11\cdots 1$(在这个数表中,最后一个整数的十进制表示中具有 $n+1$ 个 $1$)。注意到当一个整数被 $n$ 整除时存在 $n$ 个可能的余数。因为这个数表中有 $n+1$ 个整数,由鸽巢原理必有两个整数在除以 $n$ 时有相同的余数。这两个整数之差的十进制表示中只含有 $0$ 和 $1$,且它能被 $n$ 整除。

广义鸽巢原理:如果 $N$ 个物体放入 $k$ 个盒子,那么至少有一个盒子包含了至少 $\left \lceil \frac{N}{k} \right \rceil$ 个物体。

证明:假定没有盒子包含了比 $\left\lceil \frac{N}{k} \right\rceil-1$ 多的物体,那么物体总数至多是 $$k\left (\left\lceil \frac{N}{k} \right \rceil -1\right) < k\left(\left(\frac{N}{k}+1\right)-1\right)=N$$ 这与存在有总数 $N$ 个物体矛盾。证毕。

例4:在 $100$ 个中至少有 $\left\lceil \frac{100}{12}\right\rceil=9$ 个人生在同一个月。

例5:为保证一个州的 $2500$ 万个电话有不同的 $10$ 位电话号码,所需地区代码的最小数是多少?(假定电话号码是 $\textrm{NXX-NXX-XXXX}$ 形式,其中前 $3$ 位是地区代码,$N$ 表示从 $2$ 到 $9$ 包含的十进制数字,$X$ 表示任何十进制数字)。

:有 $800$ 万个形如 $\textrm{NXX-NXX-XXXX}$ 的不同的电话号码。因此,由广义鸽巢原理,在 $2500$ 万个电话号码中,一定至少有 $\left\lceil\frac{25000000}{8000000}\right\rceil$ 个同样的电话号码。因而至少需要 $4$ 个地区代码来保证所有的 $10$ 位号码是不同的。

例6:证明在不超过 $2n$ 的任意 $n+1$ 个正整数中一定存在一个正整数被另一个正整数整除。

证明:把 $n+1$ 个整数 $a_{1},a_{2},\cdots,a_{n}$ 中的每一个都写成 $2$ 的幂与一个奇数的乘积,换句话说,令 $a_{j}=2^{k_{j}}\cdot q_{j},j=1,2,\cdots,n+1$,其中 $k_{j}$ 是非负整数,$q_{j}$ 是奇数。整数 $q_{1},q_{2},\cdots,q_{m+1}$ 都是小于 $2n$ 的正奇数。因为只存在 $n$ 个小于 $2n$ 的正奇数,由鸽巢原理,$q_{1},q_{2},\cdots,q_{n+1}$ 中必有两个相等。于是,存在整数 $i,j$ 使得 $q_{i}=q_{j}$。令 $q_{i}=q_{j}=q$,那么 $a_{i}=2^{k_{i}}\cdot q,a_{j}=2^{k_{j}}\cdot q$。因而,若 $k_{i} < k_{j}$,则 $a_{i}$ 整除 $a_{j}$;反之,则 $a_{j}$ 整除 $a_{i}$。