如果一个人数大于等于三的人群满足下面这个条件：［人群中任意两个人www.ddhw.com
都有一个而且只有一个共同的朋友］，那么这群人中一定有一个人是所有人
的朋友。
www.ddhw.com
解答：
www.ddhw.com
这些人和他们之间的关系显然形成一个图。首先证明下列两点：
www.ddhw.com
1. 这个图由很多三角形组成，而且不同的三角形没有共同的边；www.ddhw.com
2. 如果命题不成立，则存在k>1，使得这个人群共有2k*(2k-1) + 1 个人，而且每个人都有2k 个朋友。
www.ddhw.com
很容易看出1 成立。注意这蕴含每个人都有偶数个朋友。
www.ddhw.com
对2，设朋友最多的人有2k个朋友，即这个人是k个三角形的顶点。称这个人为第一级，他的2k个朋友为第二级。第二级人中的朋友关系是两两成对的，没有其余的关系。再设有人不在这两级中。这样的人必定是第二级人的朋友，称他们为第三级。第三级中人只能是一个第二级中人的朋友，而与其它的第二级中人必须有公共朋友，这就是说，每个第二级中人都有第三级中人为朋友。www.ddhw.com
www.ddhw.com
现在设第二级中人朋友最少的有2j个朋友，即有2j-2个第三级朋友。这个人与其他第三级人的公共朋友就是这2j-2个人和这个人的唯一第二级朋友。也就是说，其他的第二级人（共2k-2个）手下最多还有(2k-2)(2j-2)个第三级人，这就蕴含每个第二级人都恰有2j个朋友，以及每个第三级人都有2k个朋友。
www.ddhw.com
我们再把这个图重新安排一下：任取一个第三级人作为第一级，这样就有一些原来的第二级人落到第三级。用同样的论证，这些人也有2k个朋友，即k=j。
www.ddhw.com
最后，从三级的人数推出人群共有2k*(2k-1) + 1 个人。www.ddhw.com
www.ddhw.com
再下一步就是从这里推出矛盾。这一步有两种方法。第一种用线性代数：考虑这个图的连结矩阵，NXN的矩阵A（N为总人数），A(i,j)＝1如果i，j是朋友，否则等于0。A是对称矩阵，主对角元全为0，每一行有2k个1，其它全是0。易知AA的主对角元全为2k，其它元全为1(因为任意两人有一个共同朋友，每个人有2k个朋友)。AA的特征根为一个N+2k-1，N-1个2k-1。A的特征根应该是一个+/-sqrt(N+2k-1)，N-1个+/-sqrt(2k-1)。但是容易看出2k是A的一个特征根，即2k = sqrt(N+2k-1)。而A的特征根之和为0(主对角元全为0)，因此其它N-1个特征根加起来等于-2k，即存在整数I，使得I * sqrt(2k-1) = 2k，或I = 2k/sqrt(2k-1)。这只有k = 1 时才可能，这与一开始的假设k>1矛盾。
www.ddhw.com
这个方法是Erdos给出的。www.ddhw.com
www.ddhw.com
另一种方法还是继续用图论。设p为2k-1 的一个素因子。考虑图中长度为p的圈 ({v0,v1,v2,...,vp-1,v0} 是长度为p的圈如果v1是v0的朋友，v2是 v1的朋友，...，v0是vp-1的朋友)。这里不要求vi是各不相同的，而且起点不同的圈算作不同的，例如{v0,v1,...,vp-1,v0} 与{v1,v2,....vp-1,v0,v1}算作不同的圈。记所有长度为p的圈 的集为Sp。我们计算|Sp|。因为p是素数，这些圈都不是周期的，即同一个圈可以算p遍。所以|Sp| 一定是 p的倍数。www.ddhw.com
www.ddhw.com
下面再考虑长度为 p-1的路径，即 {v0,v2,...,v(p-2)} 使得v1是v0的朋友，v2是 v1的朋友，...，v(p-2)是v(p-3)的朋友。记L为所有这样路径的集。可以算出|L|= N*(2k)^(p-2)：N 个点都可以作为起点，之后总有2k个选择。这些路径中，有些已经是圈，即v(p-2)=v0，记这些为 L1，剩下不是圈的为 L2。L1中的圈可以再加上v0的任意一个朋友（共2k个），形成一个长度为p的圈 。L2中的路径可以再加上v0与v(p-2)的朋友，形成一个圈。这样形成的圈包括了Sp中所有的圈，即|Sp| = 2k|L1| + |L2| = (2k-1)|L1| + |L| = (2k-1)|L1| + (2k(2k-1)+1)*(2k)^(p-2) = (2k-1)*(|L1|+(2k)^(p-1)) + (2k)^(p-2)。这里第一项是p的倍数，第二项不是p的倍数，因此|Sp|不是p的倍数，与前面所得矛盾。
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2006-3-9 05:28:16
收藏
分享
支持
反对
置顶卡
千斤顶
楼主