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

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

Условие

Сеть метро имеет на каждой линии не менее 4 станций, из них не более трёх пересадочных. Ни на какой пересадочной станции не скрещиваются более двух линий. Какое наибольшее число линий может иметь такая сеть, если с каждой станции на любую другую можно попасть, сделав не больше двух пересадок?


Решение

Зафиксируем какую-нибудь линию. На ней есть неперсадочная станция. С нее, сделав одну пересадку, можно попасть не более, чем на 3 линии, а с каждой из них, сделав еще одну пересадку, – ещё не более, чем на две линии. Следовательно, всего линий не более чем  1 + 3 + 2·3 = 10.  На рисунке показана схема пересадок для десяти линий, удовлетворяющая условию (для удобства беспересадочные станции не отмечены; "пересечения", не отмеченные кружочками, станциями не являются).


Ответ

10 линий.

Замечания

В условии не требуется, чтобы линии были прямымм. Поэтому, вообще говоря, достаточно привести список из 15 пересадочных станций и 10 линий. Вот пример такого списка: станции A, B, ..., O; линии {A, B, C},  {A, D, E},  {B, F, G},  {C, H, I},  {D, J, K},  {E, L, M},  {F, L, N},  {G, J, O},  {H, K, N},  {I, M, O}. Также можно привести граф с 10 вершинами степени 3, вершины которого соответствуют линиям, а рёбра – пересадочным станциям. Но при отсутствии явной симметрии проверка соответствия примера условиям становится трудоемкой.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 29
Год 1966
вариант
1
Класс 8
Тур 2
задача
Номер 4

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

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