Ich bin auf folgendes Spiel gestoßen. Ich werde dies wie gewünscht migrieren.

• Ein Käfer besucht Kreise und ein Gegner möchte seine Reisezeit maximieren.

• Der Gegner setzt bei jeder Runde einen Kreis.

• Der Käfer bewegt sich von seiner aktuellen Position direkt in Richtung der Mitte des neuesten Kreises und stoppt dann, wenn er auf das Innere des Kreises stößt. Dies ist der Fehler an der Reihe.

• Dem Gegner stehen $N$ Kreise zur Verfügung.

• Jeder nachfolgende Kreis hat einen kleineren Radius als der vorherige Kreis.

• Jeder Kreis muss den Schnittpunkt aller zuvor gespielten Kreise schneiden. Das heißt, alle Kreise müssen einen gemeinsamen Schnittpunkt haben, sobald alle gespielt wurden.

BEARBEITEN: Der Gegner kann die Radien der Kreise frei wählen, unter der Bedingung, dass die Radien monoton abnehmen.

Fragen und Antworten:

1. Ist der Abstand als begrenzt? $N\to\infty$A: Nein, diese Antwort gibt ein Beispiel für eine gegnerische Strategie
2. Was ist die maximale Entfernung, die der Käfer über das Spielen von Kreisen zurücklegen muss? $N$ Θ ( log ( N ) )A: Es wächst bei , nach der gleichen Antwort.$\Theta(\log(N))$

Variante 2 : Der Bug wandert direkt zum Schnittpunkt der beiden zuletzt gespielten Kreise.

UPDATE: Diese Variante wurde unter der Annahme angesprochen, dass sich der Fehler nur an die letzten 2 hier gespielten Kreise erinnern kann . Das Ergebnis war wieder eine grenzenlose Distanz.

Welchen Einfluss hat ein unbegrenztes Gedächtnis? Das heißt, der Bug springt zum Schnittpunkt aller zuvor gespielten Kreise . Dies erzeugte eine "lose" Bindung von , wobei der Durchmesser des ersten Kreises ist. Offensichtlich kann es nicht weniger sein. Sehen Sie hier . Die aktuelle Obergrenze war . Dies wurde erreicht, indem der Worst-Case-Pfad als eine Tour durch immer kleinere Kreise angenähert wurde. Es wurde gezeigt, dass der Bug immer in Richtung der endgültigen Kreuzung voranschreitet, wodurch sich die nächste zurückzulegende Schrittstrecke verringert.d 1000 × $O(d)$$d$$1000\times d$

Ich vermute, dass die zurückgelegte Strecke eine kleine Konstante des Umfangs des ersten Kreises ist, aber ich bin derzeit nicht in der Lage, einen guten Beweis zu liefern.

Diese Antwort besteht aus zwei Teilen, die zusammen zeigen, dass die korrekte Grenze :$\Theta(\log N)$

1. Eine Untergrenze von (multipliziert mit dem Radius des ersten Kreises).$\Omega(\log N)$
2. Eine übereinstimmende Obergrenze von .$O(\log N)$

Untergrenze von $\Omega(\log N)$

Betrachten Sie zwei Einheitskreise, die sich an einem Punkt berühren . (Siehe unten; p ist rechts, der Fehler beginnt links.) Wechseln Sie zwischen einem Kreis und dem anderen. Der Käfer bewegt sich im Zick-Zack auf und ab über den Spalt zwischen den beiden Kreisen, bewegt sich hauptsächlich auf und ab, bewegt sich aber auch langsam nach rechts. Wenn ich die Trigonometrie korrekt durchgeführt habe, beträgt der Abstand vom gemeinsamen Punkt nach N Schritten Θ ( 1 / $p$$p$$N$und derN-te Schritt veranlassen den Käfer,Θ(1/N)für eine Gesamtstrecke vonΘ(logN) zu gehen.$\Theta(1/\sqrt N)$$N$$\Theta(1/N)$$\Theta(\log N)$

Hier ist eine Skizze der Berechnungen. Betrachten Sie zwei aufeinanderfolgende Schritte, die der Fehler macht. Er geht von einem Punkt nach b nach c . Die Punkte a und c befinden sich auf demselben Kreis. Punkt b liegt auf dem anderen Kreis. Sei o der Mittelpunkt des Kreises, auf dem a liegt. Betrachten Sie die folgenden drei Dreiecke in abnehmender Reihenfolge:$a$$b$$c$$a$$c$$b$$o$$a$

1. Das Isozelen-Dreieck ( p ist der gemeinsame Punkt).$\triangle oap$$p$
2. Das Dreieck .$\triangle abp$
3. Das kleine Dreieck $\triangle abc$

Diese Dreiecke sind fast ähnlich (dh kongruente Moduloskalierung). Genauer gesagt für haben alle drei die folgende Eigenschaft: Das Verhältnis der Länge des kurzen zum langen Bein ist Θ ( ϵ ) . (Ich werde dies hier nicht detaillierter beweisen, aber beachten Sie, dass ϵ → 0, wenn der Fehler auftritt, und indem Sie einen Scheitelpunkt in jedem Dreieck um einen vernachlässigbaren Betrag stören, können die Dreiecke ähnlich gemacht werden.)$\epsilon = |ap|$$\Theta(\epsilon)$$\epsilon\rightarrow 0$

Die langen Beine und p o des ersten Dreiecks haben die Länge 1. Ihr kurzes Bein | a p | hat die Länge ϵ . Segment a p ist ein langer Schenkel des zweiten Dreiecks, so dass der kurze Schenkel a b des Dreiecks die Länge Θ ( ϵ 2 ) hat . Segment a b ist ein langer Schenkel des dritten Dreiecks, so dass der kurze Schenkel a c des Dreiecks die Länge Θ ( ϵ 3 ) hat . In diesen beiden Schritten, die der Fehler ausführt, geschieht Folgendes:$co$$po$$|ap|$$\epsilon$$ap$$ab$$\Theta(\epsilon^2)$$ab$$ac$$\Theta(\epsilon^3)$

1. Die Entfernung der Bug travels ist Θ ( ϵ 2 ) .$|ab|+|bc|$$\Theta(\epsilon^2)$
2. Der Abstand vom Käfer zum gemeinsamen Punkt nimmt von ϵ auf ϵ - Θ ( ϵ 3 ) ab .$p$$\epsilon$$\epsilon-\Theta(\epsilon^3)$

Zeit definieren ist die Anzahl der Schrittebevor ε t ≈ 1 / 2 k . Nach (2) oben nimmt ϵ nach etwa Θ ( 1 / ϵ 2 ) Schrittenum einen konstanten Faktor ab, so dass t k + 1 = t k + Θ ( 2 2 k ) = t k + Θ ( 4 k ) . Somit ist 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)$ . Das heißt, nach Θ ( 4 k ) Schritten, die Entfernung von dem Bug zu dem gemeinsamen Punkt P wird über seine 1 / 2 k . Wenn Sie die Variablen nach N Schritten ändern, ist der Abstand vom Käfer zum gemeinsamen Punkt ϵ = Θ ( 1 / $t_k = \Theta(4^k)$$\Theta(4^k)$$p$$1/2^k$$N$. Und imN-ten Schritt wandert der Fehler zuΘ(ϵ2)=Θ(1/N). Soder Gesamtabstand in der ersten gereistNSchrittenΘ(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)$

Dies ist die Untergrenze.

Es erstreckt sich auf die vorgeschlagene Variante 2 (wie ich es verstehe) wie folgt:

Das Hinzufügen der Einschränkung, dass der Fehler zum nächsten Punkt im Schnittpunkt der beiden zuletzt platzierten Kreise verschoben werden soll, hilft nicht. Das heißt, die untere Grenze von gilt weiterhin. Um zu sehen, warum, werden wir das obige Beispiel ändern, indem wir einen einzelnen äußeren Kreis hinzufügen, der es dem Fehler ermöglicht, die Einschränkung zu erfüllen, während er immer noch denselben Pfad zurücklegt:$\Omega(\log N)$

Die grünen und blauen Kreise sind die beiden Kreise aus dem obigen Beispiel. Die Schnittpunkte und b sind die gleichen a und b wie im obigen Beispiel. Der rote Kreis ist der neue "fremde" Kreis. Die vorherige Sequenz wechselte zwischen den blauen und grünen Kreisen. Die neue Sequenz wird diese Sequenz sein, wobei jedoch der rote Kreis vor jedem Kreis in der alten Sequenz eingefügt wird: rot, blau, rot, grün, rot, blau, rot, grün, rot, blau, ...$a$$b$$a$$b$

Angenommen, der Käfer sitzt an Punkt, nachdem Blau gesetzt wurde. Der nächste platzierte Kreis ist rot. Rot enthält den Fehler, sodass sich der Fehler nicht bewegt. Der nächste platzierte Kreis ist grün. Jetzt bewegt sich der Bug zu b (das ist der nächstgelegene Punkt auf dem Schnittpunkt der grünen und roten Kreise). Durch Wiederholen dieses Vorgangs wird der Fehler wie zuvor behoben.$a$$b$

Obergrenze von $O(\log N)$

Ich skizziere nur den Beweis.

Korrigieren Sie eine beliebige Folge von Kreisen. Wir werden argumentieren, dass als die Gesamtdistanz, die der Fehler in den ersten N Schritten zurückgelegt hat, O ( log N ) ist . Man gehe ohne Einschränkung der Allgemeinheit davon aus, dass der erste Kreis den Radius 1 hat.$N\rightarrow \infty$$N$$O(\log N)$

Fix eine beliebig große . Sei p durch irgendeinen Punkt im Schnittpunkt der ersten N Kreise. Beachten Sie, dass aufgrund der Art und Weise, wie sich der Fehler bewegt, er sich in jedem Schritt, in dem sich der Fehler bewegt, p nähert .$N$$p$$N$$p$

Betrachten Sie zunächst Schritte, bei denen das folgende Verhältnis mindestens beträgt : die Verringerung des Abstands zu $1/\log N$ Die in solchen Schritten zurückgelegte Gesamtdistanz istO(logN), da die in solchen Schritten zurückgelegte GesamtdistanzO(logN)multipliziert mit der Anfangsdistanz zup ist. Wir müssen also nur die in den anderen Schritten zurückgelegte Gesamtstrecke begrenzen - die, in denen dieses Verhältnis höchstens1/logNbeträgt.

Zunächst argumentieren wir etwas Schwächeres: Die in solchen Schritten zurückgelegte Gesamtstrecke, bevor der Kreisradius auf 1/2 oder weniger abfällt, ist . (Wir zeigen später, dass dies ausreicht, um die Grenze zu geben.)$O(\log N)$

Überlegen Sie sich einen solchen Schritt. Lassen und b jeweils bezeichnen die Orte des Fehlers vor und nach dem Schritt. Lassen Sie o bezeichnet den Mittelpunkt des aktuellen Kreises. Es sei b ' der Punkt auf dem Strahl → p b, so dass | p a | = | p b | :$a$$b$$o$$b'$$\overrightarrow{pb}$$|pa| = |pb|$

Betrachten Sie die folgenden Dreiecke:

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

Durch geometrische Argumente, die denen in der unteren Schranke ähnlich sind, hat für einige jedes dieser Dreiecke zwei lange Beine und ein kurzes Bein, und das Verhältnis (für jedes Dreieck) der kurzen Beinlänge zu den langen Beinlängen ist Θ ( ϵ) ) : | b b ' $\epsilon$$\Theta(\epsilon)$

Diese Gleichung und die Annahme, dass , Die der Kreisradius ist, ist in [ 1 / 2 , 1 ] bedeuten , dass | a b | $|bo|$$[1/2,1]$ , und dann das | b b ' | = Θ ( | a b $|ab| = \Theta(|pa|^2/|bo|) = \Theta(|pa|^2)$ .$|bb'| = \Theta(|ab||pa|/|bo|) = \Theta(|pa|^3)$

Jetzt konzentrieren wir uns auf den Abstand des Bugs zu . Nennen$p$ vor dem Schritt und d ' nach dem Schritt. (Beachten Sie, dass d = | p a | , d ' = | p b | und d - d ' = | b b ' | .)$d$$d'$$d=|pa|$$d'=|pb|$$d-d' = |bb'|$

In diesem Schritt verringert sich dieser Abstand um | b b ' | , die nach den obigen Beobachtungen Ω ( d 3 ) ist .$d$$|bb'|$$\Omega(d^3)$

Somit beträgt die Anzahl der zusätzlichen Schritte, die erforderlich sind, um den Abstand um einen Faktor 2 (auf höchstens ) zu verringern, 0 ( 1 / d 2 ) . Ändern der Variablen, wenn d = 1 / 2 k , die Anzahl der zusätzlichen Schritte erforderlich , um den Abstand unter bringen , 1 / 2 k + 1 ist O ( 4 k ) . Da die Summe geometrisch ist, benötigt die Gesamtanzahl der Schritte , um die Entfernung zu bringen , unter 1 / 2 k ist O $d/2$$O(1/d^2)$$d=1/2^k$$1/2^{k+1}$$O(4^k)$$1/2^{k}$ . ÄndernVariablen wieder, nach n Schritten, die Entfernung zu p wird O ( 1 / $O(1/4^k)$$n$$p$.$O(1/\sqrt n)$

Abschließend wird die angezeigte Gleichung im ten Schritt um mehrere Absätze nach oben verschoben, um die Entfernung, die der Fehler zurücklegt, dh um | a b | ist O ( ( der aktuelle Abstand zu  p ) 2 ) = O ( 1 / n ) . Somit reist der Gesamtstrecke in den ersten N solche Schritte , während der Kreisradius in ist [ 1 / 2 , 1 ] ist höchstens N Σ n = 1 O ( 1 $n$$|ab|$$O((\mbox{the current distance to } p)^2) = O(1/n)$$N$$[1/2,1]$

Durch Skalierung, schließen wir , dass, für jeden - Reisender die Gesamtstrecke , während der Kreisradius im Bereich [ 1 / 2 k , 1 / 2 k + 1 ] ist O ( log ( N ) / 2 k ) . Summiert man über k , so ergibt sich eine Gesamtstrecke von O ( log N ) . QED$k$$[1/2^k, 1/2^{k+1}]$$O(\log(N)/2^k)$$k$$O(\log N)$

Vermutete David E.

"Vielleicht wäre die Antwort anders, wenn der Käfer direkt zum nächsten Punkt in der aktuellen Kreuzung und nicht zum Zentrum des neuen Kreises laufen würde?"

(BEARBEITEN: Beachten Sie, dass dies nicht dasselbe ist wie die "Variante 2" am Ende der Frage des ursprünglichen Posters.)

Hier ist ein Beweis (mehr oder weniger) seiner Vermutung (in diesem Fall ist er begrenzt).

Lemma. Für die von David vorgeschlagene Variante ist die vom Fehler zurückgelegte Gesamtstrecke immer , wobei d 0 die maximale Strecke zwischen dem Fehler und einem beliebigen Punkt im ersten platzierten Kreis ist.$O(d_0)$$d_0$

Beweis. Angenommen, WLOG ist die letzte Ruhestätte der Ursprung und der Fehler beginnt in der Entfernung 1 von o . Für die Darstellung wird angenommen, dass der Fehler zum Zeitpunkt 0 beginnt , sich mit einer Einheitsrate (1 Zoll pro Sekunde) ausbreitet und erst stoppt, wenn er die zuletzt eingelegte CD erreicht. Beachten Sie, dass (wie weiter unten erläutert) die Entfernung zum Ursprung des Fehlers beim Durchsuchen immer geringer wird.$o$$o$$0$

Teilen Sie die Einheitsradiusscheibe (bei zentriert ) in unendlich viele Ringe, indem Sie konzentrische Kreise mit den Radien 1 , 0,99 , 0,99 2 , 0,99 3 , … zeichnen .$o$$1, 0.99, 0.99^2, 0.99^3, \ldots$

Anspruch. Innerhalb eines Rings mit (äußerem) Radius bewegt sich der Käfer insgesamt um höchstens 10 d Einheiten.$d$$10 d$

Proof-Skizze. Ohne Verlust der Allgemeinheit (durch Skalierung) wird angenommen, dass der äußere Radius 1 ist. Nehmen wir an, dass der Fehler in diesem Ring länger als 10 Sekunden dauert, bevor er in den nächsten Ring (mit dem äußeren Radius 0,99) übergeht. Berücksichtigen Sie zu jedem Zeitpunkt den Winkel α ( t ) , der durch die folgenden beiden Vektoren gebildet wird: den Vektor, der vom Käfer in die Richtung zeigt, in der sich der Käfer bewegt, und den Vektor, der vom Käfer zum Ursprung zeigt.$t$$\alpha(t)$

Der Bug bewegt sich immer in Richtung des nächstgelegenen Punkts im Schnittpunkt der bisher platzierten Scheiben, und dieser Schnittpunkt ist konvex und enthält den Ursprung. Daher ist der Winkel immer streng kleiner als neunzig Grad, und der Abstand vom Käfer zum Ursprung nimmt streng ab.$\alpha(t)$

Immer dann , wenn der Winkel ist, sagen wir, weniger als neunundachzig Grad, der Abstand zu dem Ursprung wird mit einer Rate abnimmt mindestens 1 / 100 . Aber während der gesamten Zeit im Ring, nimmt dieser Abstand von weniger als 1 / 100 , so dass die Gesamtzeit , in dem Ring ausgegeben , wenn α ( t ) < 89 höchstens 1 Sekunde beträgt. Somit werden mindestens 9 Sekunden mit einem Winkel & agr; ( t ) von mindestens 89 Grad und höchstens 90 Grad verbracht. Betrachten wir nun eine solche Zeit t . Da α $\alpha(t)$$1/100$$1/100$$\alpha(t) < 89$$9$$\alpha(t)$$t$ , und der Ring hatBreite 1 / 100 , wird der Fehler entweder deutlich im Uhrzeigersinn um den Ring oder deutlichGegenuhrzeigersinn fährt.$\alpha(t) \in [89,90]$$1/100$

Lassen Sie bezeichnen den Punkt , dass der Bug bewegt sich in Richtung (der nächste Punkt in der Kreuzung der Scheiben so weit gebracht). Wenn sich der Bug in Richtung p bewegt , betrachten Sie die Linie durch den Bug und senkrecht zur Bewegungsrichtung des Bugs. Diese Linie trennt die Ebene in zwei Halbebenen, eine "vor" dem Fehler (mit p und dem Schnittpunkt der Scheiben) und die andere "hinter" dem Fehler. Markieren Sie die Punkte in der Halbebene hinter dem Käfer als tot - der Käfer kann niemals zu einem Punkt zurückkehren, wenn er als tot markiert ist (da der Punkt nicht im Schnittpunkt der Scheiben liegt).$p$$p$$p$

Da und der Ring hat Radius 1 und die Breite 1 /$\alpha(t) \in [89,90]$$1/100$ fast die Hälfte der Punkte in den Ring hinter dem Bug und tot sind, einschließlich der Punkte unmittelbar hinter dem Bug. Der Bug kann nicht zu diesen Punkten zurückkehren. Wenn der Bug also anfänglich im Uhrzeigersinn läuft, kann er sich nicht "umdrehen" und gegen den Uhrzeigersinn weiterlaufen (länger als Sekunde). Von den 10 Sekunden müsste der Bug mindestens 8 Sekunden im Uhrzeigersinn laufen. Der Ringumfang ist jedoch 2 π < $1$$10$$8$$2\pi< 7$Wenn der Bug startet, ist die Hälfte des Rings tot, und der Bug kann nicht zu einem toten Punkt zurückkehren. Dies ist also unmöglich. Dies beweist die Behauptung (mehr oder weniger; vielleicht kann jemand ein genaueres Argument vorbringen).

Durch den Anspruch fuhr die Gesamtdistanz (in allen Ringen) höchstens

Offensichtlich ist der konstante Faktor hier locker. Wenn sich der Käfer beispielsweise im ersten Ring in einem Winkel von 89 Grad oder mehr bewegt, werden sofort fast die Hälfte der Punkte in der Scheibe mit Radius 1 (nicht nur die Punkte in diesem einen Ring) getötet.