IMO Shortlist 2021 Problema C4

El reino de Anisotropía consta de $n$ ciudades. Para cada par de ciudades existe exactamente una carretera directa y unidireccional entre ellas. Decimos que un "camino" de $X$ a $Y$ es una secuencia de carreteras en las uno se puede mover de $X$ a $Y$ a lo largo de esta secuencia sin volver a una ciudad ya visitada. Una colección de caminos se llama diversa si ninguna carretera pertenece a dos o más caminos en la colección. Sean $A$ y $B$ dos ciudades distintas en Anisotropía. Denotemos por $N_{AB}$ la cantidad máxima de caminos en una colección diversa de caminos de $A$ a $B$. De manera similar, denotemos por $N_{BA}$ la cantidad máxima de caminos en una colección diversa de caminos de $B$ a $A$. Demuestra que la igualdad $N_{AB} = N_{BA}$ se cumple si y solo si el número de carreteras que salen de $A$ es igual al número de carreteras que salen de $B$.

10

0

Kevin

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados