ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109490
Темы:    [ Раскраски ]
[ Четность и нечетность ]
[ Теория графов (прочее) ]
[ Пятиугольники ]
Сложность: 4-
Классы: 7,8,9,10
В корзину
Прислать комментарий

Условие

Можно ли покрасить 15 отрезков, изображённых на рисунке, в три цвета так, чтобы никакие два отрезка одного цвета не имели общего конца?


Решение

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


Ответ

Нельзя.

Замечания

Граф, описанный в задаче, – это знаменитый граф Петерсона.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 70
Год 2007
вариант
Класс 10
задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .