组合数学（张永刚）吉林大学 第二章 鸽巢原理和Ramsey定理.pptxVIP

1;2;3;4;5;6;7;8;9;证明：对于任意一个整数，它除以100的余数显然只能有如下100种情况， 0，1，2，3，……，99 而现在有任意给定的52个整数，我们需要构造51个盒子，即对这100个余数进行分组，共51组： {0},{1，99},{2，98},{3，97},……，{49，51}， {50};根据定理2.1.1，这52个整数，必有两个整数除以100的余数落入上面51组中的同一组中， 若是{0}或{50}则说明它们的和及差都能被100整除； 若是剩下的49组的话，因为一组有两个余数，余数相同则它们的差能被100整除，余数不同则它们的和能被100整除。;12;13;14;15;16;17;而现在共有19列，根据定理2.1.1，无论怎样涂色，则必有两列与图中的某一列相同，即各自所包含的两个同色单元格的位置相同、颜色相同。即结论成立。 ;19;1、子序列概念如果 是一个序列，那么， 是一个子序列，其中， 2、递增子序列概念 若满足 3、递减子序列概念 若满足 ;21;22;23;24;25;26;27;28;29;30;31;32;33;34;35;36;37;38;39;任何一个6人聚会，必有3个人相互认识或者相互不认识 ;41;42;定理 2.3.1 设p，q是正整数，p，q≥2，则存在最小的正整数R(p,q)，使得当n≥R(p,q)时，用红、蓝两色涂色Kn的边，或者存在一个蓝色的完全p边形Kp，或者存在一个红色的完全q边形Kq。 ;44;45;46;47;(22 February 1903 – 19 January 1930) was a British mathematician who, in addition to mathematics, made significant and precocious contributions in philosophy and economics before his death at the age of 26. He was a close friend of Ludwig Wittgenstein, and was instrumental in translating Wittgensteins Tractatus Logico-Philosophicus into English, and in persuading Wittgenstein to return to philosophy and Cambridge.;生于剑桥，其父亲是麦格达伦学院的校长，其弟弟迈克尔·拉姆齐是第100任坎特伯里大主教。拉姆齐于温切斯特公学学习，后来进入剑桥大学三一学院学习数学。 他涉猎了很多领域。在政治上，他有左翼的倾向；宗教上，其妻指他是个态度坚定的无神论者。他和查尔斯·凯·奥格顿聊天时，说他想学德语。奥格顿便给他一本文法书、字典和一篇深奥的心理学论文并告诉他：使用那本文法书和字典，告诉我们你的想法。约一星期后，他不止学会了德语，还对语法书中一些理论提出了反对意见。 他阅读了维根斯坦的Tractatus Logico-Philosophicus。这本书深深影响了他，1923年他去奥地利跟维根斯坦讨论。1924年21岁的他成为国王学院的研究员。 拉姆齐为治疗慢性肝疾而接受腹部手术，但术后并发黄疸，于1930年1月19日病逝于伦敦盖氏医院（Guys Hospital），得年仅26岁又11个月。;;保罗·埃尔德什（Erd?s Pál，在英语中作Paul Erd?s）（1913年3月26日－1996年9月20日），其音读作air-dish，匈牙利语中的意思是来自山林。匈牙利籍犹太人，发表论文高达1475篇（包括与人合写的），为现时发表论文数最多产的数学家（其次是欧拉）；曾和511人合写论文。爱多士遗传了来自数学教师父母优异的数学天赋，三岁时就能轻松心算一个人一生所活的秒数，并每日在客人面前表演四位数的乘法心算。他年仅二十一岁即被厄特沃什·罗兰大学(即布达佩斯大学)授予数学博士学位，师从数学家Lipót Fejér(他也是冯纽曼的导师)。之后爱多士为了逃离纳粹的追捕，历任曼彻斯特大学教授与普林斯顿大学之研究人员。 爱多士热爱自由，十分讨厌权威，尤其是法西斯。他四处游历，探访当地的数学家，与他们一起工作，合写论文。他很重视数学家的培训，遇到有天份的孩子，会鼓励他们继续研究。爱多士经常沉思于数学问题，视数学为生命，在母亲死后，他开始经常服食精神药物。他经常长时间工作，老年仍每日工作19小时，酷爱