At a party attended by
married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques
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
, then
.
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.