浅谈鸽巢原理及其应用

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

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

下面给出鸽巢原理的证明:假定\(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}\)。

发表评论