9

Part of 2004 Romania Team Selection Test

Problems(1)

easy, but yet an uncanny level of difficulty

Source: Romanian ROM TST 2004, problem 9, created by Harazi

n\geq 2

be a positive integer, and

X

n

A_{1},A_{2},\ldots,A_{101}

X

such that the union of any

50

of them has more than

\frac{50}{51}n

elements. Prove that among these

101

subsets there exist

3

subsets such that any two of them have a common element.

pigeonhole principlelinear algebramatrixinequalitiescombinatorics solvedcombinatorics