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

Проект МЦНМО
при участии
школы 57
Задача 65619
Темы:    [ Раскраски ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Какое наименьшее количество цветов необходимо, чтобы покрасить все вершины, стороны и диагонали выпуклого n-угольника, если должны выполняться два условия:
  1) каждые два отрезка, выходящие из одной вершины должны быть разного цвета;
  2) цвет любой вершины должен отличаться от цвета любого отрезка, выходящего из неё?


Решение

  Так как из каждой вершины выходит  n – 1  отрезок и они все должны быть покрашены различными цветами, отличными от цвета этой вершины, то количество цветов должно быть не меньше чем n.
  Докажем, что n цветов достаточно. Обозначим вершины через V0, V1, ..., Vn–1, цвета – числами  0, 1, ..., n – 1.  Произведём раскраску следующим образом: отрезок ViVj окрашивается цветом с номером  i + j (mod n),  а вершина Vi – цветом с номером  2i (mod n). 
  Несложно проверить, что такая окраска удовлетворяет условиям задачи.


Ответ

n цветов.

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

олимпиада
Название Московская математическая регата
год
Год 2015/16
класс
Класс 10
задача
Номер 10.4.3

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

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