Cuatro ciudades se encuentran en los vértices de
un rectángulo de lados 4 y 6 kilómetros.
Mediante el uso de los tres lados del rectángulo,
se puede construir una red de carreteras de la longitud total de 14 kilómetros,
que conecta las cuatro ciudades.
¿Existe una red más cortos de caminos, que conecta las ciudades?
Por ejemplo, ¿existe una tal red de longitud menor que 13 kilómetros?
Sugerencia 2
Añadir dos puntos nuevos dentro del rectángulo,
y encontrar una red de caminos que se ramifican en esos dos puntos.
Sugerencia 3
Fijar un punto del segmento paralelo al lado largo del rectángulo,
pasando por el centro, y en distancia
t
de uno de los lados cortos.
A continuación, dibuje segmentos desde cada vértice en ese mismo lado corto
a ese punto.
Repita lo mismo en el otro lado corto,
y unir las dos vías.
Ahora calcula la distancia total como función de
t,
y cálculo para encontrar el mínimo de esta función.
Haga clic aquí para ver el resto de la respuesta.
El Resto de la Respuesta
El dibujo siguiente muestra la red de caminos.
La distancia total es
f(t) = 4\sqrt{4+t^2} + 6 - 2t.
Tomando la derivada y si se establece igual a cero, obtenemos la ecuación
\frac{4t}{\sqrt{4 + t^2}} - 2 = 0,
cuya única solución positiva es
t = 2/\sqrt{3}.
Este es un mínimo para
f(t),
y
f(2/\sqrt{3}) = 6 + 4\sqrt{3} \approx 12.93
es la longitud de la correspondiente red de caminos.
Notas
por Allen Stenger
La generalización de este problema a
n
ciudades, colocados de manera arbitraria en el plano,
se llama el problema de Steiner,
después de Jakob Steiner,
un geómetra del siglo XIX.
El problema de Steiner es el tema de una gran cantidad de investigación hoy en día,
tanto para sus aplicaciones prácticas y por su interés puramente matemático.
Las aplicaciones incluyen el diseño físico de circuitos integrados,
el enrutamiento de mensajes,
el diseño de redes de comunicación,
y el problema de la filogenia en biología computacional.
Resulta que, si no permitimos que ningún punto adicional,
es fácil (también para valores grande de
n)
calcular la distancia mínima necesaria para conectar
n
ciudades,
lo que se llama el "problema de árbol recubridor mínimo".
Pero para el problema de Steiner, donde permitimos puntos adicionales,
la cantidad de cálculos necesarios crece muy rápidamente con
n,
por lo que incluso con los ordenadores se hace impracticable rápidamente.
Por lo tanto existe un gran interés en la búsqueda de buenas soluciones aproximadas
al problema de Steiner,
y en la estimación de cuál bueno son
(en comparación con el árbol recubridor mínimo).
Referencias
-
Richard Courant y Herbert Robbins,
¿Qué Son Las Matemáticas? Conceptos y métodos fundamentales,
Fondo de Cultura Económica, Mexico D. F., 2002. "Avances Recientes",
sección 10, "El Problema de Steiner", pp. 553-559. Da información sobre
el desarrollo actual de este problema.
-
(en inglés) Puede ver la problema original de Josh
aquí.
