MathDB

A subset of X with at least root 2n elements

Source:

February 1, 2011

floor functioncombinatorics proposedcombinatorics

Problem Statement

Let

X

be an

n

-element set and let

A_1,\ldots ,A_m

be subsets of

X

such that
i)

|A_i|=3

for each

i=1,\ldots ,m

.
ii)

\lfloor\sqrt{2n}\rfloor

for any two distinct indices

i,j

.
Show that there exists a subset of

X

with at least

\lfloor\sqrt{2n}\rfloor

elements which does not contain any of the

A_i

’s.

Back to Problems View on AoPS