MathDB

Colorful subsets

Source: 2022 China TST, Test 1, P6

March 24, 2022

combinatoricscoloringsgraph theoryHall s marriage theoremTSTChina TST

Problem Statement

Let

m

be a positive integer, and

A_1, A_2, \ldots, A_m

(not necessarily different) be

m

subsets of a finite set

A

. It is known that for any nonempty subset

I

of

\{1, 2 \ldots, m \}

,

\Big| \bigcup_{i \in I} A_i \Big| \ge |I|+1.

Show that the elements of

A

can be colored black and white, so that each of

A_1,A_2,\ldots,A_m

contains both black and white elements.

Back to Problems View on AoPS