Russian TST 2022 2022 Problema 2

El reino de Anisotropía consta de $n$ ciudades. Para cada dos ciudades existe exactamente una carretera directa de un solo sentido entre ellas. Decimos que un camino de $X$ a $Y$ es una sucesión de carreteras tal que uno puede moverse de $X$ a $Y$ a lo largo de esta sucesión 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 de la colección. Sean $A$ y $B$ dos ciudades distintas de Anisotropía. Sea $N_{AB}$ el número máximo de caminos en una colección diversa de caminos de $A$ a $B$ . De manera similar, sea $N_{BA}$ el número máximo de caminos en una colección diversa de caminos de $B$ a $A$ . Demuestre que la igualdad $N_{AB} = N_{BA}$ se cumple si y solo si el número de carreteras que salen de $A$ es el mismo que el número de carreteras que salen de $B$ . Propuesto por Warut Suksompong, Tailandia

0

0

Kevin

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados