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

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

Условие

Дано n точек,  n > 4.  Докажите, что можно соединить их стрелками так, чтобы из каждой точки в любую другую можно было попасть, пройдя либо по одной стрелке, либо по двум (каждые две точки можно соединить стрелкой только в одном направлении; идти по стрелке можно только в указанном на ней направлении).


Решение

  Индукция по n. База. При  n = 5  требуемый граф представлен на рис. слева.
  Шаг индукции. Рассмотрим  n + 1  точку. Пусть n из них уже соединены – получился граф с n вершинами. Можно считать, что каждые две из этих n точек соединены стрелкой: иначе проведём все недостающие стрелки (направив их в любую сторону), условие тем более будет выполняться. Обозначим (n+1)-ю точку через C и рассмотрим два случая.

  1) n чётно. Разобьём n точек на пары. Пусть  {Ak, Bk}  – одна из пар  (1 ≤ k ≤ n/2)  и из Ak идёт стрелка в Bk. Тогда проведём из C стрелку в Ak и из Bk проведём стрелку в C (рис. в центре). Так проделаем для каждой пары. Новый граф с  n + 1  вершиной построен. Пусть X, Y – две любые различные его вершины.
  Если и X и Y не совпадают с C, то из X в Y можно пройти (не более чем за два «хода») по индукционному предположению.
  Пусть X или Y совпадает с C. Тогда другая из этих точек (Y или X) входит в какую-то пару из тех, на которые мы разбили первые n точек. Таким образом, X и Y – это какие-то две из трёх точек, изображенных на центральном рисунке. Глядя на этот рисунок, легко перебрать все возможные варианты и убедиться, что требование выполняется.
  2) n нечётно. Выберем любую вершину A1. Она соединена стрелками со всеми остальными вершинами: A2, ..., An. Из A1 выходят не менее чем две стрелки или в A1 входят не менее чем две стрелки (так как  n > 4).
  Пусть из A1 выходят не менее чем две стрелки (второй случай аналогичен) – в вершины A2, A3. Остальные вершины разобьем на пары. Теперь соединим стрелками новую вершину с тройкой A1, A2, A3 – как показано на рис. справа, а со всеми парами – как показано на рис. в центре. Как и в случае а), легко доказать, что полученный граф удовлетворяет условию задачи.

Замечания

При  n = 3  требуемый граф тоже существует (рис. в центре), а при  n = 4  такого графа нет (в этом легко убедиться перебором).

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

журнал
Название "Квант"
год
Год 1973
выпуск
Номер 7
Задача
Номер М211

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

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