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

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

Условие

Каждое из рёбер полного графа с 18 вершинами покрашено в один из двух цветов.
Докажите, что есть четыре вершины, все рёбра между которыми – одного цвета.


Решение

Из произвольной вершины выходит по крайней мере 9 рёбер одного цвета (пусть красного). Рассмотрим полный граф на 9 вершинах, в которые ведут эти рёбра, и применим к нему результат задачи 30817.

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

книга
Автор Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания 1994
Название Ленинградские математические кружки
Издательство Киров: "АСА"
Издание 1
глава
Номер 13
Название Графы-2
Тема Теория графов
задача
Номер 040
книга
Автор Иванов С.В.
Название Математический кружок
глава
Номер 5
Название Графы
Тема Теория графов
задача
Номер 37

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

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