第五章 抽屉原理和瑞姆赛(Ramsey)理论

第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章第五章 抽屉原理和瑞姆赛抽屉原理和瑞姆赛(Ramsey)(Ramsey)理论理论5.1 抽屉抽屉原理原理5.2 应用应用5.3 Ramsey问题问题 5.4 Ramsey数数第五章 抽屉原理和瑞姆赛(Ramsey)理论抽屉原理又称鸽巢原理或重叠原理,是组合数学中两大基本原理之一,是一个极其初 等而又应用较广的数学原理.其道理并无深奥之处,且正确性也很明显.但若能灵活运用,便可能得到一些意料不到的结果.第五章 抽屉原理和瑞姆赛(Ramsey)理论5.1 抽抽 屉屉 原原 理理定理定理 5.1.1(基本形式基本形式)将n+1个物品放入n 个抽屉,则至少有一个抽屉中的物品数 不少于两个.证证 反证之.将抽屉编号为:1,2,n,设第i个抽屉放有qi 个物品,则第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例 5.1.1】一年365天,今有366人,那么,其中至少有两人在同一天过生日.【例【例 5.1.2】箱子中放有10双手套,从中随意取出11只,则至少有两只是完整配 对的.第五章 抽屉原理和瑞姆赛(Ramsey)理论定理定理 5.1.2(推广形式推广形式)将q1+q2+qn-n+1个物品放入n 个抽屉,则下列事件至少有一个成立:即第i个抽屉的物品数不少于qi 个,i=1,2,n.证证 反证.不然,设第i 个抽屉的物品数小于qi(i=1,2,n)(即该抽屉最多有 qi-1个物品),则有与假设矛盾.第五章 抽屉原理和瑞姆赛(Ramsey)理论推论推论 5.1.1将n(r-1)+1个物品放入n 个抽屉,则至少有一个抽屉中的物品个数不少于r 个.推论推论 5.1.2 将 m 个物品 放 入n 个 抽 屉,则 至 少 有 一 个 抽 屉 中 的 物 品 个 数 不 少 于其中x表示取正数x 的整数部分,x表示不小于x 的最小整数.推论推论 5.1.3 若n 个正整数qi(i=1,2,n)满足则至少存在一个qi,满足qir.第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例5.1.3】有n 位代表参加会议,若每位代表至少认识另外一个代表,则会议上至少 有两个人,他们认识的人数相同.证证 设某代表认识的人数为k 个,则k1,2,n-1(视为n-1个抽屉).而会 议上有n 个代表,故每位代表认识的人数共为n 个数(视为n 个物品).那么,由基本定理,结论成立.第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例 5.1.4】任意一群人中,必有两人有相同数目的朋友.证证 设有n 个人(n2),分三种情形讨论:(1)每人都有朋友,由例5.1.3即知结论成立;(2)只有一人无朋友,余下的n-1人都有朋友,由(1)知此n-1人中必有两人有相同 数目的朋友;(3)有两人或两人以上的人无朋友,则朋友数为零的人已经有两个了,同样满足条件.第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论图 5.1.1 抽屉的选择第五章 抽屉原理和瑞姆赛(Ramsey)理论5.2 应应 用用【例【例 5.2.1】任意三个整数,必有两个之和为偶数(其差也为偶数).证证 制造两个抽屉:“奇数”和“偶数”,3个数放入两个抽屉,必有一个抽屉中至少有 两个数,由整数求和的奇、偶性质即知此二数之和必为偶数.同理可知,二者之差也为偶数.第五章 抽屉原理和瑞姆赛(Ramsey)理论问题一问题一 任给3个整数,其中必存在两个整数,其和能被2整除.证明证明 此问题是上例的另一种提法,目的是为了便于问题的推广.记这3个数为a1,a2,a3,令riai mod2,则ri=0,1(i=1,2,3),其中,符号“”表示模运算.将可能出现的余数值0,1视为两个抽屉,3个数ai 看作物品,以ri 的值决定将ai 放 入哪个抽屉.那么,由抽屉原理,某个抽屉中至少有两个ai,其除以2的余数相同,从而此2数即满足要求.第五章 抽屉原理和瑞姆赛(Ramsey)理论问题二问题二 任给n 个整数,其中必存在3个整数,其和能被3整除.问n 最小应为多少.证明证明 此问题是问题一的扩展.按照常规思路,当n=7时结论成立.即记这7个数为a1,a2,a7(7个物品),并令ri=ai mod3,则ri=0,1,2(3个抽屉)(i=1,2,7).同样,由抽屉原理知,至少有3个ai,其对应的余数ri 相同,而这3个数ai 即满足要求.但实际上7并不是最少数字,而是有n=5个整数就够了.第五章 抽屉原理和瑞姆赛(Ramsey)理论记这5个数为a1,a2,a5,令ri=ai mod3,则ri=0,1,2(i=1,2,5)(构造 抽屉和物品的方法同上).那么,可分两种情况讨论问题:(1)若有某3个ri 相同,则对应的3个ai 满足条件;(2)否则,5个ri 中最多有2个ri 相同(即每个抽屉中最多放2个物品),此时,每个 抽屉必不空.那么,从每个抽屉中选一个整数,该3个数也满足条件.若n=4,则结论不一定成立.例如,选 就找不到3个数满足要求.所以必有n=5.第五章 抽屉原理和瑞姆赛(Ramsey)理论问题三问题三 任给n 个整数,其中必存在k 个整数,其和能被k 整除.问n 最小应为多少.这是问题的一般提法.例如:k=2 时,n=3;k=3 时,n=5(而非7);k=4 时,n=7(请读者自己证明).从几何角度,可以将问题一、二重新描述如下:设一维数轴上有3个整点(指坐标为整数的点),则其中必存在两个点xi 和xj,其几 何中心(xi+xj)/2也是一个整点.当点数增到5个时,必存在3个点xi、xj 和xk,其几何 中心(xi+xj+xk)/3也是一个整点,而且整点的个数最少为5.上述这些例子,都相当于在一维空间上讨论问题.这些例子也可以推广到更一般的情 形,即多维空间.第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论而当n=9时,可分为两种情形讨论:(1)若某个抽屉中至少含有3个点,则选此种类型的3个点即可.(2)否则,每个抽屉中最多有两个点.但此时至少存在某一行,或某一列,或不同行不 同列的3个抽屉,其中不空.那么,按照前述推理,从此3个抽屉中各选一点,即达目的.由本例可以看出,在证明存在性问题的过程中,即使是完全一样的一个问题,只要问 题的规模发生变化,哪怕是增加1,证明问题的思路都可能与前不同.也就是说,小规模时 的方法解决不了问题,还需要人们重新考虑解决问题的新办法.对这样的一类问题,也只能在规模上做到有限解决.这也从一个方面反映了本章在学习、理解过程中的难度.尤其是 下面的两节,问题将暴露得更为突出.第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例5.2.5】将65个正整数1,2,65随意分为4组,那么,至少有一组,该组中最 少存在一个数,是同组中某两数之和或另一数的两倍.证证 用反证法.设任何一组数中的每一个数,它既不等于同组中另外两数之和,也不 等于同组中另一数的两倍.即任何一组数中任意两个数之差总不在这个组中.第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例 5.2.6】由mn+1个不同实数构成的序列ai|i=1,2,mn+1中必存在一个(m+1)项的递增子序列或(n+1)项的递减子序列.证证 某个序列bn|n=1,2,n是递增的,是指该序列满足:b1b2b2bn,则称其是递减的.第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例 5.2.7】证明:对任意正整数n,必存在仅由数字0、3和7组成的正整数,该正整 数能被n 整除.第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例 5.2.8】已知402个集合,每个集合都恰有20个元素,其中每两个集合都恰有一 个公共元素.求这402个集合的并集所含元素的个数.第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例 5.2.9】将上下两个同心而且同样大小的圆盘 A、B 各自划分成200个全等的扇 形,在A 盘上任取100个扇形涂上红色,其余100个扇形涂上蓝色,而B 盘上的200个扇 形任意地涂上红色或蓝色.证明,总可适当地转动两圆盘到某个位置,当上下的扇形互相 重合时,两圆盘上至少有100对具有相同颜色的扇形重叠在一起.第五章 抽屉原理和瑞姆赛(Ramsey)理论证证 定义两圆盘的扇形对齐时为一种重叠格局,由于每个圆盘都分为200个扇形,故 当其中一个圆盘转动时,可能出现的重叠格局有200个.对这200个格局计算同色扇形重 叠的对数.由于A 盘上红、蓝扇形各100个,因此,B 盘上每个扇形(或红色或蓝色)在这 200个格局里与A 盘上的同色扇形各重叠100次.对B 盘的每个扇形统计,在这200个格 局中B 盘的200个扇形与A 盘同色扇形重叠在一起共100200=20000对.因此可计算 出每一格局中同色扇形重叠的平均对数为20000200=100.因此至少有一格局中同色扇 形重叠的至少有100对.第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例 5.2.10】某俱乐部有3n+1名成员.对每一个人,其余的人中恰好有n 个愿与他 打网球,n 个愿与他下象棋,n 个愿与他打乒乓球.证明该俱乐部至少有3个人,他们之间 玩的游戏三种俱全.证证 将每个人作为平面上的一个点,且任何3点不共线.由每一点引出n 条红边、n 条 蓝边、n 条黑边,分别代表打网球、下象棋及打乒乓球.问题等价于要证明图中至少有一个 三边颜色全不相同的三角形.第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论定理定理5.2.1(极端原理极端原理):最小数原理最小数原理1 在有限个实数组成的集合中,必存在最小的数.最小数原理最小数原理2 设 N是自然数全体组成的集合,若 M 是 N 的非空子集,则 M 中必有 最小的数.最大数原理最大数原理1 在有限个实数组成的集合中,必存在最大的数.最大数原理最大数原理2 在由负整数组成的集合(有限或无限)中必存在最大的负整数.第五章 抽屉原理和瑞姆赛(Ramsey)理论 最短长度原理最短长度原理1 任意给定相异两点,所有连接这两点的线中,以直线段的长度为 最短.最短长度原理最短长度原理2 在连接一个已知点与某个已知直线或已知平面上的点的所有线段 中,以垂线段的长度为最短.第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例5.2.11】某次体育比赛,每两名选手赛一场,每场比赛一定决出胜负.通过比赛确 定优秀选手.选手A 为优秀选手的条件是:对任何选手B,或者A 胜B,或者A 间接胜B.所谓间接胜B,是指存在选手C,使得A 胜C 而C 胜B.假定按上述规则确定的优秀选手 只有一名,求证这名选手全胜所有其他选手.第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论第五章 抽屉原理和瑞姆赛(Ramsey)理论【例【例5.2.13】求证:在四面体 ABCD 中,必有某个顶点,把从它引出的三条棱当作 边,这三条边可以构成一个三角形.证证 首先,已知三条线段能构成一个三角形的充分必要条件是任何两线段长度之和大 于第三条边的长度.其次,由最大数原理1知,在四面体 ABCD 的4条棱中必存在最长的 棱.设AB 为最长棱之一,则A、B 两点中至少有一点,以此点为端点的3条棱的长度满足 构成三角形的条件.若不然,由于AB 是最长棱,故以A 为端点的3条棱AB、AC、AD 和 以B 为端点的3条棱BA、BC、BD 分别满足第五章 抽屉原理