Gra polegająca na ustawianiu nakładających się kręgów, aby zmaksymalizować czas podróży między nimi

13

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? NOdp .: 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. NOdp .: rośnie przy , przy tej samej odpowiedzi.Θ(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)d1000×d

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

Josh Vander Hook
źródło
Czy promień kręgów jest wybrany przez przeciwnika? Czy wolno mu przyjmować promienie w funkcji ? (Również nie sądzę, że należy to do teorii gier)N
HdM
Jest to zdecydowanie gra ..
Suresh Venkat
2
Wydaje mi się trochę dziwne, że istnieje ograniczenie, że koła mają wspólne skrzyżowanie, ale ruch robaka niekoniecznie wprowadza je w to wspólne skrzyżowanie. Może odpowiedź byłaby inna, gdyby błąd szedł bezpośrednio do najbliższego punktu na bieżącym skrzyżowaniu, a nie w kierunku środka nowego koła?
David Eppstein,
1
@DavidEppstein: Myślę, że twoja sugestia jest poprawna. W sugerowanym wariancie całkowita przebyta odległość jest ograniczona przez gdzie r jest początkową odległością od błędu do środka pierwszego okręgu. Dodam szkic próbny w drugiej odpowiedzi poniżej. O(r)r
Neal Young,
1
@vzn i mody zwykle uwzględniają żądania.
Josh Vander Hook

Odpowiedzi:

15

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

  1. Dolna granica (razy promień pierwszego koła).Ω(logN)
  2. Pasująca górna granica .O(logN)

Dolna granica Ω(logN)

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 / √)ppN, aN-ty krok spowoduje, że błąd przejdzieΘ(1/N), na całkowitą odległośćΘ(logN).Θ(1/N)NΘ(1/N)Θ(logN)

ilustracja

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:abcacboa

  1. Trójkąt izocelowy (przypominamy, że p jest wspólnym punktem).oapp
  2. Trójkąt .abp
  3. Mały trójkąt 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ć).ϵ=|ap|Θ(ϵ)ϵ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:copo|ap|ϵapabΘ(ϵ2)abacΘ(ϵ3)

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

Określić czas będzie liczbą etapów przed ε t1 / 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 ktkϵt1/2kϵΘ(1/ϵ2)tk+1=tk+Θ(22k)=tk+Θ(4k) . 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 / tk=Θ(4k)Θ(4k)p1/2kN. 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).ϵ=Θ(1/N)NΘ(ϵ2)=Θ(1/N)NΘ(1+1/2+1/3+...+1/N)=Θ(logN)

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ą:Ω(logN)

wprowadź opis zdjęcia tutaj

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 ...abab

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.ab


Górna granica O(logN)

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.NNO(logN)

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 .NpNp

Najpierw rozważ kroki, w których następujący stosunek wynosi co najmniej : zmniejszenie odległości do  p1/logN

the reduction in the distance to pthe distance traveled in the step.
O(logN)O(logN)p1/logN

O(logN)

abobpb|pa|=|pb|

wprowadź opis zdjęcia tutaj

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

  1. opb
  2. pba
  3. abb

ϵΘ(ϵ)

|bb||ab|=Θ(|ab||pa|)=Θ(|pa||bo|)=Θ(ϵ).

|bo|[1/2,1]|ab|=Θ(|pa|2/|bo|)=Θ(|pa|2)|bb|=Θ(|ab||pa|/|bo|)=Θ(|pa|3)

pddd=|pa|d=|pb|dd=|bb|

d|bb|Ω(d3)

d/2O(1/d2)d=1/2k1/2k+1O(4k)1/2kO(1/4k)npO(1/n)

n|ab|O((the current distance to p)2)=O(1/n)N[1/2,1]

n=1NO(1/n)=O(logN).

k[1/2k,1/2k+1]O(log(N)/2k)kO(logN)

Neal Young
źródło
3
bardzo schludna konstrukcja!
Suresh Venkat
Chciałbym pokochać tę odpowiedź, ale nie ufam twojemu wyzwalaczowi. Czy jest jakaś szansa na więcej szczegółów?
Josh Vander Hook
OK, dodałem szczegóły.
Neal Young
4
i=00.99i=100
2
Szkoda, że ​​nie możemy oznaczać odpowiedzi jako ulubionych!
Jeffε
5

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(d0)d0

oo0

o1,0.99,0.992,0.993,


d10d

tα(t)

α(t)

α(t)1/1001/100α(t)<899α(t)tα(t)[89,90]1/100

ppp

α(t)[89,90]1/10011082π<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).


i=010(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).

Neal Young
źródło
2πr0
O(1)Ω(logN)N
Hm Tak, wycofuję się trochę o „oczywistym”, to było w złym guście. Nie jest to od razu oczywiste. Czy to prawda, że ​​górna granica w problemie 2 powinna być niższa niż górna granica w problemie 1?
Josh Vander Hook
1
O(d0)NΩ(d0logN)d0