Track / Stage 6 / 84 of 400 #1564 of 2444

Problem 1564

National Olympiad, first round

Combinatorics Difficulty 6.1 Prove it XVI-th Junior Balkan Mathematical Olympiad · North Macedonia

On a board there are $n$ nails each two connected by a string. Each string is colored in one of $n$ given distinct colors. For each three distinct colors, there exist three nails connected with strings in these three colors. Can $n$ be
a) $6$ ?
b) $7$ ?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

a. The answer is no.

Suppose it is possible. Consider some color, say blue. Each blue string is the side of $4$ triangles formed with vertices on the given points. As there exist $\binom{5}{2} = \frac{5 \cdot 4}{2} = 10$ pairs of colors other than blue, and for any such pair of colors together with the blue color there exists a triangle with strings in these colors, we conclude at least $3$ blue strings (otherwise the number of triangles with a blue string as a side would be at most $2 \cdot 4 = 8$ , a contradiction). The same is true for any color, so altogether there exist at least $6 \cdot 3 = 18$ strings, while we have just $\binom{6}{2} = \frac{6 \cdot 5}{2} = 15$ of them.

b. The answer is yes.

Put the nails at the vertices of a regular $7$ -gon and color each one of its sides in a different color. Now color each diagonal in the color of the unique side parallel to it. It can be checked directly that each triple of colors appears in some triangle (because of symmetry, it is enough to check only the triples containing the first color).

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.