Combinatoria
Balkan Mo

Balkan Mo P4

Hay $n$ ciudades en un país, donde $n \geq 100$ es un entero. Algunos pares de ciudades están conectados por vuelos directos (de doble sentido). Para dos ciudades $A$ y $B$ definimos: $(i)$ Un $\emph{camino}$ entre $A$ y $B$ como una sucesión de ciudades distintas $A = C_0, C_1, \dots, C_k, C_{k+1} = B$, $k \geq 0$, tal que existen vuelos directos entre $C_i$ y $C_{i+1}$ para todo $0 \leq i \leq k$; $(ii)$ Un $\emph{camino largo}$ entre $A$ y $B$ como un camino entre $A$ y $B$ tal que ningún otro camino entre $A$ y $B$ tiene más ciudades; $(iii)$ Un $\emph{camino corto}$ entre $A$ y $B$ como un camino entre $A$ y $B$ tal que ningún otro camino entre $A$ y $B$ tiene menos ciudades. Suponga que para cualquier par de ciudades $A$ y $B$ en el país, existen un camino largo y un camino corto entre ellas que no tienen ciudades en común (excepto $A$ y $B$). Sea $F$ el número total de pares de ciudades en el país que están conectados por vuelos directos. En términos de $n$, encuentre todos los valores posibles de $F$. Propuesto por David-Andrei Anghel, Rumania.

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados