China National Team Selection Test

We give three solutions as follows.

Solution 1

Construct a bipartite graph $G$ whose two parts are $X = \{A_1, A_2, \dots, A_m\}$ and $Y = A$: for $1 \le i \le m$ and $a \in A$, $A_i \in X$ and $a \in Y$ are adjacent if and only if $a \in A_i$. Since for each nonempty $I \subseteq \{1, 2, \dots, m\}$, $|\bigcup_{i \in I} A_i| \ge |I| + 1$, it follows that for any $k$ vertices of $X$, the number of vertices of $Y$ that are neighbouring to one or more of them, is at least $k+1$. According to Hall's theorem, there exists a transversal $f$ from $X$ to $Y$. For $1 \le i \le m$, let $a_i = f(A_i)$. Clearly, $a_i \in A_i$, and $a_1, a_2, \dots, a_m$ are distinct elements of $A$. Colour all the other elements $A \setminus \{a_1, \dots, a_m\}$ white, and determine the colours of $a_1, a_2, \dots, a_m$ as follows.

Every time, choose an $i$ such that $a_i$ is uncoloured and $A_i$ has a coloured neighbour, say $b$. Colour $a_i$ the opposite colour to $b$. Suppose, during the process, some elements say $a_1, a_2, \dots, a_k$ ($1 \le k \le m$) are uncoloured, but we cannot find another $i$ and colour $a_i$. Based on the algorithm, this means that all the neighbours of $A_1, A_2, \dots, A_k$ are in $\{a_1, \dots, a_k\}$, yet it contradicts $|A_1 \cup A_2 \cup \dots \cup A_k| \ge k + 1$. Hence, this process can continue until all of $a_1, a_2, \dots, a_m$ are coloured. Moreover, for $1 \le i \le m$, when $a_i$ is coloured, $A_i$ is guaranteed to have black and white neighbours, that is, $A_i$ contains both black and white elements. This colouring satisfies the problem requirements. $\square$

Solution 2

We begin with a lemma.

Lemma The finite sets $A_1, A_2, \dots, A_m$ are called "nice", if the union of any $k \le m$ ($k$ is arbitrary) of them contains at least $k+1$ elements. If $A_1, A_2, \dots, A_m$ are nice, then there exist 2-element sets $B_1, B_2, \dots, B_m$, such that $B_i \subseteq A_i$, $i = 1, 2, \dots, m$, and $B_1, B_2, \dots, B_m$ are nice.

Proof of lemma Assume the lemma is untrue. Let $A_1, A_2, \dots, A_m$ be a counterexample with the smallest $m$ value and the smallest $|A_1| + |A_2| + \dots + |A_m|$ for such $m$. There are three situations.

Case 1, if the union of any $k \le m$ ($k$ is arbitrary) sets does not contain exactly $k+1$ elements. Take $k=1$, and apparently every set contains 3 or more elements. Choose an arbitrary set and remove any element from it. The sets are still nice (as a counterexample), yet $|A_1| + |A_2| + \dots + |A_m|$ is smaller. A contradiction.

Case 2, if the union of some $k \le m-1$ sets contains exactly $k+1$ elements. Assume $|A_1 \cup A_2 \cup \dots \cup A_k| = k+1$. Since $k<m$, there exist 2-element sets $B_1, B_2, \dots, B_k$ such that $B_i \subseteq A_i$, $i=1, 2, \dots, k$, and $B_1, B_2, \dots, B_k$ are nice.

Let $C_i := A_i \setminus (A_1 \cup A_2 \cup \dots \cup A_k)$, $i = k+1, \dots, m$. It is easy to see that, among $C_{k+1}, C_{k+2}, \dots, C_m$, the union of any $d$ ($1 \le d \le m-k$, $d$ is arbitrary) sets contains $d$ or more elements. By Hall's theorem, there exist $x_i \in C_i$ ($i = k+1, \dots, m$), such that $x_{k+1}, x_{k+2}, \dots, x_m$ are all distinct. We construct $B_{k+1}, B_{k+2}, \dots, B_m$ in the following way: if for some $i \in \{k+1, k+2, \dots, m\}$, $B_i$ has not been made yet, but $A_i$ contains an element $y_i$ that belongs to some $B$ set already constructed, then let $B_i = \{x_i, y_i\}$. Clearly, $x_i$ is a new element in the constructed $B$ sets, hence these $B$ sets are still nice. Suppose, after the construction of several $B_i$'s, no more set can be constructed in the above way. Then the remaining $A$ sets do not contain any element in the constructed $B_i$'s. Since $m$ is minimal, we may construct $B_j$'s from those $A$ sets such that they are nice. Furthermore, $B_j$'s and $B_i$'s are disjoint, when combined, $B_1, B_2, \dots, B_m$ are nice. So, case 2 is not possible.

Case 3, if the union of any $k$ ($1 \le k \le m-1$, $k$ is arbitrary) sets contains $k+2$ or more elements, while the union of all $m$ sets contains exactly $m+1$ elements. Observe that any $m-1$ sets have the same union as that of all $m$ sets. Hence, every element must belong to at least 2 sets. Meanwhile, each set contains at least 3 elements. Choose any set and remove any element from it. The sets are still nice, but they have a smaller $|A_1| + |A_2| + \dots + |A_m|$, contradiction.

This verifies the lemma.

Return to the original problem. According to the lemma, we may find 2-element subsets $B_1, B_2, \dots, B_m$ of $A_1, A_2, \dots, A_m$, respectively, such that the union of any $k$ of them has $k+1$ or more elements. Treat every element of $A$ as a vertex, and then for every $1 \le i \le m$, connect the two elements in $B_i$ by an edge. Note that this graph has no cycle (otherwise, the edges in a cycle correspond to $B$ sets the number of which is the same as the number of elements in their union), and thus it is a forest, which is a bipartite graph. Colour all elements in one part black, and all elements in the other part white. This colouring satisfies the problem condition. $\square$

Solution 3

Use induction on the number of sets $m$. When $m = 1$, $|A_1| \ge 2$, choose two elements of $A_1$ and colour one black and one white. Suppose the conclusion holds for all $m \le n-1$. Consider $m = n$.

Case 1. If for any $I \subseteq \{1, \dots, n\}$, $|\cup_{i \in I} A_i| \ge |I| + 2$. Take $a \in A_n$. By the induction hypothesis, there is a colouring of $A_1 \setminus \{a\}, A_2 \setminus \{a\}, \dots, A_{n-1} \setminus \{a\}$ for which each $A_i \setminus \{a\}$ contains black and white elements. As $A_n \setminus \{a\}$ has been coloured, we can colour $a$ such that $A_n$ has elements of both colours.

Case 2. If for some $I \ne \{1, 2, \dots, n\}$, $|\cup_{i \in I} A_i| = |I| + 1$. Let $I$ be the largest, $J = \{1, 2, \dots, n\} \setminus I$, and $B = \cup_{i \in I} A_i$, $C = \cup_{j \in J} A_j$.

Case 2a. If $B \cap C = \emptyset$, then colour $B$ and $C$ separately. By induction, there is a colouring that guarantees each $A_i$ contains black and white elements.

Case 2b. If $B \cap C \ne \emptyset$, take $b \in B \cap C$, and define $A'_j = A_j \setminus (B \setminus \{b\})$ ($j \in J$). For any $T \subseteq J$, since $I$ is the largest, it follows that
$$\left| \bigcup_{t \in T} A'_t \right| \ge \left| \bigcup_{t \in I \cup T} A_t \right| - \left| \bigcup_{i \in I} A_i \right| \ge (|I \cup T| + 2) - (|I| + 1) = |T| + 1.$$
Similarly,
$$\left| \bigcup_{j \in J} A'_j \right| = \left| \bigcup_{i=1} A_i \right| - |B \setminus \{b\}| \ge n + 1 - |I| = |J| + 1.$$
By induction, we may colour $C \setminus (B \setminus \{b\}) = \cup_{j \in J} A'_j$ and $B = \cup_{i \in I} A_i$ such that $A'_j(j \in J)$ and $A_i(i \in I)$ contain elements of both colours. If $b$ has different colours in the two colourings, then reverse the colouring of $B$. Now they are compatible and give a colouring of $A$ which meets the problem requirements. $\square$