Задача
В городе 57 автобусных маршрутов. Известно, что:
1) с каждой остановки на любую другую остановку можно попасть без пересадки;
2) для каждой пары маршрутов найдётся, и притом только одна, остановка, на которой можно пересесть с одного из этих маршрутов на другой;
3) на каждом маршруте не менее трёх остановок.
Сколько остановок имеет каждый из 57 маршрутов?
Решение
Пусть на каком-то маршруте a ровно n остановок. Возьмём остановку B, через которую a не проходит. Из B есть маршрут в каждую из n остановок маршрута a, причём такой маршрут ровно один, поскольку два разных маршрута не могут иметь двух общих остановок. Каждый маршрут, проходящий через B, пересекает маршрут a. Поэтому через B проходит ровно n маршрутов.
Теперь ясно, что любой маршрут b, не проходящий через остановку B, имеет ровно n остановок. Действительно, как и выше, число остановок на нём равно числу маршрутов, проходящих через B. Рассмотрим произвольную точку A маршрута a, возьмём на маршруте AB остановку C, отличную от A и B, и проведём через неё маршрут c, отличный от AB. Маршрут c не проходит через B, следовательно, на нём n остановок. Остановка A не лежит на c, поэтому, как показано выше, через A проходит n маршрутов (включая a). То же верно для каждой точки маршрута a.
  Значит, через точки маршрута a проходит всего n(n – 1) маршрутов, отличных от a, и ещё сам маршрут a. А это – все маршруты города.
Решая уравнение n(n – 1) + 1 = 57, находим, что n = 8.
Ответ
8 остановок.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь