解

解答：

这些人和他们之间的关系显然形成一个图。首先证明下列两点：

1. 这个图由很多三角形组成，而且不同的三角形没有共同的边；
2. 如果命题不成立，则存在k>1，使得这个人群共有2k*(2k-1) + 1 个人，而且每个人都有2k 个朋友。

很容易看出1 成立。注意这蕴含每个人都有偶数个朋友。

对2，设朋友最多的人有2k个朋友，即这个人是k个三角形的顶点。称这个人为第一级，他的2k个朋友为第二级。第二级人中的朋友关系是两两成对的，他们之间没有其余的关系。再设有人不在这两级中。这样的人必定是第二级人的朋友，称他们为第三级。第三级中人只能是一个第二级中人的朋友，而与其它的第二级中人必须有公共朋友，这就是说，每个第二级中人都有第三级中人为朋友。

现在设第二级中人朋友最少的有2j个朋友，即有2j-2个第三级朋友。这个人与其他第三级人的公共朋友就是这2j-2个人和这个人的唯一第二级朋友。也就是说，其他的第二级人（共2k-2个）手下最多还有(2k-2)(2j-2)个第三级人，这就蕴含每个第二级人都恰有2j个朋友，以及每个第三级人都有2k个朋友。

我们再把这个图重新安排一下：任取一个第三级人作为第一级，这样就有一些原来的第二级人落到第三级。用同样的论证，这些人也有2k个朋友，即k=j。

最后，从三级的人数推出人群共有2k*(2k-1) + 1 个人。

（如果要解下面的土耳其奥赛题，到这里就够了，因为2009 不是这样的数。对任意n则要难的多。）

再下一步就是从这里推出矛盾。这一步有两种方法。第一种用线性代数：考虑这个图的连结矩阵，NXN的矩阵A（N为总人数），A(i,j)＝1如果i，j是朋友，否则等于0。A是对称矩阵，主对角元全为0，每一行有2k个1，其它全是0。易知A^2的主对角元全为2k，其它元全为1(因为任意两人有一个共同朋友，每个人有2k个朋友)。A^2的特征根为一个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矛盾。

这个方法是Erdos给出的。

另一种方法还是继续用图论。因为太繁琐，这里就不给出了。