Математикадан жасөспірімдер арасындағы 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)$, что можно сделать перебором.