El león y el de las cebras

Question

El león juega un juego mortal en contra de un grupo de $N$ cebras que se lleva a cabo en la estepa (= un plano infinito). El león se inicia en el origen de coordenadas $(0,0)$, mientras que el $N$ cebras puede arbitrariamente escoger a sus posiciones de partida. El león y el grupo de cebras mueven alternativamente:

• En león se mueven, el león se mueve desde su posición actual a una posición en la mayoría de los 1 unidad de distancia.
• En las cebras mover, una de las cebras se mueve desde su posición actual a una posición en la mayoría de los 1 unidad de distancia.

El león gana si por cualquier $\varepsilon\gt 0$, se puede obtener dentro de $\varepsilon$ de una cebra en un número finito de movimientos. De lo contrario, las cebras ganar.

Que solo hay 2 posibilidades:

1. Las cebras ganar para todos los $N\geq 1 $.
2. $\exists M$, de tal manera que el león gana para todos los $N\geq M$.

Posibilidad que es verdadero? (Heurísticas son bienvenidos también)

---

Fuente: he encontrado este pequeño y encantador juego de aquí, donde el caso de $N=100$ se discute, pero no es concluyente. Puede que también desee comprobar este, donde las cebras han demostrado tener una estrategia ganadora si el $\varepsilon$ el requisito se cae (es decir, el león necesita para capturar realidad de una cebra para ganar en lugar de sólo hacer dentro de $\varepsilon$ a).

---

Editado la pregunta siguiente Ycor del consejo en el comentario.

Answer 1

Las cebras ganar para todos los $N$.

Yo no me di cuenta de Lawrence respuesta en la fuente es en realidad el sonido (o eso creo, cuando me tomó algún tiempo para leer a través de esta mañana). A continuación me básicamente adoptar Lawrence estrategia para $N$, con dibujos esquemáticos para hacer el argumento más fáciles de seguir.

La siguiente es una buena posición de partida para las cebras.

donde $a$ es la distancia, que será determinado, en el que las cebras son capaces de mantener el león de distancia. Cada carril es de anchura $4+2a$ con cebras centrado horizontalmente.

Estrategia para las cebras:

Cada cebra mentalmente dibuja un cuadrado en el centro. Podemos especificar las cebras' estrategia para ganar en cada situación posible a continuación:

1. Si el león está en la frontera o fuera de la plaza, quedarse.
2. Tan pronto como el león es el interior de la plaza, pero fuera de la $2a$ franja marcada por el par de líneas punteadas (frontera incluido), zebra mover 1 unidad en posición vertical lejos de ella.
3. Tan pronto como el león es el interior de la plaza y la franja de líneas de puntos, cebra mover 1 unidad en posición vertical lejos de ella.

El león nunca gana por permanecer en la Situación de $1$ e $2$.

Estrategia en el marco de la Situación $3$

Situación 3 merece un mayor análisis, ya que allí la cebra no puede continuar indefinidamente sin que el león de cierre en el tiempo. Cuán lejos puede seguir antes de caer en el $a$ radio del león? La respuesta es que se puede ir por lo menos tan lejos como $L$, como se muestra a continuación:

Por Pythagorus, tenemos $L=1+\frac{1}{2a}$. Aviso de $L$ puede hacerse tan grande como queramos mediante el ajuste de $a$ en consecuencia. De curso $L$ tiene que ser un número entero por las cebras' estrategia se indicó anteriormente. Vamos a darle un margen muy amplio y puede ir por lo menos tan lejos como

$$L^{*}=L/2=\frac{1}{2}+\frac{1}{4a} \;\;\;\;\; (1)$$

Ahora, la idea de una estrategia en la situación 3 es este: la cebra elegir algún punto de $s$ vertical a lo largo de su ruta de escape (de longitud $L^{*}$), en la que se huye horizontalmente lejos de la de león. El punto de $s$ debe ser elegido de modo que todas las otras cebras son suficientemente lejos de este horizontales ruta de escape. En ese caso, si el león cambios de destino durante su horizontales de búsqueda, los escaper sería capaz de escapar al centro de un desocupado vertical de carril antes de que el león llega a la nueva meta de la plaza, lo que obligó a que el juego volver a la situación de $1$.

Cómo se consigue esto? Aviso a escapar hacia el centro de la más cercana desocupado lane, una cebra tendrá que cruzar una distancia en la mayoría de las $N(4+2a)$. Vamos a tomar

$$L^{*}=2N(N(4+2a)+2+2a) \;\;\;\;\;(2)$$

Luego, por el principio del palomar, existe $s$ a lo largo de la vertical de la ruta de escape cuyo más cercano distancia vertical a otra cebra es, al menos, $\frac{L^{*}}{2N}=N(4+2a)+2+2a$. Si la cebra gira y huye horizontalmente en esta $s$, el león será, al menos, $N(4+2a)$ distancia vertical desde cualquier otra cebra de la plaza, como se muestra a continuación.

Y ya está! Si el león mantiene su posición horizontal de la captura, la cebra sigue funcionando. La distancia horizontal entre la pareja siempre será mayor que $1/2$ (por $(1)$). Si el león interruptores de destino durante esta persecución, no puede llegar a su nuevo destino de la plaza antes de la edad de destino alcanza el centro de un desocupado vertical del carril, como se muestra arriba.

La solución de $(1)$ e $(2)$ da

$$a= \frac{\sqrt{256N^4 + 256N^3 + 48N^2 +1} + 1 - 16N^2 - 8N}{16(N^2 + N)}$$

El león no será capaz de obtener dentro de este radio de cualquier cebra.

---

Si mi cálculo es correcto, por el ensanchamiento de la calle (y la ampliación de las plazas en consecuencia), las cebras pueden mantener el león en forma arbitraria a gran distancia. Vamos a tomar el tamaño de la calle y las plazas para ser $2k+2a$, ecuaciones $(1)$ e $(2)$ se convierte en

$$L^{*}=\frac{(a + k - 1)^2 - a^2}{4a}\;\;\;\;\;\;\;\;\;\;\;\;\; (1)'$$

$$L^{*}=2N(N(2k+2a)+k+2a)\;\;\;(2)'$$

La solución de $(1)'$ e $(2)'$ para $a$ hemos

$$a=\frac{\sqrt{q} + k - 8kN^2 -4kN - 1}{16N(N + 1)}$$

donde

$$q= 64k^2N^4 + 64k^2N^3 + 16k^2N^2 + 8k^2N + k^2 - 16kN^2 - 24kN - 2k + 16N^2 + 16N + 1$$

Claramente, $\displaystyle{\lim_{k \to \infty} a(N,k) = \infty}$.

Así que parece que este juego es realmente sesgada a las cebras lado".

Answer 2

EDIT: El argumento de abajo está mal - me supone que todas las cebras pueden mover cada turno.

Lo que sobre el juego con una cebra y un león, en la recta real?

La cebra, a continuación, se mueve a una unidad de distancia del león en cada paso, y el león nunca puede disminuir la partida de distancia. La cebra nunca se $\epsilon$-atrapado.

Ahora, para muchos las cebras, que se puede restringir el de zebra para moverse solamente en el rayo definido por las cebras posición original y el origen, y cada uno de cebra se trate de ganarle a los "leones de la sombra" dado por su posición proyectada orhtogonally en el rayo. Claramente, si el león puede $\epsilon$-captura de una cebra en el avión, su sombra también debe $\epsilon$-captura de la cebra.

Pero el argumento anterior muestra que una cebra puede huir de la sombra, ya que si el león se mueve distancia $d$, entonces su sombra se mueve a mayor distancia $d$ en el rayo.

Por lo tanto, la cebra, siempre tiene una estrategia ganadora.