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

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

Условие

В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на  N + 2  республики так, чтобы никакие два города из одной республики не были соединены дорогой.


Решение

  Рассмотрим граф с вершинами в городах, рёбра которого соответствуют дорогам. Из условия следует, что в этом графе через каждую вершину проходит не более N нечётных циклов.
  Докажем индукцией по количеству вершин, что вершины такого графа можно покрасить в  N + 2  цвета так, чтобы никакие две вершины одного цвета не были соединены ребром.
  База для графа из одной вершины очевидна.
  Шаг индукции. Пусть утверждение верно для графа, в котором менее k вершин. Рассмотрим граф G с k вершинами, в котором через каждую вершину проходит не более N нечётных циклов. Удалив из этого графа любую вершину A и все выходящие из неё рёбра, мы получим граф H с  k – 1  вершиной. Очевидно, через каждую вершину графа H проходит не более N циклов нечётной длины. Тогда покрасим вершины графа H в  N + 2  цвета таким образом, чтобы никакие две вершины одного цвета не были соединены ребром (это можно сделать по индуктивному предположению).
  Для цвета k  (2 ≤ k ≤ N + 2)  рассмотрим граф H1k из всех вершин графа H, покрашенных в цвета 1 и k, и всех проведённых между ними рёбер графа G. Поскольку никакие две вершины одинакового цвета в графе H1k не соединены ребром, то в этом графе нет циклов нечётной длины. Построим граф G1k, добавив к графу H1k вершину A и все выходящие из неё к вершинам H1k рёбра.
  Если для некоторого k в графе G1k через вершину A не проходит ни один цикл нечётной длины, то циклов нечётной длины в этом графе нет. В этом случае несложно доказать (см. лемму к задаче 110038), что мы можем так перекрасить вершины графа G1k (используя лишь цвета 1 и k), что все рёбра в этом графе будут соединять пары вершин разных цветов. Так как все остальные вершины графа G покрашены в цвета, отличные от 1 и k, то и во всём графе G никакие две вершины одинакового цвета не соединены ребром.
  Остаётся рассмотреть случай, когда для каждого k  (2 ≤ k ≤ N + 2)  в графе G1k через вершину A проходит хотя бы один цикл нечётной длины.
  Заметим, что такой нечётный цикл проходит только по вершинам цветов 1 и k, причём среди них есть хотя бы одна вершина цвета k. Следовательно, через вершину A проходит хотя бы  N + 1  цикл нечётной длины, что противоречит условию. Следовательно, этот случай невозможен, и требуемая раскраска получена.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2000
Этап
Вариант 4
Класс
Класс 11
задача
Номер 00.4.11.8

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

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