六人集会问题

       榕城老应

好的智力游戏，挑战的是智力而不是知识。简单直观有确定的答案，但有一定的难度。问题的解决，不仅有征服高峰的快感，还常有开拓眼界的收获。上一个帖子“称球问题”就属于这一类。
 
我这里再出一道题。为了让大家有收获，先给大家一个思路。

我所学的许多知识中大约最直观的就是这个“抽屉原理”了。它是组合数学的一个基本原理，最先是由德国数学家狄利克雷明确地提出来的，因此，也称为狄利克雷原理。

这原理形象的说法是：将10个苹果放在9个抽屉，至少有一个抽屉会有2个或以上的苹果。如此等等，总之傻子都能明白的道理。其实我在上面称球问题的定理证明中就几次用到抽屉原理。只不过人人不打磕的就能通过，所以就不再提了。这抽屉原理，用信息也能给出个解释，不过组合数学觉得用集合论就能说明白，就不提了。
 
抽屉原理如果没有个不寻常的应用，那也没人会认这个账，早让奥卡姆的剃刀给切去了。下面是题目，给大家一个验证的机会。
 
1958年6/7月号的《美国数学月刊》上有这样一道题目： 证明在任意6人的集会上，有3个人以前彼此都相识，或者有3个人以前彼此不相识，这两者必居其一。
 
这道题的数目有限，自然可以用枚举法证明。但用抽屉原理，几句话就能说清，你知道该怎么证明吗？
 
别看这道题简单，六人集会问题是组合数学中著名的拉姆塞定理的一个简单的特例，它的思路可以得出另一些深入的结论。它们构成了组合数学中的“拉姆塞理论”。

×××××

你想出来怎么证明了吗？要是没有，下面是证明。

在6人中任选一人（称为主人），他与其他5人的关系，可以分成两类：认识的和不认识的。5人分2类，至少有一类是3人以上（抽屉原理）。

假设认识的至少有3人，这3人如果互相全不认识，就满足问题中后一条件。否则，至少有两人认识，再加上主人，就有了互相认识的3个人，满足前一条件。因此，两条件必居其一。

假设不认识的起码有3人，将前一假设论中“认识”与“不认识”互换，完全对称地可以证明了结论。

[LingYuan]

确实是这样。全世界有六十亿人，任何两个人都可以通过六个熟人联系起来，看来这个世界里的人还是紧密相联的。

以此类同的，比如信息传递也是，给世界上任何一个人写信，只要四行地址就能把收信人唯一地给确定下来，这点，我觉得也有点“不可思议”。

[ying312]

“友谊定理”还没听说。“六度分隔”这个6是一般都能把他们联系起来。虽然最初的社会学实验并不可靠，但后来的仿真实验和理论上的研究证实这样的概率还是很大的。

[LingYuan]

以前还听说过有个叫友谊定理的，好像和这六人集会有关是的：
“在3个或以上的人群中，若每两个人都有一个共同相识的人，肯定有一个人和谁都认识”。不知道在数学上怎么把这两个定理连起来。

另外，数字六很有意思，有个六度分隔的定理，也叫小世界现象吧。说世界上任何两个不管多么陌生的人，肯定可以找到六个互相彼此熟悉的人把他们联系起来。

在立体几何中，数字“6”出现的也很频繁。