sábado, 3 de septiembre de 2011

Un sistema de riego eficiente

Enunciado

La idea consiste en distinguir cuatro casos.

Caso 1) Los cuatro árboles ocupan los vértices de un cuadrilátero convexo, es decir, ninguno de los triángulos que forman tres de los cuatro árboles contiene a otro, y, por supuesto, no están alineados.

En ese caso, el punto de riego óptimo está en el punto de corte de sus dos diagonales, lo cual es sencillo de demostrar si usamos que situar el punto de riego entre dos puntos optimiza el gasto en tubería hacia estos dos.

Caso 2) No hay tres alineados, pero hay tres que forman un triángulo y el otro está contenido en ese triángulo.

Este caso es el que más complicado encuentro de demostrar, pero el punto de riego óptimo está exactamente en el mismo sitio que el árbol contenido en el triángulo. Al parecer, alejarse de ese punto hace que aumente más la distancia a dos de los puntos de lo que la acerca a los otros dos, y por supuesto, es evidente que fuera del triángulo el gasto en tubería es mucho mayor. Pero puesto que no es necesaria una demostración estricta, no he concretado mucho.

Caso 3) Hay tres alineados, y el otro no está en la misma recta.

Este caso es una especie de mezcla entre los dos anteriores. El mejor punto de riego está en el punto intermedio de los tres alineados. Se puede usar el razonamiento del caso 1.

Caso 4) Los cuatro están alineados.

Dos de ellos están más centrados, y los otros dos en el exterior del segmento. Cualquier punto del segmento que une los dos más centrados (incluidos las posiciones de los dos árboles) es válido como punto óptimo.