42-я Балканская математическая олимпиада. Сараево, Босния и Герцеговины, 2025 год

В стране $n$ городов, где $n \ge 100$ – целое число. Некоторые пары городов соединены (двусторонними) рейсами. Для двух городов $A$ и $B$ определяем:
   путь между $A$ и $B$ как последовательность различных городов $A=C_0,C_1,\ldots,C_k,C_{k+1}=B$, $k \ge 0$, такую, что есть рейсы между $C_i$ и $C_{i+1}$ для любого $0\le i\le k$;
   длинный путь между $A$ и $B$ как путь между $A$ и $B$ такой, что никакой другой путь между $A$ и $B$ не содержит больше городов;
   короткий путь между $A$ и $B$ как путь между $A$ и $B$ такой, что никакой другой путь между $A$ и $B$ не содержит меньше городов. Предположим, что для любой пары городов $A$ и $B$ в стране существуют длинный путь и короткий путь между ними, которые не имеют общих городов (кроме $A$ и $B$). Пусть $F$ – общее количество рейсов в стране. Найдите все возможные значения $F$ в зависимости от $n$.

Комментарий/решение

Переведем задачу в граф $G$ с городами в виде вершин и рейсами в виде ребер, гамильтонов цикл и полный граф удовлетворяет условиям

\[ \]

Утверждение: $G $ гамильтонов граф

\[ \]

Доказательство:

Возьмем самый длинный путь в графе $:$

\[ D \ = \ \overset{V_1}{\circ} \ \to \ \overset{V_2}{\circ} \ \to \ \dots \ \to\ \overset{V_t}{\circ} \]

И короткий путь для вершин $: V_1, V_t$

\[ K \ = \ \overset{V_1}{\circ} \ \to \ \overset{X}{\circ} \ \to \ \dots \ \to \ \overset{V_t}{\circ}\]

Но $:$

\[ \overset{X}{\circ} \ \to \ \overset{V_1}{\circ} \ \to \ \dots \ \to \ \overset{V_t}{\circ} \ \mid \ \overset{X}{\circ} \not \in K \cap D \ \to \ \mid K \mid = 2 \]

Несложно доказать что $:$

\[ \overset{V_{i+1}}{\circ} \ \to \ \overset{V_{t-i}}{\circ} \ \mid \ \forall \ 0\leq i\leq t-1\]

Допустим $:$

\[ \exists \ \overset{X_0}{\circ} \ \to \ \overset{X_0}{\circ} \not \in D\]

Можно выбрать его так что $: \ \exists \ 1\leq i \leq t \ \mid \ \overset{X_0}{\circ} \ \to \ \overset{V_i}{\circ}$

\[D_0 \ = \ \overset{X_0}{\circ} \ \to \ \overset{V_i}{\circ} \ \to \ \dots \ \to \ \overset{V_1}{\circ} \ \to \ \overset{V_t}{\circ} \ \to \ \dots \ \to \ \overset{V_{i+1}}{\circ}\]

Но тогда $:$

\[ \mid \ D_0 \mid \ >\ \mid D\ \mid \ \ \to \ \ \varnothing \]

Следовательно $:$

\[ \mid \ D \mid = n \quad \blacksquare\]

Последующие утверждение также верны и для $: \ i-1 > j$

\[ \]

Утверждение: Если $:\ \exists \ \ i<j-1 \mid \ \overset{V_i}{\circ} \ \to \ \overset{V_j}{\circ} \ $ тогда $:\ \overset{V_{i+1}}{\circ} \ \to \ \overset{V_{j+1}}{\circ} $

\[ \]

Доказательство:

\[ \overset{V_{j+1}}{\circ} \ \to \ \dots \ \to \ \overset{V_n}{\circ} \ \to \ \overset{V_1}{\circ} \ \to \ \dots \ \to \ \overset{V_i}{\circ} \ \to \ \overset{V_j}{\circ} \ \to \ \dots \ \to \ \overset{V_{i+1}}{\circ}\quad \blacksquare \]

Утверждение: Если $:\ \exists \ i<j-1 \mid \ \overset{V_i}{\circ} \ \to \ \overset{V_j}{\circ}\ $ тогда $: \ \overset{V_i}{\circ} \ \to \ \overset{V_{i+2}}{\circ} $

\[ \]

Доказательство:

\[ \overset{V_i}{\circ} \ \to \ \overset{V_j}{\circ} \ \to \ \overset{V_{j+1}}{\circ} \ \to \ \overset{V_{i+1}}{\circ } \ \to \ \dots \ \to \ \overset{V_{j-1}}{\circ} \ \to \ \overset{V_{i-1}}{\circ} \ \to \ \dots \ \to \ \overset{V_1}{\circ} \ \to \ \overset{V_n}{\circ} \ \to \ \dots \ \to \ \overset{V_{j+2}}{\circ} \ \to \ \overset{V_{i+2}}{\circ}\quad \blacksquare \]

Утверждение: Если $:\ \exists \ i<j-1 \mid \ \overset{V_i}{\circ} \ \to \ \overset{V_j}{\circ}\ $ тогда $: \ \overset{V_i}{\circ} \ \to \ \overset{V_{j+2}}{\circ} $

\[ \]

Доказательство:

\[ \overset{V_i}{\circ} \ \to \ \dots \ \to \ \overset{V_1}{\circ} \ \to \ \overset{V_n}{\circ} \ \to \ \dots \ \to \ \overset{V_{j+3}}{\circ} \ \to \ \overset{V_{i+3}}{\circ} \ \to \ \dots \ \to\ \overset{V_{j+1}}{\circ} \ \to \ \overset{V_{i+1}}{\circ} \ \to \ \ \overset{V_{i+2}}{\circ} \ \to \ \overset{V_{j+2}}{\circ} \quad \blacksquare\]

\[ \]

Если $: 2 \nmid n \quad \exists \ i < j-1 \mid \ \overset{V_i}{\circ} \ \to \ \overset{V_j}{\circ} \ $ граф полный, в ином случае является гамильтоновым циклом, теперь $: 2 \mid n$

Если $: 2 \mid n \quad \exists \ i < j-1 \mid \ \overset{V_i}{\circ} \ \to \ \overset{V_j}{\circ}\ \mid 2 \nmid j-i$ также влечет за собой что граф либо полный либо гамильтонов цикл

\[ 2 \mid i-j \ \ \to\ \ S_i \in \{\ j \ \mid \ \overset{V_i}{\circ} \ \to \ \overset{V_j}{\circ} \ \} \ \ \to \ \ \mid S_i \mid = \dfrac{n}{2}\]

Количество ребер $:$

\[ \sum \limits_{i=1}^{n} \dfrac{ \mid S_i \mid }{2} = n \cdot \dfrac{\frac{n}{2}}{2} = \dfrac{n^2}{4}\]

Ответ $: \forall \ n \in \mathbb{N} \ \mid \ n, \dfrac{n(n-1)}{2} \quad \forall \ 2 \mid n \ \mid \ \dfrac{n^2}{4} \ $