El problema:
Hay un agricultor que tiene un $1\text{ mile}\times 1\text{ mile}$ pedazo cuadrado de tierra. Sabe que hay un completamente recta tubería debajo de alguna parte de su propiedad, pero podría ir en cualquier dirección. Quiere cavar algunas zanjas para encontrarla. Sabe que si excava alrededor de la propiedad la encontraremos, pero eso requiere 4 millas de excavación. ¿Qué elección de líneas minimiza la cantidad de excavación necesaria, y cuál es esa cantidad mínima?
Basta con tres líneas alrededor del perímetro para reducir la excavación a sólo 3 millas. Después de pensarlo un poco más, se ve que sólo se necesitan 2 líneas diagonales, lo que supone 2,82 millas de excavación.
No creo que inventar ejemplos sea tan difícil, es sólo que demostrarlo parece imposible. De momento he encontrado algo con longitud $\sqrt{2}+\sqrt{3/2}$ pero no puedo demostrar que sea óptimo. Vale la pena señalar que las líneas pueden ser desconectados, y puede tener finitamente muchas piezas. La solución que tenía arriba se compone de dos piezas diferentes.
Cualquier ayuda es muy apreciada.
4 votos
Vaya al registro del condado y pida ver la copia archivada de la servidumbre de paso de la empresa de servicios públicos
0 votos
Menos caprichosamente, mi intuición es que el minino será un Árbol de Steiner conectando las cuatro esquinas.
1 votos
Estoy seguro de que he visto esta misma pregunta en math.SE antes, pero no puedo encontrarlo ahora. Si no recuerdo mal, alguien enlazó a un artículo que abordaba las generalizaciones de este problema a polígonos regulares; la solución óptima para el cuadrado era la unión de un árbol de Steiner en tres esquinas con una perpendicular caída desde la cuarta hasta la diagonal.
0 votos
@Henning: ¡Es una muy buena idea! Pero hay que tener en cuenta que podemos usar líneas desconectadas. La idea que tengo ahora mismo es una línea desde la esquina 1 directamente al centro. Luego conectar las otras tres esquinas, pero teniendo el punto de encuentro lo más alejado posible de la esquina 1. (He utilizado algunos cálculos para encontrar el máximo) Lo que obtuve fue $\sqrt{2}+\sqrt{3/2}$
0 votos
Sí, el árbol de Steiner completo es un poco más largo que tu solución (suponiendo que tu cálculo de su longitud sea correcto). Así que, por desgracia, no se puede utilizar para argumentar la optimalidad.
0 votos
Su solución es la que mencionó @Rahul.
0 votos
Si no me equivoco, esto equivale a un problema que he oído plantear de esta manera: Encontrar un conjunto de líneas de longitud total mínima que sea "tan bueno como" un cuadrado sólido con respecto al bloqueo de las líneas de visión. (En el caso de la OP, la tubería ocupa el lugar de una línea de visión arbitraria). piense en el problema seguía abierto cuando me enteré, pero esto fue hace 20 años. De todos modos, esta reformulación del problema puede ayudar a buscar referencias.
0 votos
Mi hipótesis es que la longitud es cero. Supongamos que ordenas todos los puntos del cuadrado que tienen coordenadas racionales, y luego cavas líneas centradas en cada uno de estos puntos racionales con longitud $\frac{\epsilon}{2^k}$ en direcciones aleatorias. La longitud total de la línea cortada es $\epsilon$ pero intuitivamente parece muy poco probable que cualquier línea pueda pasar por este cuadrado sin ser detectada. Supongo que esto se puede demostrar rigurosamente con el método probabilístico, aunque no estoy seguro y los detalles no son inmediatamente obvios.
1 votos
susqu.edu/brakke/opaque/opaqsq.html da la solución que dio Rahul, pero dice que no se ha demostrado que sea óptima. Véase también Asimov y Gerver, Minimum opaque manifolds, Geometriae Dedicata 133 (2008) 67-82. Quizá la mejor referencia sea arxiv.org/pdf/1005.2218.pdf
0 votos
Es posible que me haya imaginado "óptimo" donde el papel que recordaba vagamente decía "más conocido". Perdón por la desinformación.
0 votos
@Nick, el documento referenciado al final del comentario de Gerry tiene una prueba que $2$ es un límite inferior. En particular, su esquema no funciona porque si la longitud total de sus segmentos es $\epsilon < 1$ , ni siquiera puede cubrir todo el ancho del cuadrado, por lo que hay alguna línea vertical que pasará sin ser detectada.
0 votos
@Rahul, ahh, tienes razón mi enfoque no funciona. Gracias por la respuesta.
0 votos
Creo que necesito más información. Qué tal la longitud del tubo recto?
0 votos
Es infinito. Se desconoce la longitud que hay realmente bajo el terreno del agricultor. (Imagina una línea recta que intercepta un cuadrado).
1 votos
@GerryMyerson: Creo que deberías publicar el paper de arxiv como respuesta, porque parece ser el resultado más conocido y dice de la $\sqrt{2} + \sqrt{3/2}$ solución que "La barrera más corta conocida para el cuadrado, de longitud 2,639... se conjetura como óptima. El mejor límite inferior actual es 2, establecido por Jones [24]".
0 votos
@ShreevatsaR, lo haré, mañana, si puedo.