, 2015

Consider the collection: $A_{1} = \{1,2\}$, $A_{2} = \{2,3\}$, $A_{3} = \{1,3\}$, $A_{4}, \ldots, A_{2015}$ be any 2011 subsets of $\{1,2, \ldots, 1000\}$ that contain all $1,2,3$. One can check that this collection satisfies the given condition. For any $2$-coloring of the set $\{1,2, \ldots, 1000\}$, at least one of $A_{1}, A_{2}, A_{3}$ will contain two elements of the same color. Hence, we need more than 2 colors.

Now we show that we always can color $\{1,2, \ldots, 1000\}$ by 3 colors such that the set $A_{i}$ contains at least two elements of different color for all $i$. We choose a set $A_{i_{0}}$ with least number of elements. We color one element of $A_{i_{0}}$ by red and all the rest by blue. We color by green all the elements $\{1,2, \ldots, 1000\}$ which do not belong to $A_{i_{0}}$. It is clear that $A_{i_{0}}$ contains two elements of different color. For any subset $A_{i}$ with $i \neq i_{0}$, $|A_{i} \cap A_{i_{0}}| \geq 1$ so $A_{i}$ contains at least one red or blue color element. Moreover, because $|A_{i}| \geq |A_{i_{0}}|$, either $A_{i}$ contains another element of $A_{i_{0}}$ with the other color or contains a green element. Hence, the subset $A_{i}$ contains two elements of different color.