At a party attended by
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques
![C_1, C_2, \cdots, C_k](/media/m/e/4/f/e4fe1a9f989aee292128edc930e87d66.png)
with the following property: no couple are members of the same clique, but for every other pair of persons there is exactly one clique to which both members belong. Prove that if
![n \geq 4](/media/m/4/f/2/4f2c159d62a3247dd33ee8d022ae9f37.png)
, then
![k \geq 2n](/media/m/6/2/4/62401530f3df94300189ed3d23a09100.png)
.
Proposed by USA.
%V0
At a party attended by $n$ married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques $C_1, C_2, \cdots, C_k$ with the following property: no couple are members of the same clique, but for every other pair of persons there is exactly one clique to which both members belong. Prove that if $n \geq 4$, then $k \geq 2n$.
Proposed by USA.