[mathtruco]

Hola,

 les dejo un problema que considero interesante de abordar.


Tengo que entregar n diarios a pié dentro de una zona circular de radio r.

Para entregar el primer diario no camino nada, porque un camión me deja en la ubicación dentro del círculo que yo quiera.

SI SIEMPRE TRATO DE CAMINAR LO MENOS POSIBLE, entonces

- Si debo entregar 2 diarios, obviamente a lo más caminaré 2r (el peor de los casos es que los diarios los tenga que entregar en los extremos).

En general,
 en el peor de los casos (de ubicación de diarios), cuánto es lo que más caminaré si debo entregar diarios en n casas?

[mathtruco]

Veo que no es un problema trivial.
A mí me pareció bastante desafiante encontrar una cota.

Les tiro una cota, a ver si a alguien se le ocurre como mejorarla:

A lo más se recorre 2r(n-1).

¿Alguien consigue mejorarla?

[pepito]

Fijate que dado un \( n\in\mathbb{N} \), podés considerar la función \( f: {(\overline{B}_{((0,0),r)})}^n\rightarrow{}\mathbb{R} \) que para cada posible disposición de las \( n \) casas te da la distancia que tenés que caminar (eligiendo el camino más corto posible). Como el dominio de \( f \) es compacto y \( f \) es contínua, sabés que \( f \) alcanza un valor máximo.

Mi sospecha es que la disposición de las casas para la que \( f \) alcanzaría este máximo es si todas están ubicadas sobre el borde del círculo formando los vértices de un polígono regular, pero esto habría que probarlo...

Una posible forma de mejorar tu cota (que igual no es una gran cosa) sería dividir al círculo en \( n-1 \) "porciones" iguales, como si fuera una pizza, y como sí o sí tiene que haber dos casas en la misma "porción", entonces para toda disposición de las casas va a existir un camino en el que la longitud de uno de los tramos se puede acotar por algo más chico que \( 2r \). Después, para \( n \)'s más grandes, podrías eventualmente dividir al círculo en menos partes todavía y sacar alguna otra conclusión... pero ese no me parece que sea el camino.

[Luis Fuentes]

Hola

 Yo estoy de acuerdo con el enfoque de pepito y con su sospecha.

 Tampoco tengo muy claro como porbarlo. Pero propongo el siguiente plan:

 1) Probar que si los \( n \) puntos están en el borde del círculo el camino más largo se obtiene cuando los puntos son los vértices de un polígono regular y tal camino mide el perímetro del polígono menos un lado.

 2) Probar que cualquier distribución que tenga un punto en el interior puede ser "empeorada" llevando ese punto y/o otros a los bordes del círculo.

Saludos.

[mathtruco]

Gracias a ambos. La solución que proponene me ha dejado conforme.

Éstos son los casos en que la intuición geométrica es suficiente para probar algo. Me parece que la formalización, aunque sería muy bonito dar con ella, estaría demás.

[pepito]

Está mal. Fíjense:

Uno puede buscar un \( n \) tal que cada lado del polígono regular de \( n \) lados inscrito sobre la circunferencia mida menos que el radio (supongo que es bastante evidente que este \( n \) existe y que es universal, es decir, que no depende de la circunferencia en cuestión). Entonces, si uno considera la disposición de las casas que tenga una en el centro y las otras \( n-1 \) formando un polígono regular de \( n-1 \) lados inscrito sobre la circunferencia, va a resultar que siga el camino que siga, para esta disposición de las casas va a caminar más que si tuviera un polígono regular de \( n \) lados inscrito sobre la circunferencia (caso en el que, estamos de acuerdo, el camino más corto sería recorrerlas dibujando el polígono sin un lado), porque en este nuevo caso la distancia entre dos casas cualesquiera es mayor que los lados del polígono regular de \( n \) lados inscrito sobre la circunferencia, o sea que cada uno de los \( n-1 \) tramos que tiene que recorrer, sea entre las casas que sea, va a ser mayor que el que recorría para la otra disposición, dando una distancia total recorrida mayor para cualquier orden (en particular, el óptimo).

Pero lo pensé un poco, y me parece que (para los \( n \) que satisfacen lo que pido, que supongo que será a partir de \( 6 \) o algo por el estilo) esta nueva disposición de las casas es un buen candidato para satisfacer lo que buscamos. Y para los \( n \) menores, el polígono regular de \( n \) lados sigue siendo la opción más convincente.

PD: Si llegara a aparecer un \( n \) para el que cada lado del polígono regular de \( n \) lados inscrito sobre la circunferencia midiera igual al radio, está claro que esta nueva disposición (con una casa en el centro y las otras \( n-1 \) en el borde) también se aplicaría, dando una distancia total recorrida para el camino óptimo que es estrictamente mayor que la que teníamos para la otra disposición (con las \( n \) casas formando un polígono regular inscrito sobre la circunferencia).

[pepito]

Pero lo pensé un poco, y me parece que (para los \( n \) que satisfacen lo que pido, que supongo que será a partir de \( 6 \) o algo por el estilo) esta nueva disposición de las casas es un buen candidato para satisfacer lo que buscamos.

Tampoco, porque si \( n \) cumple que los lados del polígono regular de \( n \) lados inscrito sobre la circunferencia miden menos (o igual) que \( \frac{2r}{3} \), uno puede poner dos casas sobre la línea que marca el diámetro del círculo (dividiendo dicha línea en tres partes iguales) y las otras \( n-2 \) formando un polígono regular inscrito sobre la circunferencia. Así se consigue una disposición que te hace caminar más que si están las \( n \) en el borde. Así que a ésta habría que compararla con la última que propuse. Y después, si uno quiere que tres casas no queden en el borde (supongo que formando un triángulo equilátero cuyo centro coincide con el círculo), o cuatro (formando un cuadrado, también centrado), hay que ver cuál es el \( n \) que lo "permite", pero es casi seguro que existe.

Esto es mucho más complicado de lo que parece (bah, ya parecía bastante complicado desde el vamos). Para mí que en realidad el enunciado decía que todas las casas están en la circunferencia, y no en su interior, y que lo único que querían era que les hagas un par de cuentas para justificar que el polígono regular es el peor caso. Ésta es mi nueva conjetura 

[Luis Fuentes]

Hola

 Tienes razón pepito, pero.... mmmmm....me cuesta creer que no haya una configuración óptima, digamos, suficientemente simétrica como para formalizarla, más allá de las pruebas. Habrá que seguir pensando.

Saludos.