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

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

Условие

Автор: Пастор А.

В городе несколько площадей. Некоторые пары площадей соединены улицами с односторонним движением так, что с каждой площади можно выехать ровно по двум улицам. Докажите, что город можно разделить на 1014 районов так, чтобы улицами соединялись только площади из разных районов, и для каждых двух районов все соединяющие их улицы были направлены одинаково (либо все из первого района во второй, либо наоборот).


Решение

  Сначала докажем, что площади можно покрасить в 13 цветов так, чтобы ни с какой площади нельзя было попасть на площадь того же цвета, проехав менее трёх улиц. Для этого рассмотрим вспомогательный ориентированный граф: его вершинами будут площади, а ориентированными рёбрами будут соединены пары площадей, между которыми в нашем городе есть путь, проходящий не более чем по двум улицам. Легко видеть, что в этом графе из каждой вершины выходит не более 6 рёбер. Нужно доказать, что вершины этого графа можно раскрасить в 13 цветов правильным образом.
  Проведём индукцию по числу вершин. База: в случае, если вершин не больше 13, утверждение очевидно.
  Шаг индукции. Так как из каждой вершины выходит не более 6 рёбер, то существует вершина, в которую входит не более 6 рёбер. Удалив из графа эту вершину, мы получим граф, удовлетворяющий нашему условию и содержащий меньшее число вершин. По индуктивному предположению, мы можем раскрасить вершины этого графа в 13 цветов, после чего удалённую вершину мы также можем покрасить в один из цветов, так как она соединена не более чем с 12 вершинами.
  Теперь для каждого цвета разделим все площади данного цвета на 78 типов, в зависимости от того, на площади каких цветов ведут улицы, выходящие с данной площади. Поскольку других цветов 12, для каждого цвета есть 12 вариантов, в которых обе улицы ведут на площади одного цвета, и  12·11 : 2 = 66  вариантов, в которых они ведут на площади разных цветов. Итого 78 вариантов. Таким образом, мы можем разбить все площади на  78·13 = 1014  районов.
  Докажем, что полученное разбиение подходит. Пусть в районе A есть такие площади a1 и a2, а в районе B – такие площади b1 и b2, что из a1 выходит улица, ведущая на b1, а из b2 – на a2. Тогда, поскольку площади b1 и b2 принадлежат одному району, из них выходят улицы, ведущие на площади одних и тех же цветов. Это означает, что из b1 выходит улица, ведущая на площадь того же цвета, что и a2, а следовательно, того же цвета, что и a1. Таким образом, мы получили путь длины 2 между площадями одного цвета, что невозможно.

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

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

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

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