抽屉原理

[拼音]：chouti yuanli

[外文]：box principle

又叫鸽舍原理，其表述为：假如有n+1个（或更多）物体装入n个盒子，那么一定有某个盒子至少装有两个物体，为纪念19世纪德国数学家P.G.L.狄利克雷，也叫做狄利克雷原理。抽屉原理虽然简单，但变化多，应用广，在数论和组合数学中尤其有着广泛的应用。抽屉原理应用时，关键在于建立具体的抽屉（鸽舍）。例如，狄利克雷用它来证明：对于任何实数 α及Q>1，均存在整数h，q，使，0<q<Q。1935年，P.爱尔特希提出如下问题：对于不超过 2n的任意n+1个正整数中，至少有一个被另外一个整除。运用抽屉原理，可以给出一个非常简短的证明：设1≤α₁<α₂<…<α_n+1≤2n，写λ_i≥0，2凲b_i(i=1，2，…，n+1)， b_i小于2n，因为在1，2，…，2n中恰有n个不同奇数，故在b₁，b₂，…，b_n+1中至少有两个相同，设b_i=b_j，1≤i<j≤n+1，故α_i|α_j。又如，数论中著名的佩尔方程x²-Dy²=1(其中D>0且不是平方数)可用抽屉原理解决。运用抽屉原理，很容易说明：随意指定六个人，其中一定有三个人相互都认识或都不认识。P.爱尔特希在1935年运用抽屉原理证明了组合数学中一个著名结果：对于给定的正整数n，存在一个正整数N(n)，使得在一个平面上，没有三点在一条直线上的任意N(n)个点中含有n个点，构成一个凸n边形。

抽屉原理百科介绍

内容版权声明：除非注明，否则皆为本站转载文章。文章及图片版权归原作者所有，如有侵权请联系我们，我们立刻删除。