Escapando de infinitos perseguidores

Question

El fugitivo se encuentra en el origen. Se mueve a una velocidad de 1. Hay un guardia en cada coordenada entera excepto en el origen. La velocidad de un guardia es de 1/100. El fugitivo y los guardias se mueven simultánea y continuamente. En todo momento, los guardias solo se mueven hacia la posición actual del fugitivo, es decir, la trayectoria de un guardia es una curva de persecución. Si están dentro de una distancia de 1/100 de un guardia, el fugitivo es atrapado. El juego se desarrolla en $\mathbb{R}^2$.

¿Puede el fugitivo evitar ser capturado para siempre?

---

Lo que sé:

1. La distancia entre dos guardias siempre es no decreciente, pero mientras más lejos estén del fugitivo, más lento disminuye esa distancia.

2. Si el fugitivo corre en línea recta, siempre será atrapado por algún guardia lejano. Por ejemplo, si el fugitivo comienza en $(0.5, 0)$ y corre hacia el norte, será atrapado por un guardia a unos $(0, \frac{50^{100}}{4})$. Consulta radiodrome para el cálculo.

3. Si solo hay 2 guardias a una distancia de 1 entre sí, entonces el fugitivo siempre puede encontrar un camino para pasar entre ellos de forma segura. Esto es cierto independientemente de la distancia y las posiciones relativas de la pareja con respecto al fugitivo.

4. El fugitivo puede escapar si está simplemente "encerrado" por guardias que están a una distancia de 1 entre sí:

La forma de la cerca no tiene que ser rectangular. Los círculos u otras formas tampoco impiden la fuga, independientemente del tamaño.

---

3 y 4 no son triviales, pero se pueden demostrar mediante argumentos geométricos solos sin cálculos. Para evitar saturar la pregunta innecesariamente, más detalles se proporcionan como respuesta a continuación para aquellos que estén interesados, con suerte, serán instrumentales para resolver el problema original.

Answer 1

Como se solicitó en los comentarios anteriores, aquí está el código de mathematica que generó esto:

Podría proporcionar alguna idea. Utilicé un análogo discreto de la curva de persecución en la que por cada cuarto de paso de unidad que hacen los perseguidores (o cualquier proporción que elijas), el fugitivo da un paso de unidad a un punto en la circunferencia del círculo unitario alrededor del fugitivo que maximiza la brecha entre él y sus perseguidores. Código modificado a partir de aquí.

Obviamente, la densidad de perseguidores aumenta con el tiempo. Mientras que una ruta de escape en línea recta de la trama de la distancia entre el fugitivo y sus perseguidores está estrictamente disminuyendo

una trama de la distancia entre el fugitivo y sus perseguidores para la estrategia de evasión local es, a primera vista, no:

Sin embargo, esto es probablemente engañoso, ya que este análogo discreto oculta el camino continuo que en algún momento, sin duda, pasará dentro de los parámetros restringidos:

Answer 2

Pruebas para los puntos 3 y 4 en la pregunta.

Prueba para el punto 3

Denotemos a los dos guardias y al fugitivo por $G_1$, $G_2$ y $F$, respectivamente. Si $\angle FG_1G_2\leq\pi/4$ en el tiempo $0$, entonces es posible escapar porque:

Si $F$ se desplaza hacia $G_1$ a lo largo del eje y, $G_2$ siempre estará dentro de la intersección en forma de ojo de dos círculos antes de que $F$ alcance $G_3$, porque la distancia entre cualquier par de guardias no aumenta. Entonces la distancia entre $G_1$ y $G_2$ será mayor que $\sqrt2-1$ cuando $F$ alcance $G_3$. Para un radio de seguridad de 1/100 y una relación de velocidad de 100, el fugitivo puede escapar fácilmente entre $G_1$ y $G_2$.

¿Qué sucede si $\angle FG_1G_2\gt\pi/4$? Consideremos el caso extremo donde $\angle FG_1G_2=\pi/2$ en el tiempo $0$. Supongamos que $G_1(0)=(0,n)$ y $G_2(0)=(1,n)$. Observa que si el fugitivo corre hacia la izquierda, el segmento $G_1G_2$ se inclinará en sentido antihorario, como se ilustra a continuación:

Entonces, si el fugitivo corre en sentido horario a lo largo del arco del círculo de radio n centrado en $G_1(0)$, $\angle FG_2G_1$ será menor que $\pi/4$ cuando el fugitivo haya recorrido una distancia de $n\pi/4\approx n$. Dado que la relación de velocidad es 100, la pareja ha recorrido como máximo alrededor de $n/100$ y aún están a unos $99n/100$ de distancia, lo que significa que la distancia entre $G_1$ y $G_2$ se ha reducido como máximo alrededor del 1% en este tiempo. Ahora, el fugitivo puede correr directamente hacia $G_2$ y escapar a través de la pareja como se explicó en el primer párrafo.

De hecho, ¡hay una estrategia aún mejor! Observa que $F$, $G_1$ y $G_2$ serán colineales en algún momento antes de que el fugitivo haya recorrido una distancia de $n\pi/2\approx 2n$. Para este momento, la pareja de guardias ha recorrido como máximo $n/50$ y aún están a unos $49n/50$ de distancia, lo que significa que la distancia entre $G_1$ y $G_2$ se ha reducido como máximo alrededor del 2%. Dado que el trío es colineal, la brecha entre los guardias permanecerá constante en aproximadamente 0.98 si el fugitivo corre directamente hacia ellos. Eso es más que suficiente espacio para que el fugitivo se escape a su propio ritmo. $\blacksquare$

Prueba para el punto 4

Supongamos que los guardias rodean al fugitivo con un círculo de radio $R$. El fugitivo se mueve directamente hacia algún guardia. Cuando están cerca del guardia, digamos a una distancia de 1, el fugitivo se desvía a la derecha y pasa tangencialmente a cada guardia manteniendo una distancia de aproximadamente 1, como se ilustra esquemáticamente a continuación

Ahora, a medida que el fugitivo realiza su movimiento en sentido horario, la distancia entre un par de guardias más cercanos a él no puede ser mayor a aproximadamente 0.04 para que el objetivo no escape. Dado que la distancia entre los guardias no aumenta, cuando el fugitivo completa un ciclo completo, la distancia entre cualquier par de guardias adyacentes no es mayor a 0.04. Pero esto es imposible dado que el fugitivo ha recorrido no más de $R+2\pi R \approx 7R$. Debido a que dada la relación de velocidad de 1:100, cada guardia ha recorrido no más de $\frac{7}{100}R$. Esto significa que cada guardia todavía está al menos a $\frac{93}{100}R$ de distancia del origen. Por lo tanto, la distancia promedio entre dos guardias adyacentes es al menos $\frac{93}{100}$. Una contradicción. $\blacksquare$

Answer 3

Creo que el fugitivo puede evadir la captura indefinidamente. Aquí están mis pensamientos, que quizás puedan ser mejorados por alguien más.

Considera una variación del problema: el fugitivo comienza en (0,0) pero hay aproximadamente $2\pi R$ guardias uniformemente distribuidos alrededor de un círculo centrado en el origen de radio $R$, de manera que los guardias adyacentes están separados por ~1 unidad. También supongamos que los guardias se mueven hacia el origen en lugar de hacia el fugitivo. (Como observa un comentarista, esto ya es básicamente el caso para guardias muy distantes.)

Supongamos que el fugitivo corre a 100 unidades/s en línea recta. Entonces el prisionero intercepta el círculo de guardias después de aproximadamente $R/100$ segundos, momento en el que el círculo de guardias tiene un radio aproximado de $\frac{99}{100} R$. La brecha entre guardias adyacentes es ahora de 99/100 unidades, lo que permite que el fugitivo se escape fácilmente. Observa que esta cantidad es independiente del radio inicial $R$.

Ahora supongamos que hay círculos de guardias de radio 1, 2, 3, ... y en cada círculo, los guardias adyacentes están separados por 1 unidad. La distancia entre un par de guardias en diferentes círculos concéntricos es siempre de al menos 1, por lo que el fugitivo puede moverse libremente en los espacios entre los círculos concéntricos. Además, dado que el fugitivo puede pasar fácilmente un círculo de radio arbitrario, puede pasar fácilmente todos los círculos y evadir la captura.

Esta configuración de círculos concéntricos es interesante porque los guardias están inicialmente distribuidos con la misma distribución y densidad que en el problema original. También sigue siendo el caso de que en cada momento, la densidad de guardias alrededor de la posición del fugitivo está aumentando. Pero el fugitivo tiene una estrategia de escape fácil, y de hecho, en ningún momento está cerca de ser capturado.

Me parece que disponer los guardias en círculos concéntricos es esencialmente lo mismo que disponerlos en puntos de una red, ya que no hay nada especial acerca de las coordenadas enteras. También conjeturo que el análisis anterior no cambia significativamente si los guardias se mueven hacia el prisionero en lugar de hacia el origen.

La idea clave en este problema es que el fugitivo será atrapado si queda rodeado por una nube de guardias de densidad crítica (es decir, una nube de guardias con más de un guardia por ~0.01 unidades cuadradas). Pero los guardias comienzan con una distribución de baja densidad, y todos se mueven como uno hacia el fugitivo, por lo que su densidad aumenta muy lentamente; de hecho, su densidad aumenta más lentamente cuanto más lejos están del fugitivo. Por lo tanto, el fugitivo siempre puede pasar antes de que hayan tenido tiempo de acumular suficiente densidad.