晚宴上的客人与拉姆赛定理
第 2 页
晚宴上的客人与拉姆赛定理
英国数学家弗朗克·拉姆赛证明了这样一条定理：对于充分大的元素集合（人、数或几何点），每一个它的成员的配对，比如，有联系的或者无联系的，总是原来的集合的一个有一
晚宴上的客人与拉姆赛定理
第 2 页
晚宴上的客人与拉姆赛定理
英国数学家弗朗克·拉姆赛证明了这样一条定理：对于充分大的元素集合（人、数或几何点），每一个它的成员的配对，比如，有联系的或者无联系的，总是原来的集合的一个有一种特殊性质的较大的子集。或者子集的所有成员将互相有联系，或者它的所有成员互相无联系。在较大的无序集合中，这一子集是有序的不可避免的小岛（在群岛中有许多有意义的小岛）；这就是说，垃圾足够多的话，免费午餐就能保证存在。
问题可以用晚宴上的客人来重新叙述。对于大小为3的有序小岛的拉姆赛问题是：
为使出席的客人中至少有3人互相认识或者至少有3人互相陌生，应该邀请的最少客人数是多少？（假定如果玛萨认识乔治，那么乔治也认识玛萨。）答案是6，这可以通过设想你是宴会上的一个客人来看到这点。由于你认识或不认识其他5位的每一位，你将或者至少认识他们中的3位，或者至少不认识他们中的3位。为什么？假设你认识其中的3个（如果你至少不认识3个，论证是一样的），并且考虑你的3个熟人之间是什么关系。如果任何2位互相认识，那么这2人与你就组成一个互相认识的3位宾客小组。另一方面，如果你的3位熟人互相都不认识，那么他们3人就构成互相不认识的3人小组。这样，6位客人就已足够。为看到5位客人
第 3 页
晚宴上的客人与拉姆赛定理 来自淘豆网m.daumloan.com转载请标明出处.
