Problem

Source: 2022 China TST, Test 1, P6

Tags: combinatorics, colorings, graph theory, Hall s marriage theorem, TST, China TST



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.