J'ai rencontré le jeu suivant. Je migrerai cela comme demandé.

• Un bug est en train de visiter les cercles, et un adversaire souhaite maximiser son temps de voyage.

• L'adversaire place un cercle à chaque tour.

• Le bug part de sa position actuelle directement vers le centre du cercle le plus récent, puis s'arrête lorsqu'il rencontre l'intérieur du cercle (ainsi: il ne marche pas si un cercle est joué couvrant son emplacement). C'est au tour du bug.

• L' adversaire dispose de $N$ cercles.

• Chaque cercle suivant a un rayon inférieur au cercle précédent.

• Chaque cercle doit croiser l'intersection de tous les cercles précédemment joués. Autrement dit, tous les cercles doivent avoir une intersection commune une fois tous joués.

EDIT: L'adversaire est libre de choisir les rayons des cercles, sous la contrainte que les rayons diminuent de façon monotone.

Questions et réponses:

1. La distance sous la forme limitée? $N\to\infty$R: Non, un exemple de stratégie adversaire est donné par cette réponse
2. Quelle est la distance maximale que le bug doit parcourir sur le jeu de cercles. $N$A: elle croît en , par la même réponse.$\Theta(\log(N))$

Variante 2 : le bug se dirige directement vers l'intersection des deux derniers cercles joués .

MISE À JOUR: Cette variante a été corrigée, en supposant que le bug ne peut se souvenir que des 2 derniers cercles joués ici . Le résultat fut à nouveau une distance illimitée.

Quel impact la mémoire non imprimée a-t-elle? c'est-à-dire que le bug va à l'intersection de tous les cercles précédemment joués . Cela a produit une limite "lâche" de , où d est le diamètre du premier cercle. Évidemment, cela ne peut pas être inférieur à cela. Voyez ici . La limite supérieure actuelle était de 1 000 × d . Ceci a été obtenu en rapprochant le chemin le plus défavorable en faisant le tour de cercles progressivement plus petits. Il a été démontré que le bug progresse toujours vers l'intersection finale, réduisant ainsi la distance de l'étape suivante qu'il doit parcourir.$O(d)$$d$$1000\times d$

Je soupçonne que la distance parcourue est un peu constante fois la circonférence du premier cercle, mais je ne suis actuellement pas en mesure de fournir une bonne preuve.

Cette réponse comporte deux parties, montrant ensemble que la borne correcte est :$\Theta(\log N)$

1. Une borne inférieure de (multipliée par le rayon du premier cercle).$\Omega(\log N)$
2. Une limite supérieure correspondante de .$O(\log N)$

Limite inférieure de $\Omega(\log N)$

Considérons deux cercles unitaires qui se touchent en un point . (Voir ci-dessous; p est à droite, le bogue commence à gauche.) Alterner entre un cercle et l'autre. Le bug se déplacera de haut en bas en zigzaguant à travers la crevasse entre les deux cercles, se déplaçant principalement de haut en bas mais progressant également lentement vers la droite. Si j'ai fait la trigonométrie correctement, après N étapes, la distance du point commun sera $p$$p$$N$, et laNème étape fera marcher le bugΘ(1/N), pour une distance totale deΘ($\Theta(1/\sqrt N)$$N$$\Theta(1/N)$ .$\Theta(\log N)$

Voici un croquis des calculs. Considérez deux étapes consécutives que le bogue fait. Il va d'un certain point , à b , à c . Les points a et c sont sur le même cercle; le point b est sur l'autre cercle. Soit $a$$b$$c$$a$$c$$b$$o$ être le centre du cercle qui est allumé. Considérez les trois triangles suivants, par ordre décroissant de taille:$a$

1. Le triangle isocèle (rappel p est le point commun).$\triangle oap$$p$
2. Le triangle .$\triangle abp$
3. Le petit triangle $\triangle abc$

Ces triangles sont presque similaires (c.-à-d. Mise à l'échelle modulo congruente). Plus précisément, pour , les trois ont la propriété suivante: le rapport de la longueur de la jambe courte à la jambe longue est Θ ( ϵ )$\epsilon = |ap|$$\Theta(\epsilon)$ . (Je ne le prouverai pas plus en détail ici, mais notez que fur et à mesure que le bogue marche, et en perturbant un sommet dans chaque triangle d'une quantité négligeable, les triangles peuvent être rendus similaires.)$\epsilon\rightarrow 0$

Les longues jambes et p o du premier triangle ont une longueur 1. Sa jambe courte | a p | a une longueur ϵ . Le segment a p est une longue jambe du deuxième triangle, de sorte que la jambe courte du triangle a b a une longueur Θ ( ϵ 2 ) . Le segment a b est une longue jambe du troisième triangle, de sorte que la jambe courte du triangle a c a une longueur Θ ( ϵ 3 ) . Ainsi, dans ces deux étapes que le bogue prend:$co$$po$$|ap|$$\epsilon$$ap$$ab$$\Theta(\epsilon^2)$$ab$$ac$$\Theta(\epsilon^3)$

1. La distance le bug se déplace est Θ $|ab|+|bc|$ .$\Theta(\epsilon^2)$
2. La distance entre le bogue et le point commun diminue de ϵ à ϵ - Θ $p$$\epsilon$ .$\epsilon-\Theta(\epsilon^3)$

Définir le temps étant le nombre d'étapes avant ε t ≈ une / deux k . Par (2) ci-dessus, ϵ diminue d'un facteur constant après environ Θ ( 1 / ϵ 2 ) pas, donc t k + 1 = t k + Θ ( 2 2 k ) = t k + Θ ( 4 k ) . Ainsi, 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)$ . Autrement dit, après$t_k = \Theta(4^k)$ des étapes, la distance entre le bogue au point commun p sera d'environ 1 / 2 k . En changeant les variables, après N étapes, la distance entre le bug et le point commun sera ϵ = Θ $\Theta(4^k)$$p$$1/2^k$$N$. Et, à laNème étape, le bug se déplaceΘ(ϵ2)=Θ(1/N). Donc la distance totale parcourue dans les premiersNétapes estΘ(1+1/deux+1/trois+...+1/N)=Θ$\epsilon = \Theta(1/\sqrt N)$$N$$\Theta(\epsilon^2) = \Theta(1/N)$$N$ .$\Theta(1+1/2+1/3+...+1/N) = \Theta(\log N)$

Ceci est la limite inférieure.

Il s'étend à la variante 2 proposée (si je comprends bien), comme suit:

L'ajout de la restriction selon laquelle le bogue doit se déplacer vers le point le plus proche de l'intersection des deux derniers cercles placés n'aide pas. C'est-à-dire que la borne inférieure ci-dessus s'applique toujours. Pour voir pourquoi, nous allons modifier l'exemple ci-dessus en ajoutant un seul cercle étranger qui permet au bogue de respecter la restriction tout en parcourant le même chemin:$\Omega(\log N)$

Les cercles vert et bleu sont les deux cercles de l'exemple ci-dessus. Les points d'intersection et b sont les mêmes a et b que dans l'exemple ci-dessus. Le cercle rouge est le nouveau cercle "étranger". La séquence précédente alternait entre les cercles bleu et vert. La nouvelle séquence sera cette séquence, mais avec le cercle rouge ajouté avant chaque cercle de l'ancienne séquence: rouge, bleu, rouge, vert, rouge, bleu, rouge, vert, rouge, bleu, ...$a$$b$$a$$b$

Supposons que le bug est assis à après le bleu est placé. Le prochain cercle placé est rouge. Le rouge contient le bug, donc le bug ne bouge pas. Le prochain cercle placé est vert. Maintenant, le bug se déplace vers b (qui est le point le plus proche de l'intersection des cercles vert et rouge). En répétant cela, le bug se déplace comme avant.$a$$b$

Limite supérieure de $O(\log N)$

Je ne fais qu'esquisser la preuve.

Corrigez toute séquence de cercles. Nous soutiendrons que comme , la distance totale parcourue par le bug dans les N premières étapes est O ( log N ) . Supposons sans perte de généralité que le premier cercle a un rayon de 1.$N\rightarrow \infty$$N$$O(\log N)$

Fixe un arbitrairement grand . Soit p par n'importe quel point de l'intersection des N premiers cercles. Notez qu'en raison de la façon dont le bug se déplace, à chaque étape qu'il se déplace, il se rapproche de p .$N$$p$$N$$p$

Considérons d'abord les étapes où le rapport suivant est d'au moins : la réduction de la distance à $1/\log N$ La distance totale parcourue à ces étapes estO(logN), car la distance totale parcourue à ces étapes estO(logN)multipliée par la distance initiale jusqu'àp. Il suffit donc de délimiter la distance totale parcourue dans les autres étapes --- celles dans lesquelles ce rapport est au maximum de1/log

Tout d'abord, nous soutenons quelque chose de légèrement plus faible: que la distance totale parcourue à de telles étapes avant que le rayon du cercle ne diminue à 1/2 ou moins soit $O(\log N)$ . (Nous montrerons plus tard que cela suffit pour donner la limite.)

Considérez une telle étape. Soit et b , respectivement, les emplacements du bogue avant et après l'étape. Soit o le centre du cercle courant. Soit b ′ le point du rayon → p b tel que | p a | = | p b | :$a$$b$$o$$b'$$\overrightarrow{pb}$$|pa| = |pb|$

Considérez les triangles suivants:

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

By geometric arguments similar to those in the lower bound, for some $\epsilon$, each of these triangles has two long legs and one short leg, and the ratio (for each triangle) of the short leg length to the long leg lengths is $\Theta(\epsilon)$:

This equation and the assumption that $|bo|$, which is the circle radius, is in $[1/2,1]$ imply that $|ab| = \Theta(|pa|^2/|bo|) = \Theta(|pa|^2)$, and then that $|bb'| = \Theta(|ab||pa|/|bo|) = \Theta(|pa|^3)$.

Now we focus on the bug's distance to $p$. Call it $d$ before the step, and $d'$ after the step. (Note $d=|pa|$, $d'=|pb|$, and $d-d' = |bb'|$.)

In this step, this distance $d$ reduces by $|bb'|$, which by the above observations is $\Omega(d^3)$.

Thus, the number of additional steps required to reduce the distance by a factor of 2 (to at most $d/2$) is $O(1/d^2)$. Changing variables, if $d=1/2^k$, the number of additional steps required to bring the distance below $1/2^{k+1}$ is $O(4^k)$. Since the sum is geometric, the total number of steps required to bring the distance below $1/2^{k}$ is $O(1/4^k)$. Changing variables again, after $n$ steps, the distance to $p$ will be $O(1/\sqrt n)$.

Finally, recalling the displayed equation several paragraphs up, in the $n$th step, the distance that the bug travels, i.e. $|ab|$, is $O((\mbox{the current distance to } p)^2) = O(1/n)$. Thus, the total distance traveled in the first $N$ such steps while the circle radius is in $[1/2,1]$ is at most

By scaling, we conclude that, for any $k$, the total distance traveled while the circle radius is in the range $[1/2^k, 1/2^{k+1}]$ is $O(\log(N)/2^k)$. Summing over $k$, the total distance traveled is $O(\log N)$. QED

David E. conjectured

"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).