MathDB

2

Part of 1987 IMO Shortlist

Problems(1)

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

Source:

8/19/2010
At a party attended by nn married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques C1,C2,⋯ ,CkC_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≥4n \geq 4, then k≥2nk \geq 2n.
Proposed by USA.
combinatoricsgraph theoryExtremal Graph Theorycombinatorial inequalityIMO Shortlist