|
|
 |
Условие
В некотором городе сеть автобусных маршрутов устроена так, что каждые два маршрута имеют ровно одну общую остановку, и на каждом маршруте есть хотя бы 4 остановки. Докажите, что все остановки можно распределить между двумя компаниями так, что на каждом маршруте найдутся остановки обеих компаний.
Решение
Рассмотрим произвольные два маршрута l1 и l2; пусть A – их общая остановка. Если остановка A находится на всех маршрутах, то можно отдать её одной компании, а все остальные остановки – другой. Пусть найдётся маршрут l3, не проходящий через остановку A, а B и C – его общие остановки с l1 и l2 соответственно. Заметим, что B ≠ C (иначе у 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, то есть принадлежащей первой компании.
