Spotkałem następującą grę. Przeprowadzę migrację zgodnie z żądaniem.

• Błąd odwiedza kręgi, a przeciwnik chce zmaksymalizować swój czas podróży.

• Przeciwnik umieszcza koło na każdym kroku.

• Błąd przesuwa się z bieżącej pozycji bezpośrednio w kierunku środka najnowszego kręgu, a następnie zatrzymuje się, gdy napotka wnętrze koła (w ten sposób: nie chodzi, jeśli krąg jest odtwarzany pokrywający jego położenie). To kolej na błąd.

• Istnieją koła dostępne dla przeciwnika.$N$

• Każdy kolejny okrąg ma promień mniejszy niż poprzedni okrąg.

• Każde koło musi przecinać punkt przecięcia wszystkich wcześniej granych kół. Oznacza to, że po odtworzeniu wszystkie kręgi muszą mieć wspólne skrzyżowanie.

EDIT: Przeciwnik jest wolny , aby wybrać promienie okręgów, z zastrzeżeniem ograniczenia, że promienie spadek monotonicznie.

---

Pytania i odpowiedzi:

---

1. Czy odległość jako ograniczona? $N\to\infty$Odp .: Nie, w niniejszej odpowiedzi podano przykład strategii przeciwnika
2. Jaka jest maksymalna odległość, jaką błąd musi pokonać podczas gry w kręgów. $N$Odp .: rośnie przy , przy tej samej odpowiedzi.$\Theta(\log(N))$

---

Wariant 2 : Błąd idzie bezpośrednio w stronę skrzyżowania dwóch ostatnio granych kół.

AKTUALIZACJA: Ten wariant został rozwiązany, przy założeniu, że błąd pamięta tylko ostatnie 2 kręgi tutaj odtwarzane . Rezultatem był ponownie nieograniczony dystans.

---

Jaki wpływ ma nieograniczona pamięć? tzn. błąd trafia na skrzyżowanie wszystkich wcześniej granych kręgów . W ten sposób powstało „luźne” wiązanie , gdzie d jest średnicą pierwszego koła. Oczywiście nie może być mniej niż to. Zobacz tutaj . Obecna górna granica wynosiła 1000 × d . Zostało to uzyskane przez zbliżenie ścieżki najgorszego przypadku jako trasy wokół stopniowo coraz mniejszych kręgów. Wykazano, że błąd zawsze postępuje w kierunku końcowego skrzyżowania, zmniejszając w ten sposób odległość, którą musi pokonać kolejny krok.$O(d)$$d$$1000\times d$

Podejrzewam, że przebyta odległość jest małą stałą razy obwód pierwszego koła, ale obecnie nie jestem w stanie dostarczyć dobrego dowodu.

Ta odpowiedź składa się z dwóch części, które razem pokazują, że poprawna granica to :$\Theta(\log N)$

1. Dolna granica (razy promień pierwszego koła).$\Omega(\log N)$
2. Pasująca górna granica .$O(\log N)$

Dolna granica $\Omega(\log N)$

Rozważ dwa koła jednostek, które dotykają punktu . (Patrz poniżej; p jest po prawej stronie, błąd zaczyna się po lewej.) Na przemian między jednym okręgiem a drugim. Błąd będzie poruszał się w górę i w dół zygzakiem przez szczelinę między dwoma okręgami, poruszając się głównie w górę i w dół, ale również postępując powoli w prawo. Jeśli poprawnie wykonałem trygonometrię, po N krokach odległość od punktu wspólnego wyniesie Θ ( 1 / $p$$p$$N$, aN-ty krok spowoduje, że błąd przejdzieΘ(1/N), na całkowitą odległośćΘ(logN).$\Theta(1/\sqrt N)$$N$$\Theta(1/N)$$\Theta(\log N)$

Oto szkic obliczeń. Rozważ kilka następujących po sobie kroków. Przechodzi od pewnego punktu , b , do c . Punkty a i c znajdują się na tym samym kole; punkt b znajduje się na drugim okręgu. Niech O będzie środkiem okręgu że jest włączony. Rozważ następujące trzy trójkąty, w kolejności malejącej wielkości:$a$$b$$c$$a$$c$$b$$o$$a$

1. Trójkąt izocelowy (przypominamy, że p jest wspólnym punktem).$\triangle oap$$p$
2. Trójkąt .$\triangle abp$
3. Mały trójkąt $\triangle abc$

Te trójkąty są prawie podobne (tzn. Przystające skalowanie modulo). Dokładniej, dla , wszystkie trzy mają następującą właściwość: stosunek długości krótkiej nogi do długiej nogi wynosi Θ ( ϵ ) . (Nie udowodnię tego bardziej szczegółowo tutaj, ale zauważmy, że ϵ → 0 w miarę chodzenia błędu, a zaburzając jeden wierzchołek w każdym trójkącie o nieistotną wielkość, trójkąty można upodobnić).$\epsilon = |ap|$$\Theta(\epsilon)$$\epsilon\rightarrow 0$

Długie nogi i p o pierwszego trójkąta mają długość 1. Jego krótka noga | a p | ma długość ϵ . Segment a p jest długą nogą drugiego trójkąta, tak że krótka noga trójkąta a b ma długość Θ ( ϵ 2 ) . Segment a b jest długą nogą trzeciego trójkąta, tak że krótka noga trójkąta a c ma długość Θ ( ϵ 3 ) . Zatem w tych dwóch krokach, które podejmuje błąd:$co$$po$$|ap|$$\epsilon$$ap$$ab$$\Theta(\epsilon^2)$$ab$$ac$$\Theta(\epsilon^3)$

1. Odległość błąd podróży to Θ ( ϵ 2 ) .$|ab|+|bc|$$\Theta(\epsilon^2)$
2. Odległość od błędu do wspólnego punktu zmniejsza się z ϵ do ϵ - Θ ( ϵ 3 ) .$p$$\epsilon$$\epsilon-\Theta(\epsilon^3)$

Określić czas będzie liczbą etapów przed ε t ≈ 1 / 2 k . O (2) powyżej, ϵ zmniejsza się o stały współczynnik po około Θ ( 1 / ϵ 2 ) krokach, więc t k + 1 = t k + Θ ( 2 2 k ) = t k + Θ ( 4 k ) . Zatem 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)$ . Oznacza to, że po Θ ( 4 k ) kroków, odległość od błędu do wspólnego punktu p wyniesie około 1 / 2 k . Zmieniając zmienne, po N krokach odległość od błędu do wspólnego punktu wyniesie ϵ = Θ ( 1 / $t_k = \Theta(4^k)$$\Theta(4^k)$$p$$1/2^k$$N$. I naN-tym etapie błąd przemieszcza sięΘ(ϵ2)=Θ(1/N). Tak więc całkowita droga przebyta przez pierwszeNkroków jestΘ(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)$

To jest dolna granica.

Rozciąga się na proponowany wariant 2 (jak rozumiem), jak następuje:

Dodanie ograniczenia, że ​​błąd powinien przenosić się do najbliższego punktu na przecięciu dwóch ostatnio umieszczonych kół, nie pomaga. Oznacza to, że dolna granica powyżej nadal obowiązuje. Aby zobaczyć, dlaczego zmodyfikujemy powyższy przykład, dodając jeden obcy krąg, który pozwala błędowi spełnić ograniczenie, wciąż podróżując tą samą ścieżką:$\Omega(\log N)$

Zielone i niebieskie kółka to dwa koła z powyższego przykładu. Przecięcie wskazuje i b są takie same i b , jak w przykładzie powyżej. Czerwone kółko to nowe „obce” koło. Poprzednia sekwencja występowała na przemian między niebieskim i zielonym okręgiem. Nowa sekwencja będzie tą sekwencją, ale z czerwonym kółkiem dodawanym przed każdym okręgiem w starej sekwencji: czerwony, niebieski, czerwony, zielony, czerwony, niebieski, czerwony, zielony, czerwony, niebieski ...$a$$b$$a$$b$

Załóżmy, że błąd znajduje po umieszczeniu niebieskiego. Następne umieszczone koło jest czerwone. Kolor czerwony zawiera błąd, więc błąd się nie porusza. Następne umieszczone koło jest zielone. Teraz błąd przesuwa się do b (który jest najbliższym punktem przecięcia zielonego i czerwonego koła). Powtarzając to, błąd podróżuje jak poprzednio.$a$$b$

---

Górna granica $O(\log N)$

Szkicuję tylko dowód.

Napraw dowolną sekwencję okręgów. Będziemy argumentować, że jako całkowita odległość przebyta przez błąd w pierwszych N krokach wynosi O ( log N ) . Załóż, bez utraty ogólności, że pierwszy okrąg ma promień 1.$N\rightarrow \infty$$N$$O(\log N)$

Ustalić arbitralnie dużej . Niech p przez dowolny punkt na przecięciu pierwszych N kół. Zauważ, że z powodu sposobu, w jaki błąd się porusza, na każdym kroku, w którym błąd się porusza, zbliża się do p .$N$$p$$N$$p$

Najpierw rozważ kroki, w których następujący stosunek wynosi co najmniej : zmniejszenie odległości do $1/\log N$

$$\frac{\mbox{the reduction in the distance to } p}{\mbox{the distance traveled in the step}}.$$ $O(\log N)$$O(\log N)$$p$$1 / \log N$

$O(\log N)$

$a$$b$$o$$b'$$\overrightarrow{pb}$$|pa| = |pb|$

Rozważ następujące trójkąty:

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

$\epsilon$$\Theta(\epsilon)$

$$\frac{|bb'|}{|ab|} = \Theta\big(\frac{|ab|}{|pa|}\big) = \Theta\big(\frac{|pa|}{|bo|}\big) = \Theta(\epsilon).$$

$|bo|$$[1/2,1]$$|ab| = \Theta(|pa|^2/|bo|) = \Theta(|pa|^2)$$|bb'| = \Theta(|ab||pa|/|bo|) = \Theta(|pa|^3)$

$p$$d$$d'$$d=|pa|$$d'=|pb|$$d-d' = |bb'|$

$d$$|bb'|$$\Omega(d^3)$

$d/2$$O(1/d^2)$$d=1/2^k$$1/2^{k+1}$$O(4^k)$$1/2^{k}$$O(1/4^k)$$n$$p$$O(1/\sqrt n)$

$n$$|ab|$$O((\mbox{the current distance to } p)^2) = O(1/n)$$N$$[1/2,1]$

$$\sum_{n=1}^N O(1/n) = O(\log N).$$

$k$$[1/2^k, 1/2^{k+1}]$$O(\log(N)/2^k)$$k$$O(\log N)$

David E. domyślił się

„Może odpowiedź byłaby inna, gdyby błąd podszedł bezpośrednio do najbliższego punktu na bieżącym skrzyżowaniu, a nie w kierunku środka nowego koła?”

(EDYCJA: Pamiętaj, że to nie to samo, co „wariant 2” na końcu pytania oryginalnego plakatu).

Oto dowód (mniej więcej) jego przypuszczeń (w tym przypadku jest ograniczony).

$O(d_0)$$d_0$

$o$$o$$0$

$o$$1, 0.99, 0.99^2, 0.99^3, \ldots$

---

$d$$10 d$

$t$$\alpha(t)$

$\alpha(t)$

$\alpha(t)$$1/100$$1/100$$\alpha(t) < 89$$9$$\alpha(t)$$t$$\alpha(t) \in [89,90]$$1/100$

$p$$p$$p$

$\alpha(t) \in [89,90]$$1/100$$1$$10$$8$$2\pi< 7$, połowa pierścienia jest martwa, gdy tylko błąd się rozpocznie, a błąd nie może wrócić do żadnego martwego punktu, więc jest to niemożliwe. To potwierdza twierdzenie (mniej więcej; może ktoś może podać bardziej precyzyjny argument).

---

$$\sum_{i=0}^\infty 10 (0.99)^i ~=~ 1000.$$

Oczywiście stały czynnik tutaj jest luźny. Na przykład, jeśli błąd przemieszcza się w pierwszym pierścieniu pod kątem 89 stopni lub więcej, natychmiast zabija prawie połowę punktów na dysku o promieniu 1 (nie tylko punkty w tym pierścieniu).