MathDB

Fun sets [3-element subsets of n-element set; [sqrt(2n)]]

Source: Romanian IMO Team Selection Test TST 1999, problem 15; 15-th Iranian Mathematical Olympiad 1997/1998

August 15, 2005

floor functionceiling functionquadraticsprobabilityexpected valuecombinatorics unsolvedcombinatorics

Problem Statement

Let

X

be a set with

n

elements, and let

A_{1}

,

A_{2}

, ...,

A_{m}

be subsets of

X

such that: 1)

|A_{i}|=3

for every

i\in\left\{1,2,...,m\right\}

; 2)

|A_{i}\cap A_{j}|\leq 1

for all

i,j\in\left\{1,2,...,m\right\}

such that

i \neq j

. Prove that there exists a subset

A

of

X

such that

A

has at least

\left[\sqrt{2n}\right]

elements, and for every

i\in\left\{1,2,...,m\right\}

, the set

A

does not contain

A_{i}

. Alternative formulation. Let

X

be a finite set with

n

elements and

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

be three-elements subsets of

X

, such that

|A_{i}\cap A_{j}|\leq 1

, for every

i\neq j

. Prove that there exists

A\subseteq X

with

|A|\geq \lfloor \sqrt{2n}\rfloor

, such that none of

A_{i}

's is a subset of

A

.

Back to Problems View on AoPS