MathDB

existence of subset with conditions

Source: Mongolia 1999 Grade 10 P5

May 5, 2021

combinatorics

Problem Statement

Let

A_1,\ldots,A_m

be three-element subsets of an

n

-element set

X

such that

|A_i\cup A_j|\le1

whenever

i\ne j

. Prove that there exists a subset

A

of

X

with

|A|\ge2\sqrt n

such that it does not contain any of the

A_i

.

Back to Problems View on AoPS