MathDB

easy, but yet an uncanny level of difficulty

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

May 3, 2004

pigeonhole principlelinear algebramatrixinequalitiescombinatorics solvedcombinatorics

Problem Statement

Let

n\geq 2

be a positive integer, and

X

a set with

n

elements. Let

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

be subsets of

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.