pkaAAA鸽巢原理的应用

鸽巢原理的应用鸽巢原理不等式的应用 摘要:鸽巢原理是个重要的组合原理，本文叙述了鸽巢原理的定理和对模同余分类构造法。然后本文重点介绍鸽巢原理在不等式方面的运用。 关键字:鸽巢原理;对模同余分类法;不等

鸽巢原理的应用 鸽巢原理不等式的应用 摘要:鸽巢原理是个重要的组合原理，本文叙述了鸽巢 原理的定理和对模同余分类构造法。然后本文重点介绍鸽巢原理在不等式方面的运 用。 关键字:鸽巢原理;对模同余分类法;不等式证明 0引言 鸽巣原理又名抽屉原理或狄利克雷原理, 它最早由德国数学家狄利克雷运用于 解决数学问题而提出的，它是组合数学中解决计数问题的一个重要的工具，并且在 数论和密码学中也有着广泛的应用，运用鸽巢原理往往能起到事倍功半的效果。 1鸽巣原理 1.1 初级定理 定理1 把个物体放入个盒子里, 则至少有一个盒子里含有两个或两n，1n 个以上的物体. 例1(13个人中必有两个人的属相相同。 例2.在边为1的正方形内任取5点，则其中至少有两点，它们之间的距离 2不超过 2 1.2 高级定理 定理2 令为正整数如果将个物体放入个qqq,,,qqqn，，，,，1n12n12n 盒子, 那么, 或者第一个盒子至少含有个物体, 或者第二个盒子至少含有qq12 个物体,…,或者第个盒子至少含有个物体. qnn nm,，11 推论1 只鸽子放入个鸽笼, 则至少有一个鸽笼中有只鸽nm，， 子.