Problem 854

5. For $n=4$, we color the sides in one color, for example, blue, and the diagonals in another - red. It is then obvious that there does not exist a triangle whose vertices are the vertices of this quadrilateral, and all sides are colored in the same color.

!

For $n=5$, we color the sides in one color, for example, blue, and the diagonals in another - red. It is then obvious that there does not exist a triangle whose vertices are the vertices of this pentagon, and all sides are colored in the same color.

This proves that the desired $n>5$.

!

Now, let's prove that for any hexagon, no matter how we color each of the sides and diagonals of a regular hexagon in blue or red, there must exist at least one triangle whose vertices are also vertices of the hexagon and whose sides are all colored in the same color.

Consider one vertex of the hexagon, let's call it A. From it, there are five connections to other vertices, which are colored either blue or red.

Since $5=2 \cdot 2+1$, by the Dirichlet principle, there exists a color such that at least three of these connections are colored in that color. For example, let's say it is red.

!

Label the vertices that determine these connections with vertex $A$ as $B, C$, and $D$, so the red connections are $\overline{A B}, \overline{A C}$, and $\overline{A D}$.

If at least one of the connections $\overline{B C}, \overline{B D}$, or $\overline{C D}$ is colored red, we have a monochromatic (red) triangle.

If not, then the triangle $\triangle B C D$ is monochromatic (blue).

Note: If a student does not consider the case $n=4$ but does consider the case $n=5$ and shows that it is possible to color the pentagon such that no triangle has monochromatic sides, they do not lose points.