MathDB

Let

n\ge 5

be an integer. Consider

2n-1

subsets

A_1, A_2, A_3, \ldots , A_{2n-1}

of the set

\{ 1, 2, 3,\ldots , n \}

, these subsets have the property that each of them has

2

elements (that is that is, for

1 \le i \le 2n-1

it is true that

A_i

has

2

elements). Show that it is always possible to select

n

of these subsets in such a way that the union of these

n

subsets has at most

\frac{2}{3}n + 1

elements in total.

Problem Statement