Torneo de las Ciudades - Marzo 2016 - NM P4

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 1047
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Torneo de las Ciudades - Marzo 2016 - NM P4

Mensaje sin leer por Gianni De Rico » Sab 06 Jul, 2019 4:59 pm

En un país hay $64$ ciudades, algunos pares de ciudades están conectadas mediante caminos, pero no se sabe cuáles son estos pares. La operación permitida es elegir un par de ciudades y preguntar si están conectadas o no (la respuesta siempre será verdadera). El objetivo es averiguar si es posible viajar de cualquier ciudad a cualquier otra mediante una secuencia de caminos.
Demostrar que es imposible cumplir el objetivo con menos de $2016$ operaciones permitidas.
Queda Elegantemente Demostrado

Responder