澳洲教育论坛为大土澳群友交流经验心得与分享教育资源之用,本论坛所有文章版权归作者所有,未经作者许可不得转载!!!

抽屉原则 Pigeonhole principle

APSMO,AMC,AMO,etc

版主: 嘟嘟妈妈Albert

回复
头像
买口猪吧
帖子: 150
注册时间: 周五 8月 03, 2018 1:13 am
Reputation: 0

抽屉原则 Pigeonhole principle

帖子 买口猪吧 » 周五 8月 31, 2018 1:24 pm

先来做这道题

图片

做不出的话,请看下面的抽屉原则介绍


鸽巢原理(Pigeonhole principle),又名狄利克雷抽屉原理、鸽笼原理。


10只鸽子放进9个鸽笼,那么一定有一个鸽笼放进了至少两只鸽子。


其中一种简单的表述法为:

若有n个笼子和n+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少2只鸽子。
另一种为:

若有n个笼子和kn+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少k+1只鸽子。
集合论的表述如下:

若A是n+1元集,B是n元集,则不存在从A到B的单射。
拉姆齐定理是此原理的推广。

例子1
虽然鸽巢原理看起来很容易理解,但有时使用鸽巢原理会得到一些有趣的结论:

比如:北京至少有两个人头发数一样多。
证明:常人的头发数目在15万左右,可以假定没有人有超过100万根头发,但北京人口大于100万。如果把每个鸽巢定义为“头发的数量”,便共有100万个鸽巢。打一个比方,一根头发的人就会被编排在一根头发属于的巢、两根就在两根头发属于的巢,如此类推。鸽子则对应于人,那就变成了有大于100万只鸽子要进到100万个巢中(另一种说法是把多于100万个人编排到他们身上头发所属的鸽巢,比如有一个人有三根头发,他便会进了属于有三根头发的人的鸽巢)。因为北京人口多于100万,如果受访的前100万人头发数目刚好不同,第100万零一个的北京市民就必定会进了一个已经有一人在内的鸽巢。因此,我们便可以得到“北京至少有两个人头发数一样多”的结论。


例子2:

盒子里有10只黑袜子、12只蓝袜子,你需要拿一对同色的出来,最少需要拿出几只?假设总共只能拿一次,只要3只就无法回避会拿到至少两只相同颜色的袜子,因为颜色只有两种(鸽巢只有两个),而有三只袜子(三只鸽子),从而得到“拿3只袜子出来,就能保证有一双同色”的结论。


例子3:

某男性先后有过4位妻子,合共生有2子3女,则至少有2位子女有同一位母亲,且至少1位妻子没有女儿,至少2位妻子没有儿子。
若非如此,即任何2位子女都没有相同的母亲,则该男性至少要有5位妻子,矛盾。
若非如此,即每位妻子都有女儿,则该男性至少要有4位女儿,矛盾。
若非如此,即最多1位妻子没有儿子,则该男性至少要有3位儿子,矛盾。

转个弯的例子4:

有n个人(至少2人)互相握手(随意找人握),必有两人握过手的人数相同。
这里,鸽巢对应于握过手人数,鸽子对应于人,每个人都可以与[0,n-1]人握过手(但0和n-1不能同时存在,因为如果一个人不和任何人握手,那就不会存在一个和所有其他人都握过手的人),所以鸽巢是n-1个。但有n个人(n只鸽子),因此证明了命题正确。

鸽巢原理经常在计算机领域得到真正的应用。比如:哈希表的重复问题(冲突)是不可避免的,因为Keys的数目总是比Indices的数目多,不管是多么高明的算法都不可能解决这个问题。这个原理,还证明任何无损压缩算法,在把一些输入变小的同时,作为代价一定有其他的输入增大,否则对于长度为L的输入集合,该压缩算法总能将其映射到一个更小的长度小于L的输出集合,而这与鸽巢理论相悖。

一种表达是这样的:如果要把n个物件分配到m个容器中,必有至少一个容器容纳至少[n/m]个物件。

图片
Sent from my TARDIS

linda(7~^
帖子: 8
注册时间: 周一 8月 20, 2018 9:17 am
Reputation: 0

帖子 linda(7~^ » 周四 9月 06, 2018 12:23 am

//wg

回复