Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 数学 » , ,

抽屉原理

抽屉原理我们从小学就开始接触,直到大学还在学习,其中虽然简单,但也有许多复杂的推广,不乏精妙的数学思想。
本文简单介绍抽屉原理的基本形式及其推广内容,并通过具体例子介绍其使用方法。

一 抽屉原理

简单形式 n+1个物体放进n个抽屉里,则至少有一个抽屉有不少于两个物体。

例1:367个人中,至少两个人生日相同。
事实上,23个人中至少两个人生日相同的概率已经大于50%,60个人则大于99%。

例2:任意n个正整数,总能找出其中若干个,其和为n的倍数。
证明:事实上有以下更强的结论,能找到一段连续的序列,其和为n的倍数。不妨设正整数序列为a1,a2,…,an。构造新序列si=a1+a2+…+ai,把si对n取模:

  1. 若存在sk%n==0,则a1+a2+…+ak为n的倍数
  2. 否则,任意sk模n均不为0,则si这n个数模n的值在1~(n-1)的n-1个数中,于是必存在k1、k2(k1<k2),sk1、sk2模n的余数相同。则sk2-sk1为n的倍数,即a(k1+1)+…+a(k2)为n的倍数

例3:任意六个人中,一定可以找到三个人,其互相认识,或者互不认识。
证明:问题等价于,六个点,两两连线并涂上红色或蓝色,证明存在同色三角形。
任取一点A,其引出五条线,则必存在三条线颜色相同(不妨设为红色),令其对应的顶点为B、C、D。对于这三点,

  1. 若有两点连线为红色,则这两点与A组成同色三角形。
  2. 否则,每两个点的连线均为蓝色,则B、C、D三点组成同色三角形。

加强形式 把q1+q2+…+qn-n+1个物体放进n个抽屉里,则要么第一个抽屉至少有q1个物体,要么第二个抽屉至少有q2个物体,…,要么第n个抽屉至少有qn个物体。
可以看到,简单形式的抽屉原理是q1=q2=…=qn=2的特殊情形。

例4:任意长为n^2+1的实数序列,要么含有长为n+1的递增子序列,要么含有长为n+1的递减子序列。
证明:不妨设原序列为a1, a2, …, an^2+1。
假设不存在长为n+1的递增子序列,令mk表示ak开始的最长递增子序列的长度,则mk<=n。
又显然有mk>=1,于是m1, m2, …, mn^2+1这n^2+1个数落在1到n中,根据抽屉原理,其中至少有n+1个数相等,令其为

mk1 = mk2 = … = m(kn+1) 1 <= k1 <= k2 <= .. <= kn + 1 <= n^2+1

考察这n+1个数,假设有某个i满足aki<aki+1,于是把aki加到aki+1的最长递增子序列的前面可以得到一个以aki开始的递增子序列,即mki>mki+1,与上式矛盾。
于是aki>=aki+1,即ak1 >= ak2 >= … >= akn+1,即存在长度为n+1的递减子序列。得证。
Note:子串是连续的,子序列不一定连续。

二 Ramsey定理

Ramsey定理:对任意m>=2及n>=2,存在正整数p,满足:对完全图Kp的任意红蓝2色的边着色,要么存在红色的Km,或者存在蓝色的Kn。
Note:完全图Kn指n个顶点的无向图,其中每两个顶点间都有边相连。
Ramsey定理是抽屉原理的推广,其简单的例子为例3所示。对于例3而言,m=3,n=3,存在正整数p=6,使得K6的2边着色满足要求。

事实上,例3中的6恰是最小的满足性质的p。p=5时,有以下的着色使得性质不满足。

星星图片

Ramsey数:对于给定的m>=2和n>=2,使得定理中性质成立的最小的整数p,称为Ramsey数,记为r(m,n)。
例3中,有r(3,3) = 6。

性质1 r(m,n)=r(m,n)。
证明:交换染色中红色和蓝色的位置,显然性质成立。

性质2 r(2,n)=n。
证明:一方面,r(2,n)>n-1,因为把Kn-1的边都染成蓝色,则既没有红色的K2,也没有蓝色的Kn。
另一方面,r(2,n)<=n,因为Kn的任意红蓝边着色,要么全为蓝色(存在蓝色Kn),要么至少有一条红色边(存在红色K2)。
于是,r(2,n)=n。

性质3 对任意的正整数a>=3,b>=3,有r(a,b) <= r(a-1,b) + r(a,b-1)。
证明:令N= r(a-1,b)+ r (a,b-1),对KN的任意红蓝边着色,选择一个顶点x,与x关联的边有N-1=r(a-1,b)+r(a,b-1)-1条。这些都是红色或蓝色,根据抽屉原理,其中要么

  1. 至少有r(a-1,b)条红边。这些红边的另一个顶点构成的完全图Kr(a-1,b)中,要么有红色Ka-1,要么有蓝色Kb。对于前者,红色Ka-1加上顶点x加上与x相连的红边,构成红色Ka;对于后者,存在蓝色Kb。
  2. 至少有r(a,b-1)条蓝边。这些蓝边的另一个顶点构成的完全图Kr(a,b-1)中,要么有红色Ka,要么有蓝色Kb-1。对于前者,存在红色Ka;对于后者,蓝色Kb-1加上顶点x加上与x相连的蓝边,构成蓝色Kb。

于是,r(a,b)<=N。

性质4 对任意正整数a>=2,b>=2,有r(a,b) <= C(a+b-2, a-1) = (a+b-2)! / ((a-1)!(b-1)!)。
证明:对a+b数学归纳。
归纳基 a+b <= 5时,a=2或b=2,由性质2知成立。
归纳步 假设对任意满足5 < a+b < m+n的a、b,性质满足。则根据性质3有
r(m,n) <= r(m,n-1) + r(m-1,n) <= C(m+n-3,m-1) + C(m+n-3,m-2) = C(m+n-2,m-1)。
于是,性质成立。
Note:里用C(m,n)表示组合数\(C^n_m\),组合数一个性质为C(m,n) + C(m,n-1) = C(m+1,n)

多颜色推广 对任意整数q1, q2, …, qk>=t,存在整数p,使得任意Kp的t染色中,要么存在颜色1的Kq1,要么存在颜色2的Kq2,…,要么存在颜色t的Kqt。并称其中最小的p为Ramsey数 r(q1,q2,…,qk)。
性质1 对任意的a1, a2, …, ak,a1-ak的顺序不影响r(a1,a2,…,ak)的值
性质2 对任意的a1, a2, …, ak,有r(a1,a2,…,ak) <= r(a1,r(a2,…,ak))
性质3 对任意的a1>=2,…,ak>=2,有r(a1,…,ak) <= r(a1-1,a2,…,ak) + r(a1,a2-1,…,ak) + … + r(a1,a2,…,ak-1)
性质4 对任意的a1,a2,…,ak,有r(a1+1,…,ak+1) <= (a1+…+ak)! / (a1!a2!…ak!)

更一般的推广,这里不再讨论。

上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论