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

Бір елде $n$ қала бар, мұнда $n \ge 100$ — бүтін сан. Кейбір қала жұптары екіжақты рейстермен қосылған. Екі $A$ және $B$ қала үшін келесі анықтамалар енгізіледі:
   жол — бұл әр түрлі қалалардың тізбегі $A=C_0,C_1,\ldots,C_k,C_{k+1}=B$, $k \ge 0$, мұнда әрбір $0\le i\le k$ үшін $C_i$ мен $C_{i+1}$ арасында рейс бар;
   ұзын жол — $A$ мен $B$ арасындағы жол, мұндай жолдан артық қала қамтитын басқа жол жоқ;
   қысқа жол — $A$ мен $B$ арасындағы жол, мұндай жолдан аз қала қамтитын басқа жол жоқ. Әрбір қала жұбы $A$ және $B$ үшін ұзын және қысқа жолдар бар деп ұйғарайық, және олар ортақ қалаға тек $A$ және $B$ нүктелерінде ғана ие болады. $F$ — елдегі барлық рейстердің жалпы саны болсын. $n$-ге тәуелді барлық мүмкін болатын $F$ мәндерін табыңыз.

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

Переведем задачу в граф $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} \ $