Problem

Source: 2012 Belarus TST 4.3

Tags: combinatorics, Subsets, Coloring



Define $M_n = \{1,2,...,n\}$, for any $n\in N$. A collection of $3$-element subsets of $M_n$ is said to be fine if for any coloring of elements of $M_n$ in two colors there is a subset of the collection all three elements of which are of the same color. For any $n\ge 5$ find the minimal possible number of the $3$-element subsets of $M_n$ in the fine collection. (E. Barabanov, S. Mazanik, I. Voronovich)