32º Torneo - Primera Ronda - Problema 1 Mayor

Problemas que aparecen en el Archivo de Enunciados.

32º Torneo - Primera Ronda - Problema 1 Mayor

UNREAD_POSTpor ésta » Dom 31 Oct, 2010 11:26 pm

En cierto país hay $100$ 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 $4950$ registros).

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

b) Supongamos que $k$ registros se han borrado y que no hay tres pueblos en una misma línea. ¿Cuál es el máximo $k$ tal que está garantizada la recuperación de los registros borrados?
Imagen
Avatar de Usuario
ésta
 
Mensajes: 263
Registrado: Sab 16 Oct, 2010 4:55 pm
Medals: 3
Colaborador OFO - Jurado OFO - Jurado
Nivel: Ñandú

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

UNREAD_POSTpor 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 $5$ vértices tales que todo par de vértices esté conectado salvo uno, es decir, tenemos $3$ vértices con grado $4$ y $2$ con grado $3$. Cuando queremos ubicar un punto $p$ respecto de otro punto $p_1$ conociendo su distancia $d$, obtenemos que $p$ puede estar ubicado en cualquier punto de una circunferencia de radio $d$ y centro en $p_1$. Repitiendo esa operación con los puntos $p_2$ y $p_3$ obtenemos $3$ circunferencias que se intersecan en un único punto,
dándonos así la ubicación de $p$. Hacemos lo mismo para un punto $p'$ y de esa forma conocemos la ubicación de $p$y $p'$,
y por lo tanto su distancia, por lo que recuperamos el registro.

Para armar el grafo con los $100$ pueblos tomamos uno de ellos al azar y le asignamos las coordenadas $(0;0)$. 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.
$\phi=\frac {1+{\sqrt {5}}}{2}$
Avatar de Usuario
Gianni De Rico
 
Mensajes: 166
Registrado: Vie 16 Sep, 2016 6:58 pm
Ubicación: Rosario
Nivel: 3


Volver a Problemas Archivados

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado