Задача 77917

Темы:    [ Теория графов (прочее) ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3+ Классы: 9,10,11

Условие

Можно ли провести в городе 10 автобусных маршрутов и установить на них остановки так, что какие бы 8 маршрутов ни были взяты, найдётся остановка, не лежащая ни на одном из них, а любые 9 маршрутов проходят через все остановки.

Решение

Проведём 10 попарно пересекающихся (в различных точках) прямых. Пусть маршруты проходят по этим прямым, а остановками служат точки пересечения прямых. Любые девять маршрутов проходят через все остановки, поскольку через каждую остановку, лежащую на оставшейся прямой, проходит одна из девяти прямых, соответствующих этим маршрутам. Любые восемь маршрутов не проходят через остановку, которая является точкой пересечения двух остальных маршрутов.

Ответ

Можно.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	13
Год	1950
вариант
Класс	9,10
Тур	2
задача
Номер	4