Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

  6
2 года 2 месяца назад #

а) нет.

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

Рассмотрим количество треугольников сторона которых цвета 1. С одной стороны оно равно C2n1. С другой, если рассмотреть каждую верёвку цвета 1 по отдельности она образует ровно n2 треугольника, поэтому n2|C2n1

При n=6: 4|C25=542=10 - противоречие.

б) Да. Пусть A1,A2,...,A7 - данные гвозди. Раскрасим AiAi+1 в различные цвета, также Ai1Ai+2,Ai2Ai+3 раскрасим в тот же цвет, что и AiAi+1. Таким образом мы раскрасили все веревки. Из симметрии достаточно доказать, что можно найти треугольник с цветами (1,i,j), что можно сделать перебором.