什么是鸽巢原理(什么是鸽巢原理俗话怎么说)

鸽巢原理

鸽巢原理（也叫抽屉原理）指出，如果n只鸽子(或任何其他物品)被放入m个洞和n>m个洞中，那么至少有一个洞中必须有不止一只鸽子。 分别，如果有比鸽子更多的洞(n<m)，一些洞是空的。

如果A是一组鸽子，B是一组鸽子洞，那么鸽子到鸽子洞的映射可以用函数f:A→B来描述。 很明显，A和B可以是任意的有限集。

以下说法是正确的:

1. 如果|A|>|B|，则函数f:A→B不是单射的。

2. 如果|A|<|B|，则函数f:A→B不是满射。

鸽巢原理的一个更一般的版本表述如下:

对于任意n,m∈n，如果n个对象分布在m个集合中，则至少有一个集合中必须至少包含⌈n/m⌉对象，其中⌈⋅⌉为上限函数(一种阶梯函数，即⌈x⌉被定义为大于或等于x的最小整数)

例子

生日问题

假设一个班有40个学生。 一年中是否有一个月至少有4个学生出生?

40名学生为期12个月。 把学生当作“项目”，把月份当作“盒子”。 我们有n=40， m=12。 根据广义鸽巢原理，至少有一个盒子(月)，里面至少有⌈n/m⌉物品(学生)。 代入n和m，得到

⌈n/m⌉=⌈40/12⌉=⌈3.33⌉=4

因此，有一个月至少有4个学生过生日。

苹果装箱

有25箱苹果，有三种不同的品种。 每个盒子里只有一种苹果。 证明至少有9箱相同品种的苹果。

把盒子叫做“鸽子”，把各种苹果叫做“巢”。 利用n=25 m=3时的广义鸽巢原理，得到:

⌈n/m⌉=⌈25/3⌉=⌈8.33⌉=9

因此，至少有9箱相同品种的苹果 。

足球联赛

假设有n支球队参加足球比赛，每支球队互相比赛。 证明，在比赛的任何中间时刻，总有两支球队进行了相同数量的比赛。

我们将把球队视为“鸽子”，比赛的数量视为“鸽巢”。 很明显，一支球队的比赛次数可以从0到n - 1不等。 注意，如果有一支球队打了n - 1场比赛，那么没有其他球队会空闲。 我们有n只鸽子和n - 1个洞，其中n≥1。

根据鸽巢原理，总是会有两支比赛次数相同的球队。

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请与我联系，一经查实立刻删除内容。本文内容由快快网络小蔼创作整理编辑！