ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 76535
Темы:    [ Комбинаторная геометрия (прочее) ]
[ Классическая комбинаторика (прочее) ]
[ Проективная плоскость с конечным числом точек ]
Сложность: 4-
Классы: 10,11
В корзину
Прислать комментарий

Условие

В городе 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 остановок.

Замечания

Указанная схема маршрутов представляет собой конечную проективную плоскость 7-го порядка.

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .