If n ≥ 4, then k ≥ 2n - (IMO SL 1987-P2)

Moderator: elim

If n ≥ 4, then k ≥ 2n - (IMO SL 1987-P2)

Postby elim » Fri Oct 07, 2011 3:54 pm

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 \ge 4$, then $k \ge 2n$.

Proposed by USA.

src
elim
 
Posts: 64
Joined: Mon Feb 08, 2010 8:03 pm

Return to Combinatorics

Who is online

Users browsing this forum: No registered users and 1 guest

cron