0
1

Городок DIV-GRAD обладает отличной автобусной сетью! С каждой остановки можно проехать на любую другую без пересадок. Каждый маршрут имеет пять остановок, а каждые два маршрута имеют единственную общую остановку. Сколько же автобусных маршрутов в этом дивном граде?

задан 27 Июл '15 14:54

изменен 27 Июл '15 20:41

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
3

(Это вопрос о том, сколько прямых в конечной проективной плоскости порядка $%4+1$%. Ответ: $%4^2+4+1$%. )

Пусть через некоторую остановку A проходит $%k+1$% маршрут. Тогда на каждом из них, кроме A, еще 4 остановки, и все эти остановки различны (потому что общая остановка у любой пары маршрутов единственная - A). Никаких иных остановок нет. Итого всего в городе $%1+(k+1)4$% остановок. Они образуют $%2(k+1)(4k+5)$% пар, при этом каждый маршрут включает 10 таких пар. Значит, общее число маршрутов равно $%(k+1)(4k+5)/5$%. Мы видим, что эти характеристики однозначно задаются кол-вом маршрутов через произвольно взятую остановку. Значит, для всех остановок это количество одно и то же. Теперь нетрудно сосчитать число пар различных маршрутов, оно равно $%k(k+1)(4k+5)(4k+9)/50$%, и это должно быть в $%k(k+1)/2$% раз больше числа остановок, потому что любые два маршрута задают одну остановку, и каждая остановка получается таким образом из $%k(k+1)/2$% пар маршрутов. Получаем уравнение $%k(k+1)(4k+5)(4k+9)/50 = k(k+1)/2 \cdot (4k+5)$%, из которого $%4k+9=25$%, $%k=4$%.

Соответственно, число маршрутов равно $%5\cdot21/5=21$%.

ссылка

отвечен 27 Июл '15 15:34

3

@knop: мне кажется, здесь подсчёт можно произвести проще. Во-первых, условие в принципе не исключает, что маршрут всего один. Но если этот тривиальный случай не рассматривать, то берём точку A и не проходящий через неё маршрут с остановками $%A_1,...,A_5$%. Тогда все точки лежат на прямых вида $%AA_i$%, и повторений нет, то есть остановок будет $%1+5\cdot4=21$%.

(27 Июл '15 18:11) falcao

@falcao - да, и так тож можно. Я просто скомпилировал некоторую версию стандартного рассуждения о КПП, давшую результат

(27 Июл '15 20:07) knop

@knop: наверное, бывают какие-то задачи, где аксиомы проективной плоскости даны в ослабленной форме, и тогда рассуждение может быть более сложным. Но здесь вроде как информация дана исчерпывающая, то есть подсчёт проходит сразу.

А Вы можете дать более слабую формулировку условия, где рассуждение требуется более длинное?

(27 Июл '15 20:22) falcao

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

(27 Июл '15 23:59) knop
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,231
×164

задан
27 Июл '15 14:54

показан
437 раз

обновлен
27 Июл '15 23:59

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru