An application of Hall's theorem. We use a natural interpretation of the relation "set - element" as a bipartite graph. So, we have a bipartite graph $ G(S, P)$ with the vertices in $ S=\{s_1,s_2,\dots,s_m\}$ (sets) and $ P$ (points). A vertex $ s\in S$ is connected to $ p\in P$ if $ p\in s$. Note that the given condition is a bit stronger than the Hall's condition. the idea is to construct a matching (injection) $ M: S\to P$, then remove a point from $ P$ and construct another matching $ M':S\to P.$ By Hall's marriage theorem both objects exist. Assume for a moment, $ M(S)\cap M'(S)=\emptyset$. In this case we can color $ M(S)$ in white and $ M'(S)$ in black and we are done. In real life, $ M(S)$ and $ M'(S)$ are intertwined and more attention is needed, but that's the basic idea. More details can be found in my blog.

Here is an informal and more intuitive version of the solution for better understanding.

CANBANKAN wrote:

What if $X=S$?

math90 wrote: What if $X=S$? CANBANKAN wrote: The only other possibility is that for every $X\subset S$, $|N(X)| \ge |X|+2$, which means we can remove at least one edge such that the graph still works.

Let me explain in more details. I found an easy way to fix the hole. CANBANKAN wrote: If there is a set $X\subseteq S, X\ne \emptyset$ with $|N(X)|=|X|+1$ This works only if you assume in addition that $X\ne S$. Otherwise you can't use induction hypothesis. CANBANKAN wrote: The only other possibility is that for every $X\subset S$, $|N(X)| \ge |X|+2$, which means we can remove at least one edge such that the graph still works. This works if $|S|\ge 2$ and you again assume that $X\ne\emptyset$ and $X\ne S$. Verification requires some details, but it is easy. To complete the proof you also need to prove the claim in the case $|S|=1$, but it is easy. Anyway, my comments are less important than finding the main claim, so congrats.

I see. I considered what happened with all $X\subseteq S$ not working, but I didn't consider this a hole because it is so easy. Maybe my use of minimality made me forget about base cases. In the future, I will be more careful with the base cases.

My solution (it seems a bit too simple, but I think it works): We do induction over $m$ where the base case $m=1$ is trivial. In the induction step, we can use that we can already colour any subfamily of the $A_i$. Now start by choosing any element $x$ of one of the $A_i$ and colouring it black. Now by Hall's Marriage Theorem, we can find distinct $x_i \in A_i$ which are also distinct from $x$. Now for all the $A_i$ containing $x$, colour $x_i$ white. Now for all the $A_i$ with $x_i$ not yet coloured but containing a coloured element, colour $x_i$ black. Now for all the $A_i$ with $x_i$ not yet coloured but containing a coloured element, colour $x_i$ white. Iterate until the process stops. (Since we only ever colour elements $x_i$ and they are distinct, there can be no conflict.) All the sets containing coloured elements already have both colours by construction. The remaining sets have no coloured elements and hence can be dealt with by the induction hypothesis. Done!

Tintarn wrote: My solution (it seems a bit too simple, but I think it works):

Yes, it is correct. Here is a solution, which is a simplified version of both your solution and my solution (post #4). By Hall's marriage theorem, we can find distinct elements $x_i \in A_i$. The main claim is as follows. Claim. Given distinct $x_i\in A_i$, any coloring of $A\setminus\{x_1,\ldots,x_m\}$ in black and white can be extended to a coloring of $A$ such that each $A_i$ contains elements of both colors. Proof. By induction on $m$. The base case is true since $|A_1|\ge 2$. So now assume $m\ge 2$. In the induction step, since $\left|\bigcup_{i=1}^m A_i\right|\ge m+1$, there exist $i_0\in[m]$ and $y\in A_{i_0}$ different from $x_1,\ldots,x_m$. Without loss of generality assume $i_0=1$. Now color $x_1$ with the color not presented in $y$. So now $A_1$ contains elements of both colors and only $x_2,x_3,\ldots,x_m$ have not been colored yet. By induction hypothesis we can color $x_2,x_3,\ldots,x_m$ such that $A_2,A_3,\ldots,A_m$ all contain elements of both colors. This coloring of $A$ satisfies the induction step. $\square$ Now choose any initial coloring of $A\setminus\{x_1,\ldots,x_m\}$, for instance all black, and use the claim.

Yeah basically the same as above. In view of the condition choose a system of distinct representatives $(x_1,x_2,x_3,...,x_n)$ of $A_1,A_2,...,A_n$. Since the union of all $A_i$ is at least $n+1$ there is a remaining subset of elements $Y$ which is to be painted white. Now construct a directed graph whose : Vertex set is labelled $A_1,A_2,...,A_n$ and $Y$ There is a directed edge $A_i\to A_j$ iff $A_i$ contains the representative of $A_j$ , $x_j\in A_i$ and a directed edge $A_i\to Y$ iff $A_i\cap Y\neq\emptyset $ For any subset of indices $I\subseteq \{1,2,...,n\}$ we have that $\bigcup_{i\in I}A_i $ contains at least $|I|+1$ elements therefore at least one element from $Y\cup \{x_1,x_2,...,x_n\} \backslash \bigcup_{i\in I} A_i$ and this shows that in our directed graph for every subset of vertices from $A_1,...,A_n$ the edge cut contains an outward directed edge. This ofc shows that $Y$ can be reached from any $A_i$ by means of a directed path. Now color the representative of $A_i$ ,$x_i$ , black or white according to the distance of $A_i$ to $Y$ (minimum directed path , black if odd and white if even) and say $A_i$ itself is colored black or white . For every $A_i$ there is a minimal path $(i_1=i)$, $A_{i_1}\to A_{i_2}\to ...\to A_{i_k}\to Y$ , the next vertex in this path (it can be $Y$ which is white ) has different color but this means that $A_i$ contains another representative $x_{i_2}$ or some $y\in Y$ that has different color from $x_i$ therefore we are done.

Let $S = \{s_1, s_2, \dots, s_m \}$ be the "set-vertices", i.e., each $s_i \in S$ represents $A_i$, and let $P$ be the "element-vertices", i.e., each $p_i \in A$. Connect an edge from an element of $S$ to $P$ if $p \in A_i = s_i$. We then have that for all $S' \subseteq S, |N(S')| \geq |S'| + 1 > |S'|$, so by Hall's lemma we have a matching. Assume without loss of generality the matching is $s_i \rightarrow p_i$, for all $1 \leq i \leq m$. The main idea for the construction of the coloring is to observe that if we remove a an element $p_i$ from $P$, we still have a matching for $S$ by Hall's lemma. Remove the vertex $p_1$ from $P$. We still obtain from the problem that for all $S' \subseteq S, |N(S')| \geq |S'|$. Therefore a matching still exists and in particular we may still pair each $s_2, s_3, \dots, s_m$ with $p_2, p_3, \dots, p_m$ respectively, and a new element $q_1 \neq p_1$ with $s_1$. Now as $\{p_1, q_1 \} \in s_1$ we may color $\{p_1, q_1 \}$ as black and white respectively. Now continuing on in the identical fashion, we obtain that $\{p_2, q_2 \} \in s_2, \dots, \{q_m, p_m \} \in s_m$. We now adopt the coloring $p_i$ as black, and therefore $q_i$ as white. If we now have some strange thought such as "what if the $q_i$ aren't distinct?" This still does not affect our construction, and so we are done. $\blacksquare$

Here's a solution with linear algebra. We apply induction on $m$. The case $m=1$ is trivial, as $|A_1|\geq 2$. We can suppose that every element of $A$ is contained in some $A_i$. We assign each element $a\in A$ a real variable $x_a$. Consider the system of equations in which, for each $A_i$, the sum of the variables associated to elements of $A_i$ is zero. This is a linear system of $m$ equations, and by the condition in the statement we have $|A|\geq m+1$, which means that the system has a nontrivial solution. Color the elements $a\in A$ with $x_a>0$ in black, the elements with $x_a<0$ in white, and the elements with $x_a=0$ uncolored (for now). Since the sum of the variables corresponding to each set $A_i$ is zero, either all elements of $A_i$ are uncolored or $A_i$ contains elements of both colors. Moreover, at least one set $A_i$ contains some colored element. Consider the family $\mathcal{F}\subseteq\{A_1, A_2, \dots, A_m\}$ of subsets where all elements are uncolored. Since $|\mathcal{F}|<m$, we can apply induction to $\mathcal{F}$ (if $|\mathcal{F}|>0$) to color its elements. This ensures that every set $A_i$ contains both black and white elements. Color arbitrarily any element of $A$ that is still uncolored at this point, and we are done.

Well, China is too good at giving difficult 2/5s and easy 3/6s... Consider a bipartite graph $ G=(X,A;E), X:=\{A_1,\dots,A_m \}$. For $A_k\in X, a\in A, A_k a\in E$ if and only if $a\in A_k$. We know that for any $k$ vertices in $X$, they have at least $k+1$ neighbors in $A$. By Hall's marriage theorem, we can find $m$ vertices $v_1,\dots v_m$ in $A$, such $A_kv_k\in E$ for $1\leq k\leq m$. Let us call the vertices in $A$ other than $v_1,\dots v_m$, say $v_0,v_{-1}\dots$. We claim that we can rearrange the index on $A_1,\dots A_m$ such that for every $k$, there exists an index $j<k$, such that $A_kv_j\in E$. Use some induction and the claim above is almost trivial. ( But the important thing is that the claim actually helps us find a clear and simple subgraph of $G$ that also satisfies the original statement.) Hence now we just have to color the vertices in $A$ in the following way: first color $v_0,v_{-1}\dots $ black, then we just color $v_k$ based on the color that $A_k$ need ($A_k$ only need at most one more color, because it is connected to some $v_{<k}$). And then we are done!!!