Решение задачи 140

Решение:

Рассмотрим произвольную остановку А:

Заметим, что остановка А может быть частью не более четырёх маршрутов. Действительно, в каждом маршруте помимо А есть ещё две остановки. При этом любая остановка X не может участвовать в двух маршрутах (т.к. в этом случае маршруты будут пересекаться по двум остановкам: А и Х). Помимо А есть ещё 8 остановок, поэтому максимальное число маршрутов с А не больше 8/2=4.

Обозначим за a1 число маршрутов, с участием первой остановки, а2 - второй,..., a9 - девятой. Предположим, что всего есть n маршрутов. Тогда с одной стороны: а1+...+а9 = 3n (в каждом маршруте участвуют ровно 3 остановки), а с другой стороны, как мы показали ранее, через каждую остановку проходит не более четырёх маршрутов. Поэтому: а1+...+а9 <= 4*9=36. Поэтому 3n <=36, откуда n <= 12.

Теперь приведем пример 12-ти маршрутов (разные маршруты обозначены разными цветами):