Encontré el siguiente juego. Migraré esto según lo solicitado.

• Un error es visitar círculos, y un adversario desea maximizar su tiempo de viaje.

• El adversario coloca un círculo en cada turno.

• El error camina desde su posición actual directamente hacia el centro del círculo más nuevo, luego se detiene cuando encuentra el interior del círculo (por lo tanto: no camina si se juega un círculo cubriendo su ubicación). Este es el turno del insecto.

• Hay círculos disponibles para el adversario.$N$

• Cada círculo posterior tiene un radio menor que el círculo anterior.

• Cada círculo debe intersecar la intersección de todos los círculos jugados anteriormente. Es decir, todos los círculos deben tener una intersección común una vez que se juegan todos.

EDITAR: El adversario es libre de elegir los radios de los círculos, sujeto a la restricción de que los radios disminuyan monotónicamente.

Preguntas y respuestas:

1. ¿Está limitada la distancia como ? $N\to\infty$R: No, esta respuesta da un ejemplo de una estrategia adversaria.
2. ¿Cuál es la distancia máxima que debe recorrer el insecto durante la reproducción de círculos? $N$A: crece en , por la misma respuesta.$\Theta(\log(N))$

Variante 2 : el error camina directamente hacia la intersección de los dos círculos jugados más recientemente .

ACTUALIZACIÓN: Esta variante se abordó, bajo el supuesto de que el error solo puede recordar los últimos 2 círculos jugados aquí . El resultado fue nuevamente una distancia ilimitada.

¿Qué impacto tiene la memoria sin límites ? es decir, el error va a la intersección de todos los círculos jugados anteriormente . Esto produjo un límite "suelto" de , donde es el diámetro del primer círculo. Obviamente no puede ser menos que esto. Ver aquí . El límite superior actual era . Esto se obtuvo al aproximar el camino del peor de los casos como un recorrido por círculos progresivamente más pequeños. Se demostró que el error siempre avanza hacia la intersección final, reduciendo así la distancia del siguiente paso que debe recorrer.$O(d)$$d$$1000\times d$

Sospecho que la distancia recorrida es una pequeña constante por la circunferencia del primer círculo, pero actualmente no puedo proporcionar una buena prueba.

Esta respuesta tiene dos partes, juntas que muestran que el límite correcto es :$\Theta(\log N)$

1. Un límite inferior de (multiplicado por el radio del primer círculo).$\Omega(\log N)$
2. Un límite superior coincidente de .$O(\log N)$

Límite inferior de $\Omega(\log N)$

Considere dos círculos unitarios que se tocan en un punto . (Ver abajo; p está a la derecha, el error comienza a la izquierda). Alterna entre un círculo y el otro. El error viajará hacia arriba y hacia abajo en zigzag a través de la grieta entre los dos círculos, moviéndose principalmente hacia arriba y hacia abajo, pero también progresando lentamente hacia la derecha. Si hice la trigonometría correctamente, después de N pasos, la distancia desde el punto común será Θ ( 1 / $p$$p$$N$, y laNº paso hará que el error de caminarΘ(1/N), para una distancia total deΘ(logN).$\Theta(1/\sqrt N)$$N$$\Theta(1/N)$$\Theta(\log N)$

Aquí hay un bosquejo de los cálculos. Considere algunos dos pasos consecutivos que realiza el error. Va de algún punto , a b , a c . Puntos a y c son en el mismo círculo; el punto b está en el otro círculo. Vamos o ser el centro del círculo que una está encendido. Considere los siguientes tres triángulos, en orden decreciente de tamaño:$a$$b$$c$$a$$c$$b$$o$$a$

1. El triángulo isoceles (recordar p es el punto común).$\triangle oap$$p$
2. El triángulo .$\triangle abp$
3. El pequeño triángulo $\triangle abc$

Estos triángulos son casi similares (es decir, escala de módulo congruente). Más precisamente, para , los tres tienen la siguiente propiedad: la relación entre la longitud del tramo corto y el tramo largo es Θ ( ϵ ) . (No probaré esto con más detalle aquí, pero tenga en cuenta que ϵ → 0 a medida que el insecto camina, y al perturbar un vértice en cada triángulo en una cantidad insignificante, los triángulos se pueden hacer similares).$\epsilon = |ap|$$\Theta(\epsilon)$$\epsilon\rightarrow 0$

Las largas piernas y P o del primer triángulo tiene longitud 1. Su pierna corta | a p | tiene longitud ϵ . El segmento a p es un tramo largo del segundo triángulo, de modo que el tramo corto del triángulo a b tiene una longitud Θ ( ϵ 2 ) . El segmento a b es un tramo largo del tercer triángulo, de modo que el tramo corto del triángulo a c tiene una longitud Θ ( ϵ 3 ) . Por lo tanto, en estos dos pasos que toma el error:$co$$po$$|ap|$$\epsilon$$ap$$ab$$\Theta(\epsilon^2)$$ab$$ac$$\Theta(\epsilon^3)$

1. La distancia el error viaja es Θ ( ϵ 2 ) .$|ab|+|bc|$$\Theta(\epsilon^2)$
2. La distancia desde el error hasta el punto común disminuye de ϵ a ϵ - Θ ( ϵ 3 ) .$p$$\epsilon$$\epsilon-\Theta(\epsilon^3)$

Definir tiempo sea el número de pasos antes de ε t ≈ 1 / 2 k . Por (2) arriba, ϵ disminuye en un factor constante después de aproximadamente steps ( 1 / ϵ 2 ) pasos, entonces t k + 1 = t k + Θ ( 2 2 k ) = t k + Θ ( 4 k ) . Por lo tanto, t k = Θ ( 4 $t_k$$\epsilon_t \approx 1/2^k$$\epsilon$$\Theta(1/\epsilon^2)$$t_{k+1} = t_k + \Theta(2^{2k}) = t_k + \Theta(4^k)$ . Esto es, después de theta ( 4 k ) pasos, la distancia desde el fallo hasta el punto común p será de aproximadamente 1 / 2 k . Cambiando variables, después de N pasos, la distancia desde el error al punto común será ϵ = Θ ( 1 / $t_k = \Theta(4^k)$$\Theta(4^k)$$p$$1/2^k$$N$. Y, en elNº paso, el insecto viajaΘ(ε2)=Θ(1/N). Así la distancia total recorrida en los primerosNpasos esΘ(1+1/2+1/3+...+1/N)=Θ(logN).$\epsilon = \Theta(1/\sqrt N)$$N$$\Theta(\epsilon^2) = \Theta(1/N)$$N$$\Theta(1+1/2+1/3+...+1/N) = \Theta(\log N)$

Este es el límite inferior.

Se extiende a la Variante 2 propuesta (según tengo entendido), de la siguiente manera:

Agregar la restricción de que el error debe moverse al punto más cercano en la intersección de los dos círculos colocados más recientemente no ayuda. Es decir, el límite inferior de anterior todavía se aplica. Para ver por qué, modificaremos el ejemplo anterior agregando un solo círculo extraño que permita que el error cumpla con la restricción mientras sigue el mismo camino:$\Omega(\log N)$

Los círculos verde y azul son los dos círculos del ejemplo anterior. La intersección señala y b son los mismos una y b como en el ejemplo anterior. El círculo rojo es el nuevo círculo "extraño". La secuencia anterior alternaba entre los círculos azul y verde. La nueva secuencia será esta secuencia, pero con el círculo rojo agregado antes de cada círculo en la secuencia anterior: rojo, azul, rojo, verde, rojo, azul, rojo, verde, rojo, azul, ...$a$$b$$a$$b$

Supongamos que el fallo está sentado en después de azul se coloca. El siguiente círculo colocado es rojo. El rojo contiene el error, por lo que el error no se mueve. El siguiente círculo colocado es verde. Ahora el error se mueve a b (que es el punto más cercano en la intersección de los círculos verde y rojo). Al repetir esto, el error viaja como antes.$a$$b$

Límite superior de $O(\log N)$

Solo bosquejo la prueba.

Arregla cualquier secuencia de círculos. Argumentaremos que como , la distancia total recorrida por el error en los primeros N pasos es O ( log N ) . Suponga sin pérdida de generalidad que el primer círculo tiene radio 1.$N\rightarrow \infty$$N$$O(\log N)$

Arregle una arbitrariamente grande . Sea p por cualquier punto en la intersección de los primeros N círculos. Tenga en cuenta que debido a la forma en que se mueve el error, en cada paso que se mueve el error se acerca a la p .$N$$p$$N$$p$

Primero, considere los pasos donde la siguiente relación es al menos : la reducción en la distancia a $1/\log N$ La distancia total recorrida en dichos pasos esO(logN), porque la distancia total recorrida en dichos pasos esO(logN)multiplicada por la distancia inicial ap. Así que sólo tenemos que acotar la distancia total recorrida en los otros pasos --- aquellos en los que esta relación es como máximo de1/logN.

Primero, argumentamos algo ligeramente más débil: que la distancia total recorrida en tales pasos antes de que el radio del círculo disminuya a 1/2 o menos es . (Mostramos más tarde que esto es suficiente para dar el límite).$O(\log N)$

Considere cualquiera de esos pasos. Deje y b , respectivamente, denotar las ubicaciones del error antes y después del paso. Deje o denotar el centro del círculo actual. Deje b ′ denotar el punto en el rayo → p b tal que | p a | = | p b | :$a$$b$$o$$b'$$\overrightarrow{pb}$$|pa| = |pb|$

Considere los siguientes triángulos:

1. $\triangle opb$
2. $\triangle pba$
3. $\triangle abb'$

Por argumentos geométricos similares a los del límite inferior, para algunos , cada uno de estos triángulos tiene dos patas largas y una pata corta, y la proporción (para cada triángulo) de la longitud de la pierna corta a la longitud de la pierna larga es Θ ( ϵ ) : | b b ′ $\epsilon$$\Theta(\epsilon)$

Esta ecuación y la suposición de que , Que es el radio del círculo, está en [ 1 / 2 , 1 ] implica que | a b | = Θ ( | p a | 2 / | b o | ) = Θ ( | p a | 2 ) , y luego eso | b b ′ | = Θ ( | a b $|bo|$$[1/2,1]$$|ab| = \Theta(|pa|^2/|bo|) = \Theta(|pa|^2)$ .$|bb'| = \Theta(|ab||pa|/|bo|) = \Theta(|pa|^3)$

Ahora nos centramos en la distancia del error a . Llámelo d antes del paso, y d ' después del paso. (Nota d = | p a | , d ′ = | p b | , y d - d ′ = | b b ′ | .)$p$$d$$d'$$d=|pa|$$d'=|pb|$$d-d' = |bb'|$

En este paso, esta distancia reduce en | b b ′ | , que según las observaciones anteriores es Ω ( d 3 ) .$d$$|bb'|$$\Omega(d^3)$

Por lo tanto, el número de pasos adicionales necesarios para reducir la distancia en un factor de 2 (a lo más ) es O ( 1 / d 2 ) . Las variables cambiantes, si d = 1 / 2 k , el número de pasos adicionales requeridos para llevar la distancia por debajo de 1 / 2 k + 1 es O ( 4 k ) . Dado que la suma es geométrica, el número total de pasos necesarios para llevar la distancia por debajo de 1 / 2 k es O $d/2$$O(1/d^2)$$d=1/2^k$$1/2^{k+1}$$O(4^k)$$1/2^{k}$ . Cambiando las variables nuevamente, después de n pasos, la distancia a p será O ( 1 / $O(1/4^k)$$n$$p$.$O(1/\sqrt n)$

Por último, recordando la ecuación muestra varios párrafos arriba, en el º paso, la distancia que el insecto se desplaza, es decir, | a b | , es O ( ( la distancia actual a  p ) 2 ) = O ( 1 / n ) . Por lo tanto, la distancia total recorrida en los primeros N dichos pasos mientras que el radio del círculo está en [ 1 / 2 , 1 ] es como máximo N Σ n = 1 O ( 1 $n$$|ab|$$O((\mbox{the current distance to } p)^2) = O(1/n)$$N$$[1/2,1]$

Por escalado, se concluye que, para cualquier , la distancia total recorrida mientras que el radio del círculo está en el intervalo [ 1 / 2 k , 1 / 2 k + 1 ] es O ( log ( N ) / 2 k ) . Sumando sobre k , la distancia total recorrida es O ( log N ) . QED$k$$[1/2^k, 1/2^{k+1}]$$O(\log(N)/2^k)$$k$$O(\log N)$

David E. conjeturó

"Maybe the answer would be different if the bug walked directly to the closest point in the current intersection, rather than towards the center of the new circle?"

(EDIT: Note that this is not the same as the "variant 2" at the end of the original poster's question.)

Here's a proof (more or less) of his conjecture (it is bounded in this case).

Lemma. For the variant suggested by David, the total distance traveled by the bug is always $O(d_0)$, where $d_0$ is the maximum distance between the bug and any point in the first circle placed.

proof. Assume WLOG that the final resting place is the origin $o$, and that the bug starts at distance 1 from $o$. For exposition assume the bug starts at time $0$, travels at unit rate (one inch per second), and stops only when it reaches the last disc placed. Note that (as explained further below) as the bug crawls its distance to the origin strictly decreases.

Partition the unit-radius disc (centered at $o$) into infinitely many rings by drawing concentric circles of radii $1, 0.99, 0.99^2, 0.99^3, \ldots$.

Claim. Within any ring of (outer) radius $d$, the bug travels a total of at most $10 d$ units.

Proof sketch. WIthout loss of generality (by scaling) assume the outer radius is 1. Assume for contradiction that the bug spends more than 10 seconds in this ring before moving into the next ring (of outer radius 0.99). At any time $t$, consider the angle $\alpha(t)$ formed by the following two vectors: the vector pointing from the bug in the direction the bug is traveling, and the vector pointing from the bug to the origin.

The bug is always moving towards the nearest point in the intersection of the discs placed so far, and that intersection is convex and contains the origin. Hence, the angle $\alpha(t)$ is always strictly less than ninety degrees, and the distance from the bug to the origin is strictly decreasing.

Whenever the angle $\alpha(t)$ is, say, less than eighty-nine degrees, the distance to the origin is decreasing at rate at least $1/100$. But, during the entire time in the ring, this distance decreases by less than $1/100$, so the total amount of time spent in the ring when $\alpha(t) < 89$ is at most 1 second. Thus, at least $9$ seconds are spent with the angle $\alpha(t)$ being at least 89 degrees and at most 90 degrees. Now consider any such time $t$. Since $\alpha(t) \in [89,90]$, and the ring has width $1/100$, the bug is traveling either distinctly clockwise around the ring, or distinctly counter-clockwise.

Let $p$ denote the point that the bug is moving towards (the closest point in the intersection of the discs placed so far). As the bug moves towards $p$, consider the line through the bug and perpendicular to the direction of motion of the bug. This line separates the plane into two half-planes, one "ahead" of the bug (containing $p$ and the intersection of the discs), and the other "behind" the bug. Mark the points in the half-plane behind the bug dead --- the bug can never return to any point once it is marked dead (because the point is not in the intersection of the discs).

Since $\alpha(t) \in [89,90]$, and the ring has radius 1 and width $1/100$, almost half of the points in the ring are behind the bug and are dead, including the points immediately behind the bug. The bug cannot return to those points, so, if the bug is initially traveling, say, clockwise, then the bug cannot "turn around" and start traveling counter-clockwise (for more than say, $1$ second). Thus, of the $10$ seconds, the bug would have to spend at least $8$ seconds traveling clockwise. But the circumference of the ring is $2\pi< 7$, half of the ring is dead as soon as the bug starts, and the bug cannot return to any dead point, so this is impossible. This proves the claim (more or less; maybe somebody can give a more precise argument).

By the claim, the total distance traveled (in all rings) is at most

Obviously the constant factor here is loose. For example, if the bug travels in the first ring at an angle of 89 degrees or more, this immediately kills almost half the points in the disc of radius 1 (not just the points in that one ring).