Olimpiada Cono Sur 2013 Problema 3

Nocycleland es un país con $500$ ciudades y $2013$ caminos de dos vías, cada uno de ellos conectando dos ciudades. Una ciudad $A$ es vecina de $B$ si hay un camino que los conecta, y una ciudad $A$ es cuasi-vecina de $B$ si hay una ciudad $C$ tal que $A$ es vecina de $C$ y $C$ es vecina de $B$ . Se sabe que en Nocycleland, no hay par de ciudades conectadas directamente con más de un camino, y no hay cuatro ciudades $A$ , $B$ , $C$ y $D$ tales que $A$ es vecina de $B$ , $B$ es vecina de $C$ , $C$ es vecina de $D$ , y $D$ es vecina de $A$ . Demostrar que hay al menos una ciudad que es cuasi-vecina de al menos $57$ otras ciudades.

19

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados