Um jogo de posicionamento de círculos sobrepostos para maximizar o tempo de viagem entre eles

13

Eu encontrei o seguinte jogo. Vou migrar isso conforme solicitado.

  • Um bug está visitando os círculos e um adversário deseja maximizar seu tempo de viagem.

  • O adversário coloca um círculo a cada turno.

  • O bug sai de sua posição atual diretamente em direção ao centro do círculo mais novo e depois para quando encontra o interior do círculo (assim: não anda se um círculo for jogado cobrindo sua localização). Esta é a vez do bug.

  • Existem N círculos disponíveis para o adversário.

  • Cada círculo subsequente tem raio menor que o círculo anterior.

  • Cada círculo deve cruzar a interseção de todos os círculos reproduzidos anteriormente. Ou seja, todos os círculos devem ter um cruzamento comum depois que todos são executados.

EDIT: O adversário é livre para escolher os raios dos círculos, sujeito à restrição de que os raios diminuam monotonicamente.


Perguntas e respostas:


  1. A distância como N limitada? R: Não, um exemplo de estratégia adversária é dado por esta resposta
  2. Qual é a distância máxima que o inseto deve percorrer ao tocar N círculos. A: cresce em Θ(log(N)) , pela mesma resposta.

Variante 2 : O bug caminha diretamente em direção à interseção dos dois círculos reproduzidos mais recentemente .

UPDATE: Esta variante foi abordada, sob a suposição de que o bug consegue se lembrar dos últimos 2 círculos jogados aqui . O resultado foi novamente uma distância ilimitada.


Qual o impacto que a memória não impressa tem? ou seja, o bug vai para a interseção de todos os círculos reproduzidos anteriormente . Isso produziu um limite "solto" de , onde d é o diâmetro do primeiro círculo. Obviamente, não pode ser menor que isso. Veja aqui . O limite superior atual era 1000 × d . Isso foi obtido aproximando o caminho do pior caso como um passeio em círculos progressivamente menores. Foi mostrado que o bug sempre progride em direção à interseção final, reduzindo assim a distância do próximo passo que ele deve percorrer.O(d)d1000×d

Suspeito que a distância percorrida seja um pouco constante vezes a circunferência do primeiro círculo, mas atualmente não sou capaz de fornecer uma boa prova.

Josh Vander Hook
fonte
O raio dos círculos é escolhido pelo adversário? Ele pode receber raios em função de ? (Além disso, eu não acho que este pertence na teoria dos jogos)N
HDM
É definitivamente um jogo ..
Suresh Venkat 14/03
2
Parece-me um pouco estranho que haja uma restrição de que os círculos tenham uma interseção comum, mas que o movimento do inseto não o traga necessariamente para essa interseção comum. Talvez a resposta fosse diferente se o bug caminhava diretamente para o ponto mais próximo no cruzamento atual, em vez de para o centro do novo círculo?
precisa
1
@ DavidEppstein: Eu acho que sua sugestão está correta. Na variante sugerida, a distância total percorrida é delimitada por que r é a distância inicial do inseto ao centro do primeiro círculo. Vou adicionar um esboço de prova em uma segunda resposta abaixo. O(r)r
Neal Young
1
O @vzn e os mods geralmente acomodam solicitações.
precisa

Respostas:

15

Esta resposta tem duas partes, mostrando juntos que o limite correto é :Θ(logN)

  1. Um limite inferior de (vezes o raio do primeiro círculo).Ω(logN)
  2. Um limite superior correspondente de .O(logN)

Limite inferior de Ω(logN)

Considere dois círculos unitários que tocam em um ponto . (Veja abaixo; p está à direita, o erro começa à esquerda.) Alterne entre um círculo e outro. O bug irá subir e descer ziguezague pela fenda entre os dois círculos, movendo-se principalmente para cima e para baixo, mas também progredindo lentamente para a direita. Se eu fiz a trigonometria corretamente, após N etapas, a distância do ponto comum será Θ ( 1 / ppN, e aNth passo fará com que o erro de andarΘ(1/N), para uma distância total deΘ(logN).Θ(1/N)NΘ(1/N)Θ(logN)

ilustração

Aqui está um esboço dos cálculos. Considere algumas duas etapas consecutivas que o bug executa. Ele vai de algum ponto , a b , a c . Os pontos a e c estão no mesmo círculo; o ponto b está no outro círculo. Seja o centro do círculo em que a está. Considere os três triângulos a seguir, em ordem decrescente de tamanho:abcacboa

  1. O triângulo isoceles (recordação p representa o ponto comum).oapp
  2. O triângulo .abp
  3. O pequeno triângulo abc

Esses triângulos são quase semelhantes (ou seja, escala de módulo congruente). Mais precisamente, para , todos os três têm a seguinte propriedade: a razão entre o comprimento da perna curta e a perna longa é Θ ( ϵ ) . (Não vou provar isso com mais detalhes aqui, mas observe que ϵ 0 à medida que o erro avança e, ao perturbar um vértice em cada triângulo por uma quantidade desprezível, os triângulos podem se tornar semelhantes.)ϵ=|ap|Θ(ϵ)ϵ0

As longas pernas e p o do primeiro triângulo tem comprimento 1. Sua perna curta | a p |copo|ap|tem comprimento . Segmento de um p é uma perna longa da segunda triângulo, de modo que a perna curta do triângulo um b tem comprimento Θ ( ε 2 ) . Segmento de um b é uma perna longa da terceira triângulo, de modo que a perna curta do triângulo um c tem comprimento Θ ( ε 3 ) . Assim, nestas duas etapas que o bug executa:ϵapabΘ(ϵ2)abumacΘ(ϵ3)

  1. A distância o erro viaja é Θ ( ϵ 2 ) .|umab|+|bc|Θ(ϵ2)
  2. A distância do bug ao ponto comum diminui de ϵ para ϵ - Θ ( ϵ 3 ) .pϵϵ-Θ(ϵ3)

Definir tempo ser o número de passos antes ε t1 / 2 K . Em (2) acima, ϵ diminua por um fator constante após cerca de Θ ( 1 / ϵ 2 ) etapas, então t k )tkϵt1/2kϵΘ(1/ϵ2). Assim, t k =Θ( 4 ktk+1=tk+Θ(22k)=tk+Θ(4k)tk=Θ(4k) . Isto é, depois de passos, a distância a partir do erro no ponto comum p será de cerca de 1 / 2 K . Alterando variáveis, após N etapas, a distância do bug ao ponto comum será ϵ = Θ ( 1 / Θ(4k)p1/2kN. E, noN° passo, o erro viajaΘ(ε2)=Θ(1/N). Portanto, a distância total percorrida no primeiroNϵ=Θ(1/N)NΘ(ϵ2)=Θ(1/N)N passos é .Θ(1+1/2+1/3+...+1/N)=Θ(registroN)

Este é o limite inferior.

Estende-se à Variante 2 proposta (como eu a entendo), da seguinte maneira:

Adicionar a restrição de que o bug deve se mover para o ponto mais próximo na interseção dos dois círculos colocados mais recentemente não ajuda. Ou seja, o limite inferior acima ainda se aplica. Para entender o porquê, modificaremos o exemplo acima adicionando um único círculo estranho que permita que o bug atenda à restrição enquanto ainda estiver percorrendo o mesmo caminho:Ω(registroN)

insira a descrição da imagem aqui

Os círculos verde e azul são os dois círculos do exemplo acima. A intersecção aponta e b são os mesmos um e b como no exemplo acima. O círculo vermelho é o novo círculo "estranho". A sequência anterior alternava entre os círculos azul e verde. A nova sequência será essa sequência, mas com o círculo vermelho adicionado antes de cada círculo na sequência antiga: vermelho, azul, vermelho, verde, vermelho, azul, vermelho, verde, vermelho, azul, ...umabumab

Suponha que o bug está sentado em após azul é colocado. O próximo círculo colocado é vermelho. O vermelho contém o erro, para que ele não se mova. O próximo círculo colocado é verde. Agora o bug se move para b (que é o ponto mais próximo da interseção dos círculos verde e vermelho). Repetindo isso, o bug viaja como antes.umab


Limite superior de O(registroN)

Eu só desenho a prova.

Corrija qualquer sequência de círculos. Argumentaremos que, como , a distância total percorrida pelo bug nos primeiros N passos é O ( log N ) . Suponha, sem perda de generalidade, que o primeiro círculo tenha raio 1.NNO(registroN)

Corrija um arbitrariamente grande . Seja p em qualquer ponto da interseção dos primeiros N círculos. Observe que, devido à maneira como o bug se move, a cada passo que o bug se move, ele se aproxima de p .NpNp

Primeiro, considere as etapas em que a seguinte proporção é pelo menos : a redução na distância para  p1/logN A distância total percorrida em tais etapas éO(log

the reduction in the distance to pthe distance traveled in the step.
, porque a distância total percorrida em tais etapas é O ( log N ) vezes a distância inicial para p . Por isso, só precisa ligado a distância total percorrida em outros passos --- aqueles em que a referida relação é, no máximo, 1 / log N .O(logN)O(logN)p1/logN

Primeiro, argumentamos algo um pouco mais fraco: que a distância total percorrida em tais etapas antes que o raio do círculo diminua para 1/2 ou menos é . (Mostramos mais tarde que isso é suficiente para dar o limite.)O(logN)

Considere qualquer passo desse tipo. Deixe e b , respectivamente, denotam os locais do bug antes e depois da etapa. Deixe o denotar o centro do círculo atual. Seja b denotar o ponto no raioabob tal que| pa| =| pb| :pb|pa|=|pb|

insira a descrição da imagem aqui

Considere os seguintes triângulos:

  1. opb
  2. pba
  3. abb

Por argumentos geométricos semelhantes aos do limite inferior, para alguns , cada um desses triângulos tem duas pernas longas e uma perna curta, e a proporção (para cada triângulo) do comprimento da perna curta para o comprimento da perna longa é Θ ( ϵ ) : | b b |ϵΘ(ϵ)

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

Essa equação e a suposição de que , Que é o raio do círculo, é em [ 1 / 2 , 1 ] implica que | a b | = Θ ( | p a | 2 / | b o | ) = Θ ( | p a | 2 ) e depois | b b | = Θ ( | a b ||bo|[1/2,1]|ab|=Θ(|pa|2/|bo|)=Θ(|pa|2) .|bb|=Θ(|ab||pa|/|bo|)=Θ(|pa|3)

Agora vamos nos concentrar na distância do bug até a . Chame-o de d antes do passo e d ' depois do passo. (Nota d = | p a | , d = | p b |pddd=|pa|d=|pb| , e .)dd=|bb|

Nesta etapa, essa distância reduzida em | b b | , que pelas observações acima é Ω ( d 3 ) .d|bb|Ω(d3)

Assim, o número de etapas adicionais necessárias para reduzir a distância por um fator de 2 (no máximo ) é O ( 1 / d 2 ) . Alterando as variáveis, se d = 1 / 2 k , o número de passos adicionais necessários para trazer a distância abaixo de 1 / 2 k + 1 é O ( 4 k ) . Uma vez que a soma é geométrico, o número total de passos necessários para levar a distância abaixo 1 / 2 k é O (d/2O(1/d2)d=1/2k1/2k+1O(4k)1/2k . Alterando variáveis ​​novamente, após n etapas, a distância até p será O ( 1 / O(1/4k)np.O(1/n)

Finalmente, recordando o exibido equação vários parágrafos acima, no º passo, a distância que o bug viaja, ou seja | a b | , é O ( ( a distância atual para  p ) 2 ) = O ( 1 / n ) . Assim, a distância total percorrida nas primeiras N tais passos, enquanto o raio do círculo é em [ 1 / 2 , 1 ] é no máximo N Σ n = 1 O ( 1 /n|ab|O((the current distance to p)2)=O(1/n)N[1/2,1]

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

Por escamação, conclui-se que, para qualquer , a distância total percorrida enquanto o raio do círculo é na gama [ 1 / 2 k , 1 / 2 k + 1 ] é O ( log ( N ) / 2 k ) . Somando kk[1/2k,1/2k+1]O(log(N)/2k)k , a distância total percorrida é . QEDO(logN)

Neal Young
fonte
3
construção muito elegante!
Suresh Venkat
Eu adoraria amar essa resposta, mas não confio no seu gatilho. Alguma chance de mais alguns detalhes?
Josh Vander Hook
OK, eu adicionei os detalhes.
Neal Young
4
Se cada círculo tiver no máximo 99% por cento do tamanho do anterior, a distância total percorrida será limitada, simplesmente porque em cada etapa a distância percorrida é no máximo o diâmetro do círculo anterior e a soma dos diâmetros do círculos é no máximo . (Vezes a distância inicial do bug até o ponto mais distante do primeiro círculo.)i=00.99i=100
Neal Young
2
É uma pena que não possamos marcar respostas como favoritas!
Jeffε
5

David E. conjecturou

"Talvez a resposta seja diferente se o inseto caminhe diretamente para o ponto mais próximo no cruzamento atual, em vez de para o centro do novo círculo?"

(EDIT: Observe que isso não é o mesmo que a "variante 2" no final da pergunta do pôster original.)

Aqui está uma prova (mais ou menos) de sua conjectura (é delimitada neste caso).

Lema. Para a variante sugerida por David, a distância total percorrida pelo erro é sempre , em que d 0 é a distância máxima entre o erro e qualquer ponto do primeiro círculo colocado.O(d0)d0

prova. Suponha ao WLOG que o local de descanso final seja a origem que o erro comece na distância 1 de ooo . Para exposição, assuma que o erro começa no tempo , viaja à taxa unitária (uma polegada por segundo) e para apenas quando atinge o último disco colocado. Observe que (conforme explicado mais abaixo) à medida que o erro rastreia sua distância até a origem diminui estritamente.0

Particione o disco de raio unitário (centrado em ) em infinitos anéis, desenhando círculos concêntricos dos raios 1 , 0,99 , 0,99 2 , 0,99 3 ,o .1,0.99,0.992,0.993,


Afirmação. Dentro de qualquer anel de (exterior) de raio , o erro viaja um total de, no máximo, 10 d unidades.d10d

Esboço de prova. SEM perda de generalidade (por escala) assume que o raio externo é 1. Suponha, por contradição, que o erro gaste mais de 10 segundos neste anel antes de passar para o próximo anel (de raio externo 0,99). A qualquer momento , considere o ângulo α ( t ) formado pelos dois vetores a seguir: o vetor apontando do erro na direção em que ele está viajando e o vetor apontando do erro para a origem.tα(t)

O erro está sempre se movendo em direção ao ponto mais próximo na interseção dos discos colocados até agora, e essa interseção é convexa e contém a origem. Portanto, o ângulo é sempre estritamente menor que noventa graus, e a distância do erro até a origem está estritamente diminuindo.α(t)

Sempre que o ângulo é, digamos, inferior a oitenta e nove graus, a distância para a origem que diminui a taxa de pelo menos 1 / 100 . Mas, durante todo o tempo em anel, esta distância diminui por menos do que 1 / 100 , de modo que a quantidade total de tempo gasto no anel quando α ( t ) < 89 é no máximo de 1 segundo. Assim, são gastos pelo menos 9 segundos com o ângulo α ( t ) sendo pelo menos 89 graus e no máximo 90 graus. Agora considere qualquer momento tα(t)1/1001/100α(t)<899α(t)t . Desde , e o anel tem largura 1 / 100 , o erro está viajando quer distintamente dos ponteiros do relógio em torno do anel, ou distintamente sentido anti-horário.α(t)[89,90]1/100

Vamos denotar o ponto em que o erro está se movendo (o ponto mais próximo na interseção dos discos colocados até agora). À medida que o inseto se move em direção a p , considere a linha através do inseto e perpendicular à direção do movimento do inseto. Essa linha separa o plano em dois semiplanos, um "à frente" do erro (contendo pppp a interseção dos discos) e o outro "atrás" do erro. Marque os pontos no semi-plano atrás do erro como morto - o erro nunca pode retornar a qualquer ponto depois de marcado como morto (porque o ponto não está na interseção dos discos).

Desde , e o anel tem um raio e largura 1 / 100 , quase metade dos pontos do anel estão por trás do erro e são mortos, incluindo os pontos imediatamente por trás do erro. O erro não pode retornar a esses pontos; portanto, se ele estiver inicialmente viajando, digamos, no sentido horário, então não poderá "girar" e começar a viajar no sentido anti-horário (por mais de 1 segundo). Assim, dos 10 segundos, o bug teria que gastar pelo menos 8 segundos viajando no sentido horário. Mas a circunferência do anel é 2 πα(t)[89,90]1/10011082π<7, metade do anel está morto assim que o bug é iniciado e o bug não pode retornar a nenhum ponto morto, portanto, isso é impossível. Isso prova a afirmação (mais ou menos; talvez alguém possa dar um argumento mais preciso).


Pela reivindicação, a distância total percorrida (em todos os anéis) é, no máximo,

i=010(0.99)i = 1000.

Obviamente, o fator constante aqui é frouxo. Por exemplo, se o erro viaja no primeiro anel em um ângulo de 89 graus ou mais, isso mata imediatamente quase metade dos pontos no disco do raio 1 (não apenas os pontos desse anel).

Neal Young
fonte
2πr0
O(1)Ω(logN)N
Hum. Sim, eu recuo um pouco sobre "óbvio", que estava de mau gosto. Não é imediatamente óbvio. É verdade que o limite superior no problema 2 deve ser menor que o limite superior no problema 1?
Josh Vander Gancho
1
O(d0 0)NΩ(d0 0registroN)d0 0