|
|
 |
Условие
Можно ли покрасить 15 отрезков, изображённых на рисунке, в три цвета так, чтобы никакие два отрезка одного цвета не имели общего конца?
Решение
Пусть A, B, C, D, E – последовательные вершины внешнего пятиугольника, A', B', C', D', E' – соответствующие вершины внутренней звезды. Покажем, что каждому цвету, в который покрашена хотя бы одна сторона внешнего пятиугольника, отвечают два из образующих звезду отрезков того же цвета.
Из этого следует отрицательный ответ на вопрос задачи: если на контуре пятиугольника встречаются только два цвета, то они чередуются, что невозможно
из-за нечётности числа 5. Если же на контуре наблюдаются все три цвета, то отрезков, образующих звезду, обнаружится не менее шести – хотя бы по два отрезка каждого цвета, а их всего пять.
Итак, рассмотрим произвольную сторону внешнего пятиугольника, скажем, AB (остальные случаи отличаются переобозначениями вершин). Пусть она синяя. Тогда отрезки AA' и BB' не синие. Два отрезка звезды, исходящих из вершины A', отличаются по цвету от отрезка AA' (который не синий) и, кроме того, различны по цвету. Значит, среди них есть синий. Аналогично на звезде есть синий отрезок, с вершиной B'.
Ответ
Нельзя.
Замечания
Граф, описанный в задаче, – это знаменитый граф Петерсона.
