В какое минимальное количество цветов нужно раскрасить диагонали, стороны и вершины правильного 17-угольника, чтобы отрезки одного цвета не имели общих вершин и цвет каждой вершины отличался от цвета исходящих из нее отрезков?

задан 26 Окт 1:36

10|600 символов нужно символов осталось
1

Соединений из точки выходит 16, у них разные цвета. У вершины цвет отличается. Поэтому 17 цветов нужно как минимум.

Занумеруем вершины от 0 до 16. Ребро от i к j раскрасим в цвет номер i+j mod 17. Вершину i будем считать соединением от i к i; она примет цвет i+i mod 17. Для фиксированного i, все значения вида i+0, i+1, ... , i+16 по модулю 17 будут попарно различны, то есть 17 цветов хватает.

ссылка

отвечен 26 Окт 2:40

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,005

задан
26 Окт 1:36

показан
28 раз

обновлен
26 Окт 2:40

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru