首页 . 理学 . 数学 . 组合数学 . 极值组合学

鸽笼原理

/pigeonhole principle/
条目作者侯庆虎

侯庆虎

最后更新 2022-01-20
浏览 365
最后更新 2022-01-20
浏览 365
0 意见反馈 条目引用

是数学中非常基础而又发挥着重要作用的定理。又称鸽巢原理、狄利克雷原理、狄利克雷抽屉原理或抽屉原理。

英文名称
pigeonhole principle
又称
鸽巢原理、狄利克雷原理、狄利克雷抽屉原理或抽屉原理
所属学科
数学

鸽笼原理的叙述十分简单:有10只鸽子飞进9个笼子,那么无论如何总会有一个笼子有2只或者2只以上的鸽子。更一般地,如果有至少只鸽子飞进个笼子,则无论如何总会有一个笼子有只或者只以上的鸽子。

用反证法可以很容易地给出鸽笼原理的证明。反证,假设每个笼子的鸽子数目都不超过,那么个笼子的总共的鸽子数目将会不超过,与总共至少有只鸽子矛盾。从而会有一个笼子有只或者只以上的鸽子。这样就完成了证明。

虽然鸽笼原理的叙述以及证明都非常简单,但是在数学中却发挥着极其重要的作用,尤其是在存在性的证明中。例如,利用鸽笼原理可以很容易证明如下的定理:

假设认识是相互的(即不存在甲认识乙,乙不认识甲这种情况。),那么全世界任意六个人总有三个人互相都彼此认识或者有三个人互相都彼此不认识。

证明:随便选取6个人中的1个,称其为甲,显然对于其余个人,甲要么认识要么不认识。这样就构成了认识和不认识两个笼子,其余个人看作只鸽子,那么将只鸽子放入个笼子,必然会有一个笼子装有至少只鸽子。不妨设这个笼子是认识,这3只鸽子称作乙、丙、丁。那么甲认识乙、丙、丁,接下来考虑乙、丙、丁之间是否认识。如果乙、丙、丁之间存在两个人互相认识,不妨设为乙和丙,那么就找到了甲、乙、丙,这三个人互相认识。接下来剩下的唯一一种情形就是乙、丙、丁三个人两两不认识。于是找到了三个人互相都不认识。这样就完成了证明。

鸽笼原理在计算机领域也有广泛的应用。例如,由鸽笼原理可知,散列表的重复问题是不可避免的;任何无损压缩算法在把一个文件变小的同时必有其他文件的增大来辅助。

  • BRUALDI R A.Introductory combinatorics. 5th ed.Pearson Prentice Hall:Upper Saddle River, NJ,2010.

相关条目

阅读历史

    意见反馈

    提 交

    感谢您的反馈

    我们会尽快处理您的反馈!
    您可以进入个人中心的反馈栏目查看反馈详情。
    谢谢!