解

解答：

這些人和他們之間的關係顯然形成一個圖。首先證明下列兩點：

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給出的。

另一種方法還是繼續用圖論。因為太繁瑣，這裏就不給出了。