Ramsey数.docx

抽屉原理与拉姆塞（Ramsey）定理
教学安排的说明

章节题目：抽屉原理与拉姆塞定理
学时分配：2课时
本章教学目的与要求：理解抽屉原理，能够用抽屉原理解决简单的数学问题，理解拉姆塞数的含义，理解抽屉原理与拉姆塞定理间的联系。
其它：本部分为补充内容

课堂教学方案

课程名称：抽屉原理与拉姆塞（Ramsey）定理
授课时数：2学时
授课类型：理论课
教学方法与手段：讲授法
教学目的与要求：理解抽屉原理，能够用抽屉原理解决简单的数学问题，理解拉姆塞数的含义，理解抽屉原理与拉姆塞定理间的联系。
教学重点、难点：抽屉原理与拉姆塞定理间的联系
教学内容：
补充：
抽屉原理与拉姆塞（Ramsey）定理
抽屉原理
抽屉原理又叫鸽巢原理.
桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，有的抽屉可以放一个，有的可以放两个，有的可以放五个，但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理。
抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n＋1或多于n＋1个元素放到n个集合中去，其中必定至少有一个集合里至少有两个元素。”
抽屉原理有时也被称为鸽巢原理（“如果有五个鸽子笼，养鸽人养了6只鸽子，那么当鸽子飞回笼中后，至少有一个笼子中装有2只鸽子”）。它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原理。它是组合数学中一个重要的原理。
一．抽屉原理最常见的形式
1.抽屉原理的最简单形式：
如果把十l件东西放入个盒子，则至少有一个盒子含有两件或更多件东西。
[证明]（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+1，矛盾.
例１：400人中至少有两个人的生日相同.
解：将一年中的365天视为365个抽屉，400个人看作400个物体，由抽屉原理可以得知：至少有两人的生日相同.
又如：我们从街上随便找来13人，就可断定他们中至少有两个人属相相同.
“从任意5双手套中任取6只，其中至少有2只恰为一双手套。”
“从数1，2，...，10中任取6个数，其中至少有2个数为奇偶性不同。”
2.抽屉原理的加强形式
设是个正整数，如果将件东西放入个盒子里，则必有第个盒子里至少装有件东西。
特别地，当时，则有：
若将个物体放入个盒子中，则必存在一个盒子至少装个物体。
取，则有：把多于mn个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。
如果个非负整数的平均数大于，那么至少有一个整数大于或等于，这是平均原理，
抽屉原理多用于证明题或作出某种判断或最好决策。
二．应用抽屉原理解题
抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
例2在小于或等于2的任意+1个不同的正整数中，一定存在两个正整数，使得它们是互素的。
证明：构造如下个抽屉，放1，2；放3，4；…；放2-1，2n。根据抽屉原理，这+1个小于或等于2的正整数放入这个抽屉中。可以断定，必有两个数被放入同一个抽屉中，且这两个数相邻。比如有和-1在同一抽屉中，可以证明和-1是互素的。设为和-1的任意正整数因子，则必存在正整数，使得，于是，.因此，即和-1是互素的。
拉姆塞（Ramsey）定理
抽屉原理的一个深刻而又重要的推广就是以英国逻辑学家FrankPlumptonRamsey命名的定理——Ramsey定理
弗兰克·普伦普顿·拉姆塞(FrankPlumptonRamsey,1903-1930)是位天才的英国科学家，只活了27岁。但在经济学中做出极重要贡献，包括概率论，赋税论，最优储蓄理论，在他去世的1930年，他发表了一篇学术论文，其副产物就是所谓拉姆塞理论。
1、拉姆塞（Ramsey）定理简介
在1953年美国的WilliamLowellPutnam数学竞赛中，包含着这样一个问题：对于一个阶为6的完全图，其每条边用红色或蓝色两种颜色染色。证明：必定可以找到3个顶点，使得连接它们的三条边都有相同的颜色。
其通俗解释为：如果认识是相互的，在某个宴会上，6人中必有三个人相互认识或三个人相互不认识。
分析:上述两问题等价的。该问题反映出人与人之间或相互认识或相互不认识这种二元关系，这正好符合用图论方法研究问题的特征。由于所证结果是存在三人相互认识或相互不认识。于是，我们可以常用另外的刻画方式进行处理：若两人认识，在相应顶点之间连一条边，并染成红色（即连一条红边）；若两人不认识，也在相应顶点之间连条边，并染成蓝色（即连一条蓝边），从而就形成了一个染有红、蓝两色的。于是，可将待证问题转化为：在二色中一定存在同色三角形（红色三角形或蓝色三角形）。
证明：用表示这任何