Olimpiada IMO Shortlist 2021 Problema C4

El reino de Anisotropía consta de $n$ ciudades. Para cada dos ciudades existe exactamente un camino directo de un solo sentido entre ellas. Decimos que un camino de $X$ a $Y$ es una secuencia de caminos tal que uno puede moverse de $X$ a $Y$ a lo largo de esta secuencia sin regresar a una ciudad ya visitada. Una colección de caminos se llama diversa si ningún camino pertenece a dos o más caminos en la colección. Sean $A$ y $B$ dos ciudades distintas en Anisotropía. Sea $N_{AB}$ denota el número máximo de caminos en una colección diversa de caminos de $A$ a $B$ . De manera similar, sea $N_{BA}$ denota el número máximo 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 caminos que salen de $A$ es el mismo que el número de caminos que salen de $B$ .

26

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados