Belorusija 2012

We call any 3-element subset a triple; a triple is said to be monochromatic if all its three elements are the same color. Let $f(n)$ denote the minimal possible number of the triples in a fine collection of $M_n$.

First, we have $f(5)=10=\left(\genfrac{}{}{0ex}{}{5}{3}\right)$ — the total number of triples in $M_5$. Indeed, if the collection does not contain some triple $\{a,b,c\}$, then we color $a$, $b$, $c$ black and the remaining 2 elements we color white. This coloring shows that the collection is not fine. On the other hand, the collection contains all 10 possible triples. Since for any coloring in two colors there are at least three elements, say $x,y,z$, of the same color, then the triple $\{x,y,z\}$ is monochromatic, thus the collection is fine.

Further, $f(6)=10=\frac{1}{2}\left(\genfrac{}{}{0ex}{}{6}{3}\right)$ — a half of the number of all triples in $M_6$. Note that we can divide all the triples in $M_6$ into 10 pairs of triples so that in any pair the union of both triples is $M_6$ itself. Now, if the collection contains less than 10 triples then there is a pair of triples $\{a,b,c\}$, $\{d,e,f\}$ ($\{a,b,c,d,e,f\}=M_6$) such that neither of the triples belong to the collection. If $a,b,c$ are colored black and $d,e,f$ are colored white, then there is no monochromatic triple for such coloring, hence the collection is not fine. On the other hand, the collection of 10 triples having exactly one triple from any pair is obviously fine.

Let now $n\ge 7$. We start with $M_7$, considering the following collection of triples: $\{1,2,3\}$, $\{1,4,5\}$, $\{1,6,7\}$, $\{2,4,6\}$, $\{2,5,7\}$, $\{3,4,7\}$, $\{3,5,6\}$ We can observe that any element from $M_7$ belongs to exactly three triples and any possible pair of elements is present exactly in one triple. Consider any coloring of $M_7$. There are at least 4 elements of the same color, say, black.

Consider a number $x$ of white color. Let $x$ belong to the triples $\{x,a,b\}$, $\{x,c,d\}$, $\{x,e,f\}$. Suppose that none of the triples is monochromatic (i.e., white). Then one of them, say, $\{x,e,f\}$ contains black elements $e,f$; the other two of them contain (except for $x$) one black and one white element. Let $a$ and $c$ be black, $b$ and $d$ be white. Note that if $f$ belongs to the triple $\{f,a,c\}$ then we have a monochromatic triple for this coloring. If not, then $f$, besides $\{x,e,f\}$, can belong only to the triples $\{f,a,d\}$, $\{f,b,c\}$. In this case element $e$, besides $\{x,e,f\}$, belongs to the triples $\{b,d,e\}$ and $\{a,c,e\}$. The latter is monochromatic. Thus the collection is fine. Hence $f(7)\le 7$.

Further, note that $f(n+1)\le f(n)$, because any fine collection of $M_n$ is obviously a fine collection of $M_{n+1}$ as well. It follows that $f(n)\le 7$ for any $n\ge 7$.

Let's show that $f(n)=7$ for any $n\ge 7$. Suppose, contrary to our claim, that $f(n)\le 6$ for some $n\ge 7$, and choose the minimal $n\ge 7$ satisfying the inequality. Thus there is a fine collection of $M_n$ containing $k\le 6$ triples. Then there are at most $18=3\cdot 6$ pairs of elements in the collection. Further, $n\ge 7$, so there are at least $21=\frac{7\cdot 6}{2}$ possible pairs of elements in $M_n$. Since $21>18$, there are two elements $a,b\in M_n$, such that the pair $\{a,b\}$ does not belong to any triple from the collection. We may suppose that $\{a,b\}=\{n-1,n\}$. Let's now identify the elements $a$ and $b$. Also we identify all the pairs of triples of the kind $\{a,x,y\}$, $\{b,x,y\}$, if any. The collection thus obtained is obviously fine, and it contains at most $k$ triples. But this is a fine collection for $M_{n-1}$, contrary to the minimality of $n$. Thus the proof is finished.