XVI-th Junior Balkan Mathematical Olympiad

Question

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? FIGURE_0

Accepted Answer

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

(2 5) = \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

(2 6) = \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).