32º Torneo - Primera Ronda - Problema 1 Mayor

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
ésta

Colaborador OFO - Jurado
Mensajes: 291
Registrado: Sab 16 Oct, 2010 4:55 pm
Medallas: 3
Nivel: Ñandú

32º Torneo - Primera Ronda - Problema 1 Mayor

Mensaje sin leer por ésta » Dom 31 Oct, 2010 11:26 pm

En cierto país hay [math] pueblos (considérelos como puntos del plano). Hay un libro que, para cada par de pueblos, contiene el registro de la distancia entre ellos (un total de [math] registros).

a) Un registro se ha borrado. ¿Es posible restablecerlo usando los otros registros?

b) Supongamos que [math] registros se han borrado y que no hay tres pueblos en una misma línea. ¿Cuál es el máximo [math] tal que está garantizada la recuperación de los registros borrados?
Imagen

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 444
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: 32º Torneo - Primera Ronda - Problema 1 Mayor

Mensaje sin leer por Gianni De Rico » Sab 17 Jun, 2017 8:57 pm

Parte a):
Spoiler: mostrar
Armemos un grafo donde los pueblos son los vértices y dos pueblos están conectados por una arista si y solo si existe su registro. Tomemos [math] vértices tales que todo par de vértices esté conectado salvo uno, es decir, tenemos [math] vértices con grado [math] y [math] con grado [math]. Cuando queremos ubicar un punto [math] respecto de otro punto [math] conociendo su distancia [math], obtenemos que [math] puede estar ubicado en cualquier punto de una circunferencia de radio [math] y centro en [math]. Repitiendo esa operación con los puntos [math] y [math] obtenemos [math] circunferencias que se intersecan en un único punto,
dándonos así la ubicación de [math]. Hacemos lo mismo para un punto [math] y de esa forma conocemos la ubicación de [math]y [math],
y por lo tanto su distancia, por lo que recuperamos el registro.

Para armar el grafo con los [math] pueblos tomamos uno de ellos al azar y le asignamos las coordenadas [math]. Luego vamos ubicando todos los puntos a las distancias que conocemos hasta que tenemos el grafo sólo con una arista faltante. Lo único que cambia es que todo el grafo puede estar rotado con centro en nuestro primer punto, pero como eso no afecta la forma de ubicar los puntos faltantes, no pasa nada.
[math]

Responder