Problem 1816

Let $A = \{1, 2, 3, 4, 5, 6, 7\}$. Two colors are not enough because the sets in the following sequence of three-element subsets of $A$ should have alternating colors: $\{1, 2, 3\}$, $\{4, 5, 6\}$, $\{7, 1, 2\}$, $\{3, 4, 5\}$, $\{6, 7, 1\}$, $\{2, 3, 4\}$, $\{5, 6, 7\}$, $\{1, 2, 3\}$.

With three colors we can color, for example, the three-element subsets of $A$ as follows: we use
- the first color for all the subsets containing the element $7$;
- a second color for all the subsets that do not contain the element $7$ and for which the sum of their elements is even;
- a third color for all the remaining subsets.

We prove that the minimum number is $3$. Assuming that a coloring with two colors was possible, let $U$ be the set of the three-element subsets colored with the first color, and $V$ be the set of the three-element subsets colored with the second color. For every subset $X \in U$ there are $4$ subsets of $A \setminus X$ that have to be in $V$. If we represent the set of the three-element subsets as a graph in which we join two vertices (representing two three-element subsets of $A$) if they are disjoint, then every element of $U$ is joined with exactly $4$ elements of $V$, and vice-versa. It follows that the total number of edges, i.e. the numbers of pairs of disjoint three-element subsets, is $4 \cdot \text{card } U = 4 \cdot \text{card } V$, hence $\text{card } U = \text{card } V$. But then $\text{card } U \cup V$ should be even, while in fact it is $\binom{7}{3} = 35$, which is odd, contradiction.

A coloring with three colors can be found as follows: we choose two arbitrary elements $x, y \in A$. We color the three-element subsets that do not contain neither $x$ nor $y$ with the first color, those that contain $x$ but do not contain $y$ with the second color, and finally the subsets that contain $y$ with the third color.