鸽巢原理|

鸽巢原理

鸽巢原理一般指抽屉原理，是组合数学中一个重要的原理。抽屉原理的含义：如果每个抽屉代表一个集合，每一个苹果代表一个元素，假如有n+1个元素放到n个集合中，其中必定有一个集合里至少有两个元素。

鸽巢原理

鸽巢原理的现象：桌上有10个苹果，把这10个苹果放到9个抽屉里，无论怎样放，都会发现至少会有一个抽屉里放不少于两个苹果。

运用鸽巢原理的核心是分析清楚问题中哪个是物件，哪个是抽屉。

比如属相有12个，将属相看成12个抽屉，那么任意37个人中，至少有一个属相是不少于4个人。

鸽巢的原理是什么

把多于n个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n×1，而不是题设的n+k(k≥1)，故不可能。

把多于mn(m乘n)+1（n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。证明（反证法）：若每个抽屉至多放进m个物体，那么n个抽屉至多放进mn个物体，与题设不符，故不可能。

把无数还多件物体放入n个抽屉，则至少有一个抽屉里有无数个物体。

鸽巢问题公式

鸽巢问题的计算公式：物体个数÷鸽巢个数=商……余数、至少个数=商+1。鸽巢问题就是某个物体放在个抽屉，求物体数的最小值就是歌巢问题。解决鸽巢问题的方法有枚举法、假设法。

鸽巢问题的由来：先是由19世纪的德国数学家狄里克雷运用于解决数学问题的。

|鸽巢原理