|
|
 |
Условие
Сеть автобусных маршрутов в пригороде Амстердама устроена так, что:
а) на каждом маршруте есть ровно три остановки;
б) каждые два маршрута либо вовсе не имеют общих остановок, либо имеют только одну общую остановку.
Какое наибольшее количество маршрутов может быть в этом пригороде, если в нём всего 9 остановок?
Решение
Оценка. Рассмотрим какую-нибудь остановку A. Определим наибольшее количество маршрутов, проходящих через неё. Кроме A, в городе еще 8 остановок. На каждом маршруте, проходящем через A, есть ещё две остановки. Так как никакие два из этих маршрутов не могут иметь общих остановок, отличных от A, то всего через A может проходить не более, чем 8 : 2 = 4 маршрута. Занумеруем все остановки и обозначим через a1 количество маршрутов, проходящих через первую остановку, через a2 количество маршрутов, проходящих через вторую остановку, ..., через a9 количество маршрутов, проходящих через девятую остановку. Так как на каждом маршруте ровно 3 остановки, то
a1 + ... + a9 = 3n, где n – общее количество маршрутов. По доказанному выше, каждое слагаемое не больше четырёх. Следовательно, 3n < 4·9 = 36, то есть n < 12.
Пример. На рисунке изображена схема, удовлетворяющая условию задачи и содержащая 12 маршрутов.
Ответ
12 маршрутов.
Замечания
1. Ср. с задачами 76531, 76535.
2. Для знатоков. Известно, что каждая точка плоскости задаётся своими координатами (x, y), а прямые на ней задаются уравнениями вида ax + by + c = 0. Заменим теперь все действительные числа на остатки по модулю p: будем называть Fp-плоскостью множество пар (x, y) остатков по модулю p, а прямыми на ней будем называть множества решений сравнения ax + by + c = 0. Для такой конечной плоскости выполнены многие аксиомы обычной геометрии – в частности, условие б) задачи (первый постулат Евклида).
2. Нетрудно подсчитать, что на Fp-плоскости имеется p2 точек и p(p + 1) прямая, каждая из которых состоит из p точек. При p = 3 такая плоскость и дает пример, приведённый в конце решения.
