Городок DIV-GRAD

[Zeddikus]

Правильное ли решение следующей задачи?
Городок DIV-GRAD обладает отличной автобусной сетью! С каждой остановки можно проехать на любую другую без пересадок. Каждый маршрут имеет 5 остановок, а каждые два маршрута имеют единственную общую остановку. Сколько же автобусных маршрутов в этом дивном граде? Нарисуйте карту.
Решение:
Пусть a – один из маршрутов, B – остановка, через которую маршрут a не проходит. Каждый маршрут, проходящий через B, пересекает маршрут a. При этом два разных маршрута, проходящих через B, пересекают a по разным остановкам (иначе они имели бы две общие остановки, что противоречит условию). Поэтому через B проходит ровно пять маршрутов.
На каждом из них есть по 4 остановки, отличных от B. Значит, всего в городе 21 остановка. Через каждую пару остановок (а их 210) проходит единственный маршрут, при этом на каждом маршруте – пять пар остановок. Следовательно, всего маршрутов 210 : 5 = 42.

Карту не получилось нарисовать.

[Ende]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: темы, в которых нужно что-то объяснить или подсказать в пределах учебных курсов, создаются в этом разделе.
В олимпиадном разделе размещаются задачи, решение которых известно топикстартеру, но он предлагает другим участникам попробовать свои силы в поисках этого решения.

[mihaild]

Zeddikus в сообщении #1630236 писал(а):

Через каждую пару остановок (а их 210) проходит единственный маршрут, при этом на каждом маршруте – пять пар остановок

А сколько пар остановок на маршруте?

[waxtep]

Формально автобусная "сеть" из одного маршрута тоже подходит

[waxtep]

Задача обладает некоторым коварством: если на каждом маршруте по две остановки (а не по пять), - подходит вообще любое количество маршрутов (от трёх и больше)

[мат-ламер]

В качестве юмора

Zeddikus в сообщении #1630236 писал(а):

С каждой остановки можно проехать на любую другую без пересадок. Каждый маршрут имеет 5 остановок, а каждые два маршрута имеют единственную общую остановку.

Можно взять правильный пятиугольник. Его стороны единственный маршрут в городе. Условие "каждые два маршрута ..." выполняется автоматически, поскольку маршрут всего один

[Dendr]

Zeddikus в сообщении #1630236 писал(а):

при этом на каждом маршруте – пять пар остановок. Следовательно, всего маршрутов 210 : 5 = 42.

А разве не 10 пар? Тогда маршрутов тоже 21.

[Dendr]

Zeddikus в сообщении #1630236 писал(а):

Карту не получилось нарисовать.

Собственно, задача распространяется на общий случай $N$ станций на каждом маршруте, тогда в городе $N^2-N+1$ станция и столько же маршрутов.

Случай $N=2$ - это треугольник, каждая из сторон которого - один маршрут. Банально...

Для $N=3$ рисовать нетрудно почти наугад, но картинка ясности не вносит, там просто семиконечный граф из разноцветных треугольников. Мне кажется, лучше подобрать логику и объяснить на словах.
Есть Центральный автовокзал (обозначим его буквой $O$), через который проходит 3 треугольных маршрута (для удобства все маршруты - круговые), на каждом из них остановки пронумерованы: $A_0, A_1, B_0, B_1, C_0, C_1$. Еще 4 маршрута формируются так: $\{A_iB_jC_k\; |\; i+j+k \equiv 0\mod{2}\}$, можно и единице - неважно. Тогда все условия выполнены.

Соответственно, для $N=5$ можно поступить аналогично: центр $O$, через который строятся маршруты $A, B, C, D, E$ с остановками с индексами $0..3$. Тогда еще 16 маршрутов проходят по точкам $A_iB_jC_kD_lE_m$. Здесь можно исхитриться суммой по модулю, но мне лениво, а можно составить таблицу, где обозначить маршруты буквами от $F$ до $U$ по этим точкам. Например:

На карте, очевидно, выйдет месиво из линий, поэтому можно рисовать, но лучше воображать.