什么是“六人集会问题”V5

1947年，匈牙利奥林匹克数学竞赛试题中有这样一道证明题：“证明在任意6个人中，至少有3人相互握过手，或者至少有3人相互未握过手。”1958年6月，著名的《美国数学月刊》将它作为一个数学游戏问题重新发表，它从此成了一道国际上著名的趣题，被称为“六人集会问题”。

怎样证明呢？我们先不妨把任意6个人设想成平面上6个不同的顶点，分别用大写英文字母A、B、C、D、E、F表示，并且用两个顶点间连成的实线来表示两个人握过手，用两个顶点间连成的虚线来表示他们未握过手。这样，我们就可以得到一些表示6人之间握手关系的图。从图1可以看出，上述命题都是成立的。

那么这样的图一共有多少呢？在握手关系图中，从每个顶点出发，都可以与其它5个顶点连成直线，共有6×5=30条，其中有一半是重复的，所以在握手关系图中，共有30÷2=15条边。而每条边都有实边和虚边两种可能，因此，所有的6人握手关系图共有2¹⁵种不同的情况。下面我们来证明上面的命题。

先来看看其中一个顶点的情况，不妨看A，其他5人要么至少有3人与他握过手，要么至少有3人与他未握过手，否则，与他握过手的与未握过手的人数加起来就将小于5。我们先来看第一种情况，A与其中至少3人握过手，不妨设为B、C、D。如果B、C、D3人中相互未握过手（图2），那么命题中至少有3人相互未握过手的结论就成立了。反之，3人中至少有2人握过手，不妨设为C和D（图3），那么命题中至少有3人握过手的结论就成立了。我们再来看第二种情况，A与其中至少3人未握过手，不妨也假设为B、C、D，这时只要将图2中的实边改为虚边，其它的证明同上，大家不妨自己试一试，会得到什么样的结论。

综上所述，我们可以证明：在任意6个人中，至少有3人相互握过手，或者至少有3人相互未握过手。

本题还可以进一步推广：在不少于6人的一群人中，至少有3人相互握过手，或者至少有3人相互未握过手。但如果少于6人，结论就可能不成立。如图4就是一个反例，5人中既没有3人相互握过手，也没有3人相互未握过手。

关键词：六人集会问题