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

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

Условие

В некотором городе сеть автобусных маршрутов устроена так, что каждые два маршрута имеют ровно одну общую остановку, и на каждом маршруте есть хотя бы 4 остановки. Докажите, что все остановки можно распределить между двумя компаниями так, что на каждом маршруте найдутся остановки обеих компаний.


Решение

   Рассмотрим произвольные два маршрута l1 и l2; пусть A – их общая остановка. Если остановка A находится на всех маршрутах, то можно отдать её одной компании, а все остальные остановки – другой.
   Пусть найдётся маршрут l3, не проходящий через остановку A, а B и C – его общие остановки с l1 и l2 соответственно. Заметим, что  BC  (иначе у l1 и l2 есть две общих остановки).
   Распределим остановки по компаниям так: все остановки остановки маршрутов l1, l2, l3, отличные от A, B и C, отдадим первой компании,
а все остальные остановки – второй компании.
   Покажем, что это распределение – требуемое. Ясно, что каждый из маршрутов l1, l2, l3 проходит через остановки обеих компаний.
   Рассмотрим любой из оставшихся маршрутов l. С каждым из маршрутов l1, l2, l3 у него лишь одна общая остановка. Значит, на l есть не более трёх остановок первой компании; поэтому там есть остановка второй. Далее, l не может проходить через две из остановок A, B, C (иначе он будет иметь две общих остановки с одним из маршрутов l1, l2, l3). Пусть для определённости l не проходит через B и C. Тогда l пересекается с l3 по некоторой остановке X, отличной от B и C, то есть принадлежащей первой компании.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2011-2012
Этап
Вариант 5
класс
Класс 9
Задача
Номер 9.8

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

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