什么是“六人集会问题”

1947年匈牙利奥林匹克数学竞赛试题中有这样一道证明题：“在任意6个人中，至少有3人相互握过手，或者至少有3人相互未握过手。”

由于这道题出得很精彩，因此著名的《美国数学月刊》在1958年6月号上作为一个数学游戏问题重新加以发表，这样就使它成了一道国际上著名的趣题，被称为“六人集会问题”。

怎样证明呢？先让我们来分析一下。不妨把任意6个人设想成平面上6个不同的顶点，分别用大写英文字母A、B、C、D、E、F表示。

我们约定，如果两个人握过手，就在对应的2个顶点之间连条实线；如果他们未握过手，就在对应的2个顶点之间连条虚线。用这种方法，我们就可以得到一个表示6人之间握手关系的图。例如，图1中的3个图表示了6人之间可能出现的3种握手关系。

图1

在图1（a）中，我们可以找到3个人是相互握过手的，例如C、D、E。在图1（6）中，我们可以找到3个人是相互未握过手的，例如A、B、D。在图1（c）中，我们既可以找到3个人是相互握过手的，例如A、B、C；也可以找到3个人是相互未握过手的，例如D、E、F。

在握手关系图中，共有15条边，每条边都有实边和虚边2种可能，因此，所有的6人握手关系图共有2¹⁵种不同的情况。当然，我们不愿意将2¹⁵种不同情况的握手关系图都画出来，然后采用穷举的办法证明我们所要求的结论。这样做太麻烦了，我们希望本题有一个简短而优美的证明。

先来看看A的情况，除A以外，共有5个人。因为与A握过手的人数加上与A未握过手的人数等于5。所以A与其中至少3人握过手；否则，A与其中至少3人未握过手。两者必居其一。不然的话，与A握过手以及与A未握过手的人数都不超过2，加起来的和数就将小于5。

如果A与其中至少3人握过手。不妨设A与B、C、D3人握过手，如图2所示。接下来看看B、C、D3人之间的握手情况。如果他们相互之间未握过手，如图3所示，于是就符合了问题中确有3人相互未握过手的结论。否则的话，B、C、D3人中是有人相互握过手的，不妨设C与D握过手，如图4所示。这时从图4上可以看出，A、C、D3人是相互握过手的，符合了问题中确有3人相互握过手的结论。

如果A与其余5人中的至少3人未握过手，假定A与B、C、D未握过手，这时只要将图2中的实边改为虚边。以下的讨论与上面是类似的。检查B、C、D三者之间的握手情况，如果他们相互之间握过手，则出现相互握过手的3人，符合了问题中要求的结论。如果他们之中有人未握过手，譬如C与D未握过手，则A、B、D3人相互未握过手，也符合了问题中要求的结论。

综合以上各种情况的分析，我们可以作出结论：在任意六个人中，至少有3人相互握过手，或者至少有3人相互未握过手。

本题的解决还进一步表明：在不少于6人的一群人中，至少有3人相互握过手；或者至少有3人相互未握过手。如果少于6人，结论可能不成立。像图5就是一个反例，这5个人之间，既没有3人相互握过手，也没有3人相互未握过手。

本题是一道趣味数学题，换个形式还曾经作为一道数学竞赛题。不仅如此，它与图论和组合数学中目前正在研究的拉姆赛问题有着密切的关系呢！