第二章 鸽巢原理
我们在本章考虑一个重要而又初等的组合学原理,它能够用来解决各种有趣的问题,常常得出一些令人惊奇的结论。这个原理有许多的名字,但最普通的名字叫鸽巢原理,也叫做鞋盒原理。有关于鸽巢的原理阐释,粗略地说就是如果有许多鸽子飞进不足够多的鸽子巢内,那么至少要有一个鸽巢被两个或多个鸽子占据。更精确的叙述在下面给出。
2.1 鸽巢原理的简单形式
鸽巢原理的简单的形式可以描述如下:
定理2.1.1 如果n+1个物体被放进n 个盒子,那么至少有一个盒子包合两个或更多的物体。
证明:如果这n 个盒子中的每一个都至多含有一个物体,那么物体的总数最多是n 。 既然我们有n +1个物体,于是某个盒子就必然包含至少两个物体。 注意,无论是鸽巢原理,还是它的证明,对于找出含有两个或更多物体的盒子都没有任何帮助。它们只是简单地断言,如果人们检查每一个盒子,那么他们会发现有的盒子里面放有多于一个的物体:鸽巢原理只是保证这样的盒子存在。因此,无论何时鸽巢原理被用来证明一个排列或某种现象的存在性,除了考察所有可能性之外,它都不能对任何构造排列或寻找现象的例证给出任何指示。 我们可以把将物体放入盒子改为用n 种颜色中的一种颜色对每一个物体涂色:此时,鸽巢原理断言,如果n +1个物体用n 种颜色涂色,那么必然有两个物体被涂成相同的颜色。
下面是两个简单的应用。
应用1 在13个人中存在两个人,他们的生日在同一个月份里。
应用2 设有n 对已婚夫妇。为保证能够有一对夫妇被选出,至少要从这2n 个人中选出多少人?
为了在这种情形下应用鸽巢原理,考虑n 个盒子,其中一个盒子对应一对夫妇。如果我们选择n +1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去,那么就有同一个盒子含有两个人;也就是说,我们已经选择了一对已婚夫妇。选择n 个人使他们当中一对夫妻也不没有的两种方法是选择所有的丈夫或选择所有的妻子。因此,n +1是保证能有一对夫妇被选中的最小的人数。 还存在一些与鸽巢原理相关的其他原理,有必要正式叙述如下:
如果将n 个物体放入n 个盒子并且没有一个盒于是空的,那么每个盒子恰好包合一个物体。
如果将n 个物体放入n 个盒子并且没有盒子被放入多于一个的物体,那么每个盒子里有一个物体。
在应用2里,如果我们这样选择n 个人,从每一对夫妻中至少选一人,那么我们就从每对夫妻中恰好选出了一个人。同样,如果我们选择n 个人的方法是从每一对夫妻中至多选一人,那么我们就从每对夫妻中至少(从而也恰好)选出了一个人。
应用3 给定m 个整数m a a a ,,,21 ,存在整数k 和l ,m l k ≤<≤0o ,使得l k k a a a +++++ 21’能够被m 整除。通俗地说,就是在序列m a a a ,,,21 中存在连续i a ,这些i a 的和能被m 整除。
为了深入这个问题,考虑m 个和
m a a a a a a a a a ++++++ 21321211,,,,,
如果这些和当中的任意一个可被m 整除,那么结论就成立。因此,我们可以设这些和中的每一个除以m 都有一个非零余数,余数等于1,2,……,m-1。由于存在m 个和而只有m-1个余数,则必然有两个和数除以m 有相同的余数。因此,存在整数k 和l ,k 应用4 一位国际象棋大师有11周的时间备战一场锦标赛,他决定每天至少下一盘棋,但为了不使自己过于疲劳他还决定在每周不能下棋超过12盘。证明存在连续若干天期间这位大师恰好下了2l 盘棋。 令1a 是在第一天所下的盘数,2a 是在第一天和第二天所下的总盘数, 而3a 是在第一天、第二天和第三天所下的总盘数,等等。由于每天至少要下一盘棋,故数值序列7721,,,a a a 是一个严格递增的序列。此外,11≥a ,而且出于每周下棋最多是12盘,故≤77a 12×ll =132。因此,我们有 13217721≤<<<≤a a a 。序列21,,21,217721+++a a a 也是一个严格递增序列, 153212*********≤+<<+<+≤a a a , 于是,7721,,,{a a a ,}153,2,1{}21,,21,217721 ?+++a a a ,因此154个数中至少有两个是相等的。而7721,,,a a a 是互不相等的,21,,21,217721+++a a a 也是互不相等的,因此,因此必然存在一个i 和一个j ,使得21+=i j a a 。从而,这位国际象棋大师在第j i ,,1 +天总共下了21盘棋。 应用 5 (中国余式定理)令m 和n 为二互素的正整数,并令a 和b 为两整数,且10-≤≤m a 以及10-≤≤n b 。于是,存在一个正整数x ,使得x 除以m 的余数为a ,并且x 除以n 的余数为b ;即x 可以写成a pm x +=的同时又可写成x b qn +=的形式,这里,p 和q 是两个整数。 为证明这个结论,我们考虑n 个整数a m n a m a m a +-++)1(,,2,, ,这些整数中的每一个除以m 都余a 。设其中的两个除以n 有相同的余数r 。令这两个数为a im +和a jm +,其中10-≤<≤n j i 。因此,存在两整数i q 和j q ,使得 r n q a im i +=+,r n q a jm j +=+。 从第二个方程减去第一个方程,得到n q q m i j i j )()(-=-。上面的方程告诉我们n 是m i j )(-的一个因子、由于m 和n 没有除1之外的公因子,因此n 是i j -的一个因子。然而,10-≤<≤n j i 意味着10-≤-≤n i j ,也就是说n 不可能是是i j -的的因子。该矛盾产生干我们的假设:a m n a m a m a +-++)1(,,2,, ,这些整数中的两个除以n 有相同的余数r 。因此我们断言, a m n a m a m a +-++)1(,,2,, 这n 个数中的每一个数除以n 都有不同的余数;根据鸽巢原理:n 个数1,,2,1,0-n 中的每一个作为余数都要出现;特别是数b 也是如此。令p 为整数,满足10-≤≤n p ,且使数a pm x +=除以n 余数为b ,则对于某个适当的q ,x b qn +=。因此,a pm x +=且x b qn +=,从而x 具有所要求的性质。 一个有理数b a /最终可以写成十进制循环小数的结论实际上就是鸽巢原理的推论,我们将其证明留作练习。 2.2 鸽巢原理的加强形式 定理2.2.1 如果把121+-+++n q q q n 个物体放进n 个盆子里,那么或者第一个盒子里装有至少1q 个物体,或者第二个盒子里装有至少2q 个物体,…,或者第n 个盒子里装有至少n q 个物体。 证明 若对所有的i (n i ≤≤1),第i 个盒子至多只有1-i q 个物品,则n 个盒子中至多有=-++-+-)1()1()1(21n q q q n q q q n -+++ 21个物品。矛盾,故 理成立. 在定理2.2.1中令2221====q q q ,则变成了鸽巢原理的简单形式。在定理2.2.1中令r q q q n ==== 21时,则得到如下的推论: 推论2.2.1 若将n(r-1)十1个物品放入n 个盒子中,则至少有一个盒子中有r 个物品。 推论2.2.2 如果n 个非负整数n m m m ,,,21 的算术平均值 121->++r n m m m n , 那么n m m m ,,,21 中至少有一个大于或等于r 。 也可以叙述成如推论1.2.2所描述的另一形式: 推论2.2.3 若将m 个物品放入n 个盒子中,则至少有一个盒子中有不少于 ??????n m 个物品.其中,?? ????n m 是不小于n m 的最小整数。 应用5 将1到16的16个正整数任意分成三部分,其中必有一部分中的一个元素是某两个元素之差(三个元素不一定互不相同)。 证明 用反证法。设将1到16个整数任意分成,1P ,2P 3P 三个部分,若这三部分中无一具有问题所指的性质,即其中一个元素是其中某两个元素之差,由此我们来导出矛盾,从而证明问题的结论是正确的. (1)将1到16的整数任意分成三部分,由鸽巢原理知,其中必有一部分至少有:6316=?? ????个元素。不妨设1P 中含有6个元素,为654321a a a a a a <<<<<。令},,,,,{6543211a a a a a a P A ==, 若A 中存在一个元素是某两个元素之差,则1P 满足问题的要求。否则,令121a a b -=,132a a b -=,143a a b -=,154a a b -=,165a a b -=,并令},,,,{54321b b b b b B =。显然,161≤≤i b )51(≤≤i ),即B 中的元素仍是l 到l6的整数。根据假设,54321,,,,b b b b b 无一属于1P 。否则,与1P 中不存在一元素等于某两元素之差相矛盾。所以,B 中元素属于2P 或3P 。 (2)与(1)类似,不妨设B 中至少有325=?? ????个元素属于2P ,设为321c c c <<,并令},,{321c c c C =。由假设,C 中不存在一元素是某两个元素之差。令121c c d -=,132c c d -=,并令},{21d d D =。显然,D 中元素不属于2P ,否则,与2P 中不存在一元素是某两个元素之差相矛盾。且16121≤≤≤d d 。下面再证明D 中元素不属于1P 。 设i j i b c =()51;3,2,1≤≤=i j i ,则 121c c d -=)()(11111212a a a a b b j j j j ---=-=++)(1112++-=j j a a 。 同理:132c c d -=)()(11111313a a a a b b j j j j ---=-=++)(1113++-=j j a a 所以,21,d d 均不属于1P 。因此,因此,D 中元素不属于3P 。 (3) 根据假设,在3P 中不存在一元素是另两个元素之差,所以121d d d -≠,令12d d e -=,与(1)类似,e 不属于3P ;同(2)可以证明e 也不属于1P 和2P 。即存在一整数161≤≤e ,它不属于1P ,2P 和3P 中的任何一个,这与将1到16间的整数任意分成三个部分的假设相矛盾。 2.3 Ramsey 问题与Ramsey 数 2.3.1 Ramsey 问题 1958年6-7月号美国《数学月刊》上登载着这样一个有趣的问题:“任何6个人的聚会,其中总会有3人互相认识或3人互相不认识.”这就是著名的Ramsey 问题。 以6个顶点分别代表6个人,如果两人相识,则在相应的两顶点间连一红边,否则在相应的两顶点间连一蓝边,则上述的Ramsey 问题等价于下面的命题: 命题2.3.1 对6个顶点的完全因6K 任意进行红、蓝两边着色,都存在一个红色三角形或一个蓝色三角形。 证明 设654321,,,,,v v v v v v 是6K 的6个顶点,1v 与 65432,,,,v v v v v 所连的5条边着红色或蓝色。由鸽巢原理知,其中至少有325=?? ????条边同色。不妨设1v 与432,,v v v 所连的3条边均为红色,如图所示。若432,,v v v 间有一条红边,不妨设为32v v ,则△321v v v 是一红色三角形。否则,432,,v v v 认间均为蓝边,即△432v v v 是一蓝色三角形。 类似于命题2.3.1,还有如下的命题2.3.2-2.3.4: 命题2.3.2 对6个顶点的完全图6K 任意进行红、蓝两边着色,都至少有两个同色三角形。 证明 设654321,,,,,v v v v v v 是6K 的6个顶点,由命题1.3.1知,对6K 任意进行红、蓝两边着色都有一个同色三角形,不妨设△321v v v 红色三角形。以下分各种情况来讨论: (1)若615141,,v v v v v v 均为蓝边,如图所示,则若654,,v v v 之 间有一蓝边,不妨设为54v v ,则△541v v v 为蓝色三角形;否则, △654v v v 为红色三角形。 (2)若615141,,v v v v v v 中有一红边,不妨设41v v 为红边,此时若 4342,v v v v 中有一条红边,不妨设43v v 是红边。则△431v v v 是一 红色三角形,见图。 以下就4342,v v v v 均为蓝边的情况对与4v 相关联的边的颜色 进行讨论: (i)若6454,v v v v 中有一蓝边,不妨设54v v 为蓝边,如图所示。 此时,若5352,v v v v 均为红边,则△532v v v 是红色三角形,否则△542v v v 或△543v v v 是蓝色三角形。 (ⅱ)若6454,v v v v 均为红边,见图。此时,若651,,v v v 间 边,不妨设51v v 为红边,则△541v v v 为红色三角形,否则△651v v v 为蓝 色三角形。 由以上对各种情况的讨论知,对6K 的任意红、蓝两边着 色均有两个同色三角形。 命题2.3.3 对10个顶点的完全图10K ,任意进行红、蓝两边着色,都或者有一红色4K ,或者有一蓝色3K 。 证明 设a 是10K 的一个顶点,与a 相关联的9条边用红、蓝两色着色,由鸽巢 原理知,这9条边中要么有6条红边,要么 有4条蓝边。类似于前面两个命题的分析证 明过程可以得出结论,具体分析过程见图。 命题2.3.4 对9个顶点的完全图9K 任 意进行红、蓝两边着色,都或者有—个红色 4K ,或者有一蓝色3K 。 证明 在9K 中,如果与每个顶点关联 的红边均为5条,因为一条红边连着两个顶点,所以9K 中应有2 45295=?条边,它不是整数,所以不成立。故必有—个顶点关联的红边数不为5,设此顶点为a ,则与a 关联的红边数至少为6或至多为4。以下可以用与命题2.3.3中完全相同的分析过程来证明9K 中必有—个红色4K ,或者有一蓝色3K 。 2.3.2 Ramsey 数 从2.3.1节的讨论中可以归纳出如下的一般性定义:对于任意给定的两个正整数a 和b ,如果存在最小的正整数),(b a r ,使得当),(b a r N ≥时,对N K 任意进行红、蓝两边着色,N K 中均有红色a K 或蓝色b K ,则),(b a r 称为Ramsey 数。 由命题2.3.1知6)3,3(≤r ;在 5K 按左图的方式进行红、 蓝两边着色(实线为红边,虚线为蓝边),则既无红色3K 也无 蓝色3K ,所以5)3,3(>r 。从而得知6)3,3(=r 。 由命题2.3.4知9)3,4(≤r ;在8K 中按左图的方式进行红、 蓝两边着色,则既无红色则既无红色4K 也无蓝色3K ,所以 8)3,4(>r 。从而得知9)3,4(=r 。 Ramsey 于1930年证明了对于任给的整数a 和b ,Ramsey 数),(b a r 的存在性。但是,Ramsey 数的确定却是一个非常难的问题,以致于至今)5,5(r 尚不为世人所知。表1.3.1中列出了目前所知的一些Ramsey 数。 定理2.3.1 设Ramsey 数),(b a r ,其中,b a ,为正整数,则有 1、),(b a r ),(a b r = 2、)1,(a r 1),1(==a r 3、)2,(a r a a r ==),2( 证明留给读者 定理2.3.2 对于任意不小于2的整数b a ,有 ),1()1,(),(b a r b a r b a r -+-≤ 当)1,(-b a r ,),1(b a r -都为偶数时,上式中的不等式严格成立。 证 令),1()1,(b a r b a r n -+-=, 要证上式成立,只要用红、白两色对n 顶点完全图n K 上的边着色,每边恰涂一色,然后证明n K 上或者存在红色a K ,或者有白色的b K 即可。 从n K 上任取一个顶点v ,则v 恰好是n-1条边的公共端点。即是1),1()1,(--+-b a r b a r 条边的端点。依据鸽巢舍原理可知,这些边中、或者有不少于)1,(-b a r 条白色边,或者有不少于),1(b a r -条红色的边。 若是前一种情形,只要考察顶点v 以及与v 以白边相连的)1,(-b a r 个顶点在n K 上导出的完全子图。结合Ramsey 数)1,(-b a r 的定义,不难看出该完全子图上或者存在红色的a K ,或者存在白色的b K 。 不论哪种情形,都证明了n K 上或者有红色a K ,或者存在白色的b K 。故上式成立。 现在证明,当)1,(-b a r ,),1(b a r -都为偶数时,上式中的不等式严格成立。即有),1()1,(),(b a r b a r b a r -+-<,令 ),1()1,(b a r b a r m -+-=。 设v 是完全图m K 上的任意一点,则v 恰好是1-m 条边的公共端点。由于1-m 是偶数,所以这些边可能由偶数条红边加上偶数条白边构成;也可能由奇数数条红边加上奇数条白边构成。现在证明,m K 上至少有一点j v ,它恰是偶数条红边的端点。反证。用j c 表示与顶点j v 关联的全部红边数,m j ,,2,1 =。 若m c c c ,,,21 都是奇数,则m c c c c +++= 21也是奇数,而m K 上的全部红边数为2/c 不可能是整数,矛盾。 下面的证明可以完全仿上式的推导过程。只要注意到,假定i v 是一个恰与偶数条红边关联的顶点,那么,以i v 为—端的2),1()1,(--+-b a r b a r 条边中,或者有不少),1(b a r -条红边,或者有不多于2),1(--b a r 条红边,即有不少于)1,(-b a r 条白边。 定理2.3.3 对任意的正整数2,2≥≥b a ,有 )!1()!1()!2(12),(---+=??? ? ??--+≤b a b a a b a b a r 证明 对b a +作归纳。 当5≤+b a 时,2=a 或2=b ,由等式a a r =)2,((知定理成立。 假设对一切满足n m b a +<+≤5的b a ,,定理成立,由定理2.3.2及归纳假设,有 ??? ? ??--==???? ??--++???? ??--+≤-+-≤122313)1,(),1(),(m n m n n m n n m n m r n m r n m r 所以,对于任意的正整数2,2≥≥b a ,定理的结论成立。 2.4 Ramsey 数的推广 将2.3节中的红、蓝两色推广到任意k 种颜色,对n 个顶点的完全图n K 用n c c c ,,,21 共k 种颜色任意进行k 边着色,它或者出现1c 颜色的1a K 或者出现2c q 颜色的2a K ,或者出现k c 颜色的k a K 。满足上述性质的n 的最小值记为 ),,,(21k a a a r 。 定理2.4.1 对任意的正整数k a a a ,,,21 ,有 )),,(,(),,,(2121k k a a a r a a a r ≤ 证明 留作习题。 类似于定理2.3.1和定理2.3.2,有如下的结论: 定理2.4.2 对任意的正整数2,,2,221≥≥≥k a a a ,有 2)1,,,(),,1,(),,,1(),,,(21212121+--++-+-≤n a a a r a a a r a a a r a a a r k k k k 证明 类似于定理2.3.1的证明。 定理2.4.3 对任意的正整数k a a a ,,,21 ,有 ! !!)!()1,,1,1(212121k k k a a a a a a a a a r +++≤+++ 证明 类似于定理2.3.2的证明。 利用广义Ramsey 数,我们来讨论一类集合划分问题。 考虑集合{}13,,2,1 的一个划分{}{}{}{}9,8,7,6,5,12,11,3,2,13,10,4,1,可以看出,在上面的划分的每一块中,都不存在三个数z y x ,,(不一定不同)满足方程 z y x =+ 然而,无论如何将集合}14,,2,1{ 分成三个子集合,总有一个子集合中有三个数满足方程z y x =+ 。schur 于19l6年证明了对任意的正整数n ,都存在一个整数n f ,使得无论如何将集合},,2,1{n f 划分成n 个子集合,总有一个子集合中有三个数满足方程z y x =+。下面我们用Ramsey 数来证明这个结论。 定理 2.4.4 设{}n S S S ,,,21 是集合{}n r ,,2,1 的任一划分,即{}n n i n r S ,,2,11 ==,且=j i S S ?(),1,n j i j i ≤≤≠,则对某一个i ,i S 中有三个 数z y x ,,(不一定不同),满足方程z y x =+。其中=n r 个 n r )3,,3,3( 证明 将完全图n r K 中的n r 个顶点分别用n r ,,2,1 来标记,对n r K 的边进行n 着色如下:设v u ,是n r K 的任意两个顶点,若j S v u ∈-,则将边uv 染成第j 种颜色。由广义Ramsey 数n r 的定义知一定存在同色三角形,即有三个顶点c b a ,,,使得边bc ac ab ,,有相同的颜色,设为第j 种颜色。另不妨设c b a >>,则有,b a -,c b -c a -i S ∈。令,,,c a z c b y b a x -=-=-=则有i S z y x ∈,,,且z y x =+。 设n s 是满足下述性质的最小整数:将{}n s ,,2,1 任意划分成n 个子集合,总有一个子集合中台有三个数z y x ,,,满足方程z y x =+。容易证明,5,221==s s 143=s 。在本章的习题中,还列有一些关于n r 和n s 的上、下界的结论。 将前面的鸽巢原理和Ramsey 数进一步推广,可以得到下面更一般的Ramsey 定理: 定理2.4.5(Ramsey 定理) 设t q q q n ,,,,21 是正整数,且t q i ≥()1n i ≤≤,则必存在最小的正整数);,,,(21t q q q N n ,使得当≥m );,,,(21t q q q N n 时,设S 是一集合且S m =,将S 的所有t 元子集任意分放到n 个盒子里,那么要么有S 中的1q 个元素,它的所有t 元子集全在第一个盒子里;要么有S 中的2q 个元素,它的所有t 元子集全在第二个盒子里;…;要么有S 中的n q 个元素,它的所有t 元子集全在第n 个盒子里。 证明 略. 当1=t 时,Ramsey 定理说明)1;,,,(21n q q q N 存在,使得对任何 ≥m )1;,,,(21n q q q N 把m 个物体故人n 个盒子里,或者有1q 个物体在第一个盒子里;或者有2q 个物体都在第二个盒子里;…;或者有n q 个物体都在第n 个盒子里。从2.2节中鸽巢原理的加强形式知 1)1;,,,(2121+-+++=n q q q q q q N n n 当2=t 时,可以设想S 是一完全图的顶点集合,n 个盒子可以设想成n 种颜色S c c c n ,,,,21 的2元子集就是图中连接两个顶点的边。此时,Ramsey 定理中的 ),,,()2;,,,(2121n n q q q r q q q N = 特别地,当=n 2时,由2.3节中的结论知 6)3,3()2,3,3(==r N 9)4,3()2,4,3(==r N 定理2.4.6 2211),,(,);,(q t q t N q t t q N == 证明 若S 中元素少于或等于11-q 个,则将S 的所有t 元子集全部放入第一个盒子里。这时,没有S 的1q 元子集,它的所有t 元子集全在第一个盒子里;第二个盒子为空,也没有t 元子集在第二个盒子里。故11);,(q t t q N ≥。 若S 中恰有1q 个元素,把S 的t 元子集分放到两个盒子中。若第二个盒子非 空,即盒中至少存在一个t 元子集,该t 元子集在第二个盒子中;若第二个盒子为空,则S 的所有t 元子集全在第一个盒子里,且S 1q =。无论哪种情况,均满足要求,故11);,(q t t q N ≤。 综合以上分析,知11);,(q t t q N =。 同理可证:22),,(q t q t N = 内容提要 本章考虑鸽巢原理及其推广-Ramsey 定理。鸽巢原理是重要的组合基本原理之一,又名抽屉原理或鞋盒原理。 1、鸽巢原理 如果把n 十1个物体放进n 个盒子里,那么至少有一个盒子里装有两个或两个以上的物体。 2、鸽巢原理的加强形式 如果把121+-+++n q q q n 个物体放进n 个盆子里,那么或者第一个盒子里装有至少1q 个物体,或者第二个盒子里装有至少2q 个物体,…,或者第n 个盒子里装有至少n q 个物体。 当r q q q n ==== 21时,它有下列形式作为特例: 如果把n(r 一1)十1个物体放进n 个盒子里,那么至少有一个盒子装有r 个或多于r 个物体。 上述命题又等价于下列事实: 如果n 个非负整数n m m m ,,,21 的算术平均值121-≥++r n m m m n ,那么n m m m ,,,21 中至少有一个大于或等于r 。 3、Ramsey 定理 设r q q q n ,,,,21 是正整数,且r q r q r q n ≥≥≥,,,21 。那么存在正整数,从而存在最小正整数),,,,(21r q q q N n (它依赖且仅依赖r q q q n ,,,,21 )具有以下性质: 如果把至少具有),,,,(21r q q q N n 个元素的集合S 的所有r-子集(有r 个成员的子集)分配到n 个盒子中,那么或者有1q 个元素使得由它们组成的所有r-子集全在第1个盒子里或者有2q 个元索使得出它们组成的所有r-子集全在第2个 盒子里,…,或者有n q 个元素使得由它们组成的所有r-子集全在第n 个盒子里。 Ramsey 定理在r =l 时正是加强形式的鸽巢原理=)1,,,,(21n q q q N 121+-+++n q q q n 。因此,我们说Ramsey 定理是鸽巢原理的推广。 Ramsey 定理在n =2,r =2时可叙述为: 对正整数21,q q ,存在正整数)2,,(21q q N ,使得在空间的)2,,(21q q N 个或更多个点(没有三个共线)之间用红色或蓝色线段两两相连时,或者有1q 个点之间全部由红色线段相连或者有2q 个点之间全部由蓝色线段相连。 我们称),,,,(21r q q q N n 为Ramsey 数,已知 )2,3,3(N =6,)2,4,3(N =9,)2,5,3(N =14,)2,6,3(N =18 )2,3,3,3(N =17, 28)2,5,4(25≤≤N 等等。 练习题 1 一口袋内装有12个黑球和12个蓝球。问取出多少个球才能保证取出一个黑球和一个蓝球;一次取出多少个球才能保证取出一对蓝球。 解 至少取出13个球才能保证取得一个黑球和一个监球,而至少取出14个球才能保证取出一对蓝球。 2 某一制造铁盘的工厂,由于设备和技术的原因只能将将产的盘了的重量控制在ag 到(a +0.1)g 之间,现在需要制成重量相差不超过0.005g 的两铁盘来配制一架天平,问该工厂至少要生产多少铁盘,才能保证得到一对符合要求的铁盘。 解 我们把铁盘按重量分类,所有ag 到a 十0.005g 的为一类;a 十0.005g 到a 十0.01g 为一类; a 十0.01g 到a 十0.015g 为一类;a 十0.015g 到a 十0.02g 为一类;…a 十0.095g 到a 十0.1g 为一类,共计20类。由鸽巢原理可知,若该工厂生产21个铁盘,那么就能保证有两个铁盘属于同一类,因而它们之间的重量差将不超过0.005g 。 3 试证:m 只鸽子飞进n 个鸽巢时,有一个鸽巢至少飞进了11+?? ????-n m 只鸽子。([]表示不大于n m 1-最大整数)。 证 若每个鸽巢飞进的鸽子不多于?? ????-n m 1个,那么鸽子总数将不多于n n m ??????-1,即11-≤?? ????-≤m n m n m ,这是不可能的。 4 证明在n (2≥n )个人中总有两个人他俩在这群人中所认识的人数目相同。 证 若这n 个人中有一人不认识其他任何人,那么我们可只考虑余下n-1。人(n-1≥2。若不然余下一人,这两人互不认识,命题得证)。若这n 个人中有多人不认识其他任何人,那么命题得证(此时已有两人认识的人数是零)。因此,不失一般性,可设每个人至少认识另一个人。可是每个人又至多认识其他n-1个人,因此,据鸽巢原理知,这n 个人至少有两人认识的人的数日是一样的。 5 证明 如果n 十1个不同的数选自1,2,3,…,2n 中,那么它们中至少有一对数互质。 证 设这n 十1个数是121,,,+n a a a 且121+<< 6 一位国际象棋大师有11周的时间备战一场锦标赛,他决定每天至少下一盘棋,但为了不使自己过于疲劳他还决定在每周不能下棋超过12盘。证明存在连续若干天期间这位大师恰好下了2l 盘棋。 令1a 是在第一天所下的盘数,2a 是在第一天和第二天所下的总盘数, 而3a 是在第一天、第二天和第三天所下的总盘数,等等。由于每天至少要下一盘棋,故数值序列7721,,,a a a 是一个严格递增的序列。此外,11≥a ,而且出于每周下棋最多是12盘,故≤77a 12×ll =132。因此,我们有 13217721≤<<<≤a a a 。序列21,,21,217721+++a a a 也是一个严格递增序列, 153212*********≤+<<+<+≤a a a , 于是,7721,,,{a a a ,}153,2,1{}21,,21,217721 ?+++a a a ,因此154个数中至少有两个是相等的。而7721,,,a a a 是互不相等的,21,,21,217721+++a a a 也是互不相等的,因此,因此必然存在一个i 和一个j ,使得21+=i j a a 。从而,这位国际象棋大师在第j i i ,,1, +天总共下了21盘棋。 7 证明从1,2,…,200中可选取100个数使它们中没有一个能被另一个整除,并证明符合条件的100个数中的最小数至少是16。