Город на проективной плоскости

[Профессор Снэйп]

Автобусная сеть города устроена следующим образом:

1) С любой остановки на любую другую можно доехать одним из маршрутов без пересадки.

2) Для любой пары маршрутов существует единственная остановка, на которой можно пересесть с одного маршрута на другой.

3) На каждом маршруте $n$ остановок. Число $n$ больше единицы. Количество маршрутов больше единицы.

Требуется

а) Найти количество маршрутов и количество всех остановок.

б) Определить все возможные значения $n$.

[e2e4]

По-моему, решения существуют только при $n=2$, и их бесконечное множество.

[Профессор Снэйп]

e2e4 писал(а):

По-моему, решения существуют только при $n=2$, и их бесконечное множество.

1) Вам для $n=3$ решение показать или сами перебором найдёте?

2) Покажите мне хотя бы два различных решения для $n=2$

[Kid Kool]

Пусть имеется k остановок и m маршрутов.

Рассмотрим все пары остановок, их будет $\frac{k(k-1)}{2}$ штук. Каждой паре соответствует маршрут, каждый из которых мы считали $\frac{n(n-1)}{2}$ (число пар остановок на маршруте) раз. Значит, $k(k-1)$ = $mn(n-1)$.

Выделим один маршрут. Рассмотрим оставшиеся (не лежащие на маршруте) k-n остановок. Среди них имеется $\frac{(k-n)(k-n-1)}{2}$ пар, каждая дает нам один из m-1 оставшихся маршрутов, каждый из которых учитывался $\frac{(n-1)(n-2)}{2}$ раз. Итого получаем $(k-n)(k-n-1)$ = $(m-1)(n-1)(n-2)$ = $mn(n-1) - n(n-1) - 2(m-1)$ = $k(k-1) - n(n-1) - 2(m-1)$, $(k-n)^2-(k-n)-k^2+k = -n(n-1)-2(m-1)$, $-2kn+n^2+n$ = $-n^2 + n - 2(m-1)$, $2n^2-2kn = -2(m-1)$, m-1 = n(k-n). Тогда либо k=n, что невозможно, т.к. иначе имеется один маршрут, либо $k-n-1$ = $n(n-1)(n-2)$, $k$ = $(n-1)^3+2$, m = n(k-n)+1.

Но это только необходимое условие.

Добавлено спустя 2 минуты 36 секунд:

P.S. У меня n - общее число остаовок на маршруте, включая начальный и конечный пункты.

[Профессор Снэйп]

Kid Kool писал(а):

Пусть имеется k остановок и m маршрутов.

Рассмотрим все пары остановок, их будет $\frac{k(k-1)}{2}$ штук. Каждой паре соответствует маршрут, каждый из которых мы считали $\frac{n(n-1)}{2}$ (число пар остановок на маршруте) раз. Значит, $k(k-1)$ = $mn(n-1)$.

Выделим один маршрут. Рассмотрим оставшиеся (не лежащие на маршруте) k-n остановок. Среди них имеется $\frac{(k-n)(k-n-1)}{2}$ пар, каждая дает нам один из m-1 оставшихся маршрутов, каждый из которых учитывался $\frac{(n-1)(n-2)}{2}$ раз. Итого получаем $(k-n)(k-n-1)$ = $(m-1)(n-1)(n-2)$ = $mn(n-1) - n(n-1) - 2(m-1)$ = $k(k-1) - n(n-1) - 2(m-1)$, $(k-n)^2-(k-n)-k^2+k = -n(n-1)-2(m-1)$, $-2kn+n^2+n$ = $-n^2 + n - 2(m-1)$, $2n^2-2kn = -2(m-1)$, m-1 = n(k-n). Тогда либо k=n, что невозможно, т.к. иначе имеется один маршрут, либо $k-n-1$ = $n(n-1)(n-2)$, $k$ = $(n-1)^3+2$, m = n(k-n)+1.

Не знаю, где у Вас там ошибка (лень вникать), но ответ неправильный.

Рассмотрите для примера $n=3$. В этом случае $k=m=7$ и карта маршрутов рисуется "единственным образом" (она всегда единственна с точностью до перестановки остановок )

[e2e4]

Профессор Снэйп писал(а):

Вам для $n=3$ решение показать или сами перебором найдёте?

Покажите, пожалуйста.

Профессор Снэйп писал(а):

Покажите мне хотя бы два различных решения для $n=2$

Пожалуйста:

*         *-------*
| \       |\    / |
|  \      |  \ /  |
*---*     |  / \  |
          | /    \|
          *-------*

Звездочки - остановки. Линии - маршруты. Ничего, что я воспользовался ASCII-графикой?

Добавлено спустя 9 минут:

Нда, подумал еще (у меня такая привычка - я привык два раза думать (с) ), и понял, что квадрат не подходит - не удовлетворяется условие №2 для диагональных маршрутов.

Как построить с $n=3$ я все-таки не понимаю. Равнобедренный треугольник с медианами (биссектрисами, высотами), с точкой пересечения и точкой на противоположной стороне треугольника - остановками - не получается, не удовлетворяет условию №1.

[Профессор Снэйп]

e2e4 писал(а):

Нда, подумал еще (у меня такая привычка - я привык два раза думать (с) ), и понял, что квадрат не подходит - не удовлетворяется условие №2 для диагональных маршрутов.

Надеюсь, Вы берёте назад свои слова о множественности решений при $n=2$?

e2e4 писал(а):

Как построить с $n=3$ я все-таки не понимаю. Равнобедренный треугольник с медианами (биссектрисами, высотами), с точкой пересечения и точкой на противоположной стороне треугольника - остановками - не получается, не удовлетворяет условию №1.

Ну, если Вы так настаиваете на примере...

Всего 7 остановок, которым соответствуют числа от $1$ до $7$. Каждый маршрут --- это трёхэлементное подмножество множества $\{ 1, \ldots, 7 \}$. Маршрутов тоже $7$. Ниже я их перечисляю.

М1: $\{ 1,2,3 \}$
М2: $\{ 1,4,5 \}$
М3: $\{ 1,6,7 \}$
М4: $\{ 2,5,6 \}$
М5: $\{ 3,4,6 \}$
М6: $\{ 3,5,7 \}$
М7: $\{ 2,4,7 \}$

Проверяйте

P. S. Эти 7 маршрутов легко изобразить графически. Начертите равносторонний треугольник, отметьте середину сторон и поставьте точку в середине треугольника. Проведите три медианы (они же биссектриссы и высоты). Шесть маршрутов готово. Седьмой маршрут --- "кольцевой", соединяет середины сторон.

[e2e4]

Профессор Снэйп писал(а):

Надеюсь, Вы берёте назад свои слова о множественности решений при $n=2$?

Да, беру.

Профессор Снэйп писал(а):

Седьмой маршрут --- "кольцевой", соединяет середины сторон.

Не догадался до соединения седьмого маршрута кольцом. Тогда, действительно, всем условиям удовлетворяет, спасибо за пример.

[Kid Kool]

Профессор Снэйп писал(а):

Не знаю, где у Вас там ошибка (лень вникать), но ответ неправильный.

Пересчитал. Получилось $k = m = n^2 - n +1$.

Добавлено спустя 1 минуту 30 секунд:

Ошибка была здесь:

Kid Kool писал(а):

$(m-1)(n-1)(n-2)$ = $mn(n-1) - n(n-1) - 2(m-1)$

[Профессор Снэйп]

Kid Kool писал(а):

Профессор Снэйп писал(а):

Не знаю, где у Вас там ошибка (лень вникать), но ответ неправильный.

Пересчитал. Получилось $k = m = n^2 - n +1$.

Да, это правильный ответ. Расскажу теперь своё решение. Оно мне нравится тем, что носит "чисто геометрический" характер (и вообще выдержано в духе школьного учебника по геометрии).

Лемма 1. Для каждой остановки найдётся маршрут, не проходящий через эту остановку.

Доказательство. Пусть $A$ --- произвольная остановка. Зафиксируем два различных маршрута $\alpha$ и $\beta$ (по условию имеется больше одного маршрута). Если хотя бы один из них не содержит $A$, то доказывать нечего. В противном случае рассмотрим отличные от $A$ остановки $B$ и $C$, такие что $B \in \alpha$ и $C \in \beta$ (они найдутся, поскольку каждый маршрут содержит более одной остановки). Имеем $B \not\in \beta$, так как в противном случае маршруты $\alpha$ и $\beta$ содержат более одной общей остановки ($A$ и $B$). Так как $C \in \beta$ и $B \not\in \beta$, то $B \neq C$. По условию существует маршрут $\gamma$, содержащий остановки $B$ и $C$. Так как $B \in \gamma$ и $B \not\in \beta$, то $\gamma \neq \beta$. Но тогда $\gamma$ не может содержать $A$, ибо в противном случае различные маршруты $\beta$ и $\gamma$ содержат разные общие остановки $A$ и $C$. $\qed$

Лемма 2. Через каждую остановку проходит ровно $n$ различных маршрутов.

Доказателство. Пусть $A$ --- произвольная остановка. По лемме 1 найдётся маршрут $\gamma$, такой что $A \not\in \gamma$. Пусть $B_1, \ldots, B_n$ --- все остановки, лежащие на маршруте $\gamma$. По условию для каждого $i \in [1,n]$ найдётся единственный маршрут $\alpha_i$, проходящий через остановки $A$ и $B_i$. Так как любой маршрут, проходящий через $A$, имеет общую остановку с маршрутом $\gamma$, то $\alpha_1, \ldots, \alpha_n$ --- это все маршруты, проходящие через $A$. Осталось показать, что при различных $i$ и $j$ маршруты $\alpha_i$ и $\alpha_j$ также различны. Предположим противное и пусть $\alpha = \alpha_i = \alpha_j$ при $i \neq j$. Тогда $B_i \in \alpha$, $B_j \in \alpha$ и маршруты $\alpha$ и $\gamma$ имеют более одной общей остановки. Но они не могут быть равны, поскольку $A \in \alpha$ и $A \not\in \gamma$. Противоречие. $\qed$

Теперь выберем произвольную остановку $A$ и пусть $\alpha_1, \ldots, \alpha_n$ --- все маршруты, проходящие через неё. Пусть $\beta_i = \alpha_i \setminus \{ A \}$ для $i$ от $1$ до $n$. Поскольку любая остановка, отличная от $A$, соединяется с $A$ одним из маршрутов, то множество $\{ A \} \cup \bigcup_{i=1}^n \beta_i$ содержит все имеющиеся остановки. Любые два члена этого объединения не пересекаются, так что общее количество остановок получается равным $n(n-1)+1$.

Наконец, выберем произвольный маршрут $\alpha$ и пусть $A_1, \ldots, A_n$ --- все его остановки. Для каждого $i$ от $1$ до $n$ пусть $\mathcal{M}_i$ --- множество всех маршрутов, отличных от $\alpha$ и проходящих через $A_i$. Так как любой маршрут имеет общую остановку с маршрутом $\alpha$, то $\{ \alpha \} \cup \bigcup_{i=1}^n \mathcal{M}_i$ есть множество всех имеющихся маршрутов. При различных $i$ и $j$ справедливо $\mathcal{M}_i \cap \mathcal{M}_j = \varnothing$, ибо в противном случае найдётся маршрут $\beta \in \mathcal{M}_i \cap \mathcal{M}_j$, не равный $\alpha$ и содержащий две общих с маршрутом $\alpha$ остановки $A_i$ и $A_j$. Кроме того, по лемме 2 каждое множество $\mathcal{M}_i$ содержит ровно $n-1$ элемент. Таким образом, количество всех маршрутов также равно $n(n-1)+1$.

------------------------------

Что касается второй задачи (при каких $n$ система маршрутов с указанными свойствами вообще существует), то я сам не знаю, как её решать. Более того, я где-то слышал, что этот вопрос является открытой проблемой (по сути это вопрос о возможном количестве элементов у конечной проективной плоскости). Вроде бы даже не известно, существует ли решение при $n=13$.

Сформулирую тогда уж третью задачу, решение которой мне известно

в) Доказать, что для $n=p^k+1$, где $p$ --- простое, существует система маршрутов со свойствами, описанными в первом сообщении темы.

[RIP]

Особо не думал, но похоже, что в задаче идёт речь о конечной проективной плоскости порядка $n-1$. Есть гипотеза, что конечная проективная плоскость порядка $m$ существует тогда и только тогда, когда $m=p^k$. Для $m=p^k$ можно взять самую обычную проективную плоскость $\mathbb{PF}_{m}^2$ над полем из $m$ элементов (хотя существуют и другие примеры). А вот в другую сторону начинаются проблемы. Единственное, что известно мне, так это теорема Брука-Райзера (Bruck-Ryser) о том, что если для $m\equiv1,2\pmod4$ существует конечная проективная плоскость порядка $m$, то $m$ представимо в виде $m=x^2+y^2$, $x,y\in\mathbb Z$, а также то, что суровым компутерным перебором проверено, что не существует конечной проективной плоскости порядка 10.

[Профессор Снэйп]

RIP писал(а):

Для $m=p^k$ можно взять самую обычную проективную плоскость $\mathbb{PF}_{m}^2$ над полем из $m$ элементов (хотя существуют и другие примеры).

В общем-то, я именно её и имел в виду в третьей задаче

Так что задачу номер 3 можно решать двумя способами:

1) Посмотреть в книжке, что такое $\mathbb{PF}_{m}^2$.
2) Догадаться самому.

Я когда-то нашёл решение вторым способом