OMA Foros

En cierto país hay [math]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 [math]4950 registros).

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

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

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

Para armar el grafo con los [math]100 pueblos tomamos uno de ellos al azar y le asignamos las coordenadas [math](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.