开学季1对1辅导

高考

101教育热线电话
400-6869-101
微信
当前位置: 高考> 高考备考> 高考各科复习> 高考数学> 高考数学知识点

晚宴上的客人与拉姆赛定理

来源:101教育 2016-11-09 字体大小: 分享到:

作者:[美] 珀洛斯(J. P. Paulos)

  英国数学家弗朗克·拉姆赛证明了这样一条定理:对于充分大的元素集合(人、数或几何点),每一个它的成员的配对,比如,有联系的或者无联系的,总是原来的集合的一个有一种特殊性质的较大的子集。或者子集的所有成员将互相有联系,或者它的所有成员互相无联系。在较大的无序集合中,这一子集是有序的不可避免的小岛(在群岛中有许多有意义的小岛);这就是说,垃圾足够多的话,免费午餐就能保证存在。

  问题可以用晚宴上的客人来重新叙述。对于大小为3的有序小岛的拉姆赛问题是:

  为使出席的客人中至少有3人互相认识或者至少有3人互相陌生,应该邀请的最少客人数是多少?(假定如果玛萨认识乔治,那么乔治也认识玛萨。)答案是6,这可以通过设想你是宴会上的一个客人来看到这点。由于你认识或不认识其他5位的每一位,你将或者至少认识他们中的3位,或者至少不认识他们中的3位。为什么?假设你认识其中的3个(如果你至少不认识3个,论证是一样的),并且考虑你的3个熟人之间是什么关系。如果任何2位互相认识,那么这2人与你就组成一个互相认识的3位宾客小组。另一方面,如果你的3位熟人互相都不认识,那么他们3人就构成互相不认识的3人小组。这样,6位客人就已足够。为看到5位客人不够,设想你在一个很小的宴会上,其中你刚好认识其他4位中的2位,而他们2位中的每一位又都只认识你所不认识的2位中的1位,并且2人认识的又不同。

  对于大小为4的小岛,客人数必须为18,而对于5,则是在43到55之间。对于更大的数,分析就要复杂得多,拉姆赛类型的问题的答案仅对于很少的数是已知的。

  自从1930年拉姆赛去世以来,已发展成整个小作坊来从事证明同样的一般形式的问题:

  总存在某个具有规律性模式的给定大小的子集(即某种阶的小岛)的集合有多大?多产而周游世界的数学家保尔·爱尔多希发现许多这样的岛,其中有些非常优美。特殊的岛的细节是复杂的,但是一般来说,关于集合的必要大小的问题答案通常会落入狄阿可尼斯的格言:如果它足够大,几乎所有垃圾都会发生。

上一篇:承诺、问题及隐含意图

下一篇:复杂性、混沌和多余的零钱

2020高考备考
标签: 数学 (责任编辑:101教育小编)

新学期开学季

姓名
手机号
年级
*图形验证码
获取验证码
免费预约
开学季1对1辅导