鸽子洞原理或者称为抽屉原理

原理概述:

     有n只鸽子和m个鸽洞,所有鸽子都住在鸽洞里,如果n>m,那么至少有二只鸽子必须住在同一鸽洞里。

函数观点:

   把鸽子看成是定义域A中元素ai,鸽洞看成是值域B中的元素bj,鸽子住鸽洞作为函数关系。

鸽洞原理:

     设f是从有限集A到有限集B的函数,若|A|>|B|,则必有a1,a2∈A,a1≠a2,使f(a1)=f(a2)=b∈Bf 包含于B(Bf是象域)。

  反证:若对任意a1,a2∈A,a1≠a2,f(a1)≠f(a2),|A|=|Bf|≤|B|与|A|>|B|矛盾

注:

  鸽洞原理本质上是对一个非一对一函数的充分性判别。

  这个原理看上去容易理解,且有广泛的应用。

例1:在n2+1个不同整数的任意排列中,证明一定存在长为n+1的上升子序列或下降子序列。

证明

   设此序列为:a1,a2,…,ak,…,从ak开始上升子序列长度为xk,下降子序列长度为yk,每一个ak(k=1,2,…,n2+1)都对应了(xk,yk)。

    若不存在长为n+1的上升或下降子序列,那么xk ≤n,yk≤n,形如(xk,yk)的不同点对至多有n2个,而ak有n2+1个,必有ai,aj(1≤i<j≤n+1)同时对应(xi,yi)=(xj,yj)。

   由于ai≠aj,若ai<aj,则xi至少比xj大1,若ai>aj,则yi至少比yj大1,与(xi,yj)=(xj,yj)矛盾。

例2: 132个球放入77个盒子内,每盒至少放一球,求证:一定有21个球放在相邻的某几只盒子里。

证明

    设第k个盒子里放的球为bk,得到b1,b2,…,b77,按题意,欲寻找i和j,i>j≥0,使bj+1+bj+2+…+bi=21,即完成证明。�

    设ak=,得到a1,a2,…,a77,显然,{ak}是严格单调上升的,ai≠aj (i≠

 设  Ck=,得到C1,C2,…,C77,{Ck}也是严格单调上升的,Ci≠Cj (i≠j),且C77=153,Ci=ai+21。�

    {ak}与{Ck}合在一起共有154个,但只能在1~153中取值,由鸽洞原理,必有二个相同,且不会同是ak中的,也不会同是Ck中的,不妨ai=Cj=aj+21,ai-aj=21,即,得到bj+1 +bj+2+…+bi=21。

例3

      设x1,x2,…,xn是任意排列的任意整数,证明其中存在连续的若干个数,它们之和是n的倍数。

证明:  设ai

   若ai中有n的倍数,则命题成立

   若ai中没有n的倍数,由n除ai的余数只能在1~n-1中取

   以ai(i=1,2,…,n)作鸽子,1~n-1作鸽洞,ai,aj,使ai≡aj(modn)(i>j),则  n|(ai-aj),  即xj+1+xj+2+…+xi是n的倍数。

摘录自百度文库:鸽子洞原理

原文地址:https://www.cnblogs.com/xiangyangzhu/p/5372875.html