Question 82
Given 2015 subsets $A_{1}, A_{2}, \ldots, A_{2015}$ of the set $\{1,2, \ldots, 1000\}$ such that $|A_{i}| \geq 2$ for every $i \geq 1$ and $|A_{i} \cap A_{j}| \geq 1$ for every $1 \leq i \lt j \leq 2015$. Prove that $k=3$ is the smallest number of colors such that we can always color the elements of the set $\{1,2, \ldots, 1000\}$ by $k$ colors with the property that the subset $A_{i}$ has at least two elements of different colors for every $i \geq 1$.