Estrategia general más rápida para la reunión del pueblo

Question

Aquí hay un problema, que ni yo ni mis amigos (muy experimentados en resolver cosas como esta) podemos resolver. Pero se utilizó para una competencia hace varios años y un tipo lo resolvió allí, al menos eso sé. Desafortunadamente, la solución (y el tipo) está perdido.

Tienes un pueblo. Tiene forma de un cuadrado de 1 por 1. El jefe vive en el centro exacto del cuadrado. Las demás casas están dispersas por toda el área del pueblo, y solo hay una persona por casa. Hay un número finito de casas, todas tienen tamaño 0 y todos son conscientes de su ubicación.

El jefe necesita organizar una reunión que recoja a todos los aldeanos. Para hacer esto, va a alguna otra casa y habla sobre la reunión, luego va a otra, etc. Por supuesto, cada aldeano se garantiza estar en su casa; una vez informado, puede participar en la reunión o ir al lugar de la reunión en la casa del jefe. Todos viajan a la velocidad de 1 y no toma tiempo informar a alguien, una vez que has llegado a su casa.

Necesitas encontrar el tiempo mínimo $T_{\text{MinMax}}$ en el que todos los aldeanos (incluido el jefe) pueden ser recogidos en el centro del pueblo, independientemente de su número y ubicación inicial.

La respuesta debe venir junto con una prueba, es decir, necesitas:
a) proporcionar una estrategia (quién va a dónde) y demostrar que funcionará para cualquier pueblo en un tiempo $t \le T_{\text{MinMax}}$
b) demostrar que para todas las demás estrategias debe haber un pueblo que "se recolectará" en un tiempo $t \ge T_{\text{MinMax}}$.

¿Alguien aquí puede resolverlo?

Puedes estar seguro de que $T_{\text{MinMax}} < \infty$. Por ejemplo, la siguiente estrategia funciona en $T_{\text{Max}} < 3\sqrt{5}+3\sqrt{2}/2$:
1) El área del pueblo se divide en 4 subáreas cuadradas de 0,5 por 0,5.
2) El jefe va a la casa más cercana en una subárea y asigna a su anfitrión como sub-jefe y le pide que haga la misma estrategia en su subárea.
3) Luego el jefe va a otra subárea vecina y hace lo mismo. Y repite esto con el resto de las 2 subáreas.
4) El jefe regresa al centro del pueblo.
5) Si alguna subárea no tiene casas en su interior, el jefe simplemente la omite.
Digamos que en el peor de los casos tomará tiempo $X$. Luego para los sub-jefes tomará tiempo $X/2$. El primer sub-jefe se asigna en un tiempo máximo de $\sqrt{2}/2$, el siguiente en $\sqrt{2}/2+\sqrt{5}/2$ y el último en $\sqrt{2}/2+3\sqrt{5}/2$. Luego en el tiempo $\sqrt{2}/2+3\sqrt{5}/2+X/2$ se recoge la última subárea en su centro y en $\sqrt{2}/4$ tiempo puede estar en el centro del pueblo. Lo que significa que $X < \sqrt{2}/2+3\sqrt{5}/2+X/2+\sqrt{2}/4$. Entonces $T_{\text{Max}} = X < 3\sqrt{5}+3\sqrt{2}/2$.

Es fácil probar que $T_{\text{MinMax}} \ge 2+\sqrt{2}$ (considera un pueblo con 4 casas en las esquinas), y estoy casi seguro que $T_{\text{MinMax}} = 2+\sqrt{2}$, fue el resultado de ese tipo de la competencia.

Answer 1

Esto no es una respuesta completa, sino una prueba de que una estrategia parcial lo suficientemente buena para "pocos" aldeanos es suficiente.

Si los aldeanos solo se encuentran en dos grupos en dos esquinas opuestas del cuadrado, entonces la mejor (y única) estrategia toma un tiempo $2\sqrt 2 < 2+\sqrt 2$.

Supongamos que tienes una estrategia no necesariamente óptima que toma un tiempo de hasta $T \ge 2+\sqrt 2$ para resolver cualquier cuadrado. (sabemos que estas existen por el argumento de dividir y conquistar presentado en la pregunta)

Si puedes alcanzar a $n^2-1$ personas suficientes en un tiempo $\frac 12 \sqrt 2 + \varepsilon$, entonces puedes separar el cuadrado en $n^2$ cuadrados pequeños, usar la estrategia en los cuadrados pequeños, luego regresar al centro, lo que te da una estrategia con un tiempo total de $(\frac 12 \sqrt 2 + \varepsilon) + (1- \frac 1{2n})\sqrt 2 + \frac 1n T + (\frac 12 - \frac 1 {2n}) \sqrt 2$.

A medida que $n \to \infty$, esto converge a $2\sqrt 2 + \varepsilon.
Bajo la suposición de que dado suficientes personas en el cuadrado puedes hacer que $\varepsilon$ converga a $0$, puedes comenzar con cualquier estrategia razonable y convertirla en una nueva estrategia cuyo peor tiempo converge a $2\sqrt 2$ a medida que el número de aldeanos aumenta.

Y de los ejemplos anteriores de peor caso, sabemos que $2\sqrt 2$, y el tiempo $\frac 12 \sqrt 2 + \varepsilon$ son los mejores posibles.

---

Ahora voy a demostrar que si tienes suficientes personas en el cuadrado, entonces puedes alcanzar a $N$ aldeanos en cerca de $\frac 12 \sqrt 2$ tiempo.

Supongamos que tienes $N$ aldeanos ubicados en una pequeña franja rectangular de longitud $\frac 12 \sqrt 2$ y ancho $w$ y el jefe comienza en el centro de una de las extremidades de la banda.

Luego, visitando a cada aldeano en orden y ramificándose, puedes alcanzarlos en un tiempo de a lo sumo $\frac 12 \sqrt 2 + (\frac 12 + \lfloor \log_2(N) \rfloor )w$: la cantidad de "zigzagueo" necesaria se distribuye a todos los aldeanos gracias a la ramificación.

Finalmente, dado que el rectángulo "cubre" un ángulo de $2\arctan (w/\sqrt 2)$, puedes cubrir un círculo entero de radio $\sqrt 2/2$ con $\lceil \pi / \arctan (w / \sqrt 2) \rceil$ rectángulos.

Por lo tanto, si hay $\lceil \pi / \arctan (w / \sqrt 2) \rceil (N-1)+1$ aldeanos en total, entonces por el principio de los palomos hay una franja que contiene $N$ de ellos, y así hay una forma de alcanzar a $N$ aldeanos en un tiempo de $\frac 12 \sqrt 2 + (\frac 12 + \lfloor \log_2(N) \rfloor )w$

---

Tomando $n=5$ y $T = 2+\sqrt 2$ obtenemos una estrategia recursiva que funciona en un tiempo de $2+\sqrt 2$ siempre que podamos alcanzar a $24$ personas en un tiempo de $(16-5\sqrt 2)/10 = 0.892893\ldots$

Para lograr esto necesitamos bandas con un ancho $w = (8/5-\sqrt 2)/(\frac 12+4) = (16/5 - 2\sqrt 2)/9 = 0.041286\ldots$

Por lo tanto, necesitamos $108$ bandas, y finalmente $2485$ aldeanos.

Si puedes idear una estrategia que funcione en un tiempo de $2+\sqrt 2$ para hasta $2484$ aldeanos, entonces este método te da una estrategia que siempre funciona en este tiempo.

Answer 2

Primero daré el algoritmo y luego la prueba.

1. El jefe va a la casa más cercana a él.
2. El jefe nombra al villager de esa casa como jefe temporal.
3. Ambas personas en la casa luego van a las dos casas más cercanas que tienen un villager no notificado al que nadie más va a visitar (es decir, si dos jefes están más cerca de la misma casa, el más cercano la obtendrá) y nombran jefe temporal a cada villager que encuentran.
4. El último paso se repite hasta que no haya más casas a las que ir. Por ejemplo, si hay cinco casas además de la casa del jefe, el jefe iría a la primera casa, luego irían a las seguna y tercera casas, y luego dos de las tres personas irían a la cuarta y quinta casa, pero una de ellas iría al centro del pueblo.

Como señalaste con las casas en las cuatro esquinas, $T_{MinMax}\ge2+\sqrt2$. Sin embargo, debido a la naturaleza ramificada de este problema, agregar otra persona generalmente reduce el tiempo que lleva. Considera de nuevo las cuatro casas, pero esta vez, agrega otra casa directamente al norte de la casa del jefe. Con este algoritmo, el jefe visitará esta casa al norte, luego se dividirá para visitar las esquinas superiores, luego una de las dos personas actualmente en cada una de las esquinas superiores irá directamente al sur hacia las dos personas restantes y las otras dos personas que han sido visitadas irán directamente al centro del pueblo. Esto tomará un tiempo total de $\frac12+\frac12+1+\frac{\sqrt2}2=2+\frac{\sqrt2}2$. Ahora, realmente podrías poner esa quinta casa en cualquier lugar y seguiría produciendo algo menor que $2+\sqrt2$. Para ver esto, dibuja el camino original, agrega otra casa y dibuja una nueva casa. Deberías poder ver que el camino original es más largo que el nuevo camino.

Básicamente, esto es una prueba por inducción. Hay dos casos cuando agregas una casa:

Caso 1: Para cuando llegas a la casa extra en el algoritmo, tienes suficientes personas para cubrir la casa extra sin perder tiempo. Esto sería en el caso con seis o siete casas, ya que en lugar de que las dos personas en las esquinas regresen al centro del pueblo, irían a recoger a otras personas. Sabemos que no añadirán tiempo por la desigualdad triangular, ya que el punto donde se encuentran y las dos casas forman un triángulo y siempre será más rápido que se separen y visiten ambos lugares que uno vuelva al pueblo y la otra persona se encargue de ambos.

Caso 2: La casa extra introduce un punto de ramificación, como en el caso con cinco casas como se detalló anteriormente. En este caso, agregar una casa extra puede disminuir el tiempo si se coloca cerca del comienzo de la ejecución y aumentarlo si se coloca al final de la ejecución. Cuanto más cerca coloques ese primer punto de ramificación del centro del pueblo, más tiempo ahorrarás, pero al hacerlo te permites más espacio para colocar esa última casa de ramificación, lo que te permite aumentar el tiempo. Cuanto más lejos lo pongas del centro del pueblo, menos tiempo ahorrarás, pero no tendrás que desviarte tanto porque la última casa debe estar más cerca de la última esquina.

Siento como si me estuviera perdiendo algo, así que si alguien ve algún error, por favor házmelo saber.