16-я Балканская математическая олимпиада среди юниоров Верия, Греция, 2012 год

На доске вбито $n$ гвоздей, каждые два из которых соединены веревкой. Каждая веревка окрашена в один из $n$ цветов. Для каждых трёх различных цветов есть три гвоздя, соединенных веревками этих цветов.
а) Может ли $n$ быть равно 6?
б) Может ли $n$ быть равно 7?

Комментарий/решение

а) нет.

Заметим, что поскольку количество треугольников с вершинами в гвоздях и количество троек цветов равны по $C_n^3$, из условия следует, что все треугольники по тройкам цветов различны, и нет треугольника, в котором два цвета равны.

Рассмотрим количество треугольников сторона которых цвета $1$. С одной стороны оно равно $C_{n-1}^2$. С другой, если рассмотреть каждую верёвку цвета $1$ по отдельности она образует ровно $n-2$ треугольника, поэтому $n-2|C_{n-1}^2$

При $n=6:$ $4|C_5^2=\frac{5\cdot4}2=10$ - противоречие.

б) Да. Пусть $A_1,A_2,...,A_7$ - данные гвозди. Раскрасим $A_iA_{i+1}$ в различные цвета, также $A_{i-1}A_{i+2}, A_{i-2}A_{i+3}$ раскрасим в тот же цвет, что и $A_iA_{i+1}$. Таким образом мы раскрасили все веревки. Из симметрии достаточно доказать, что можно найти треугольник с цветами $(1,i,j)$, что можно сделать перебором.