PUZZLE ENCERRADO

Star Wars

Edição #014 · jun. de 2024
← Voltar para o puzzle atual

Darth Vader prendeu Luke Skywalker na estrela da morte. Luke pode voar no interior da estrela com velocidade 1, enquanto Darth voa apenas sobre sua superfície, mas com velocidade k. O poder da força permite que ambos saibam a posição exata um do outro, a qualquer momento. Se Luke conseguir chegar na superfície sem que Darth esteja por perto, ele consegue fugir em segurança.

Considerando que a estrela da morte é uma esfera de raio 1, Luke e Darth tem dimensões desprezíveis e os dois são muito inteligentes, responda:

a) Determine k_lim tal que Luke consegue escapar se, e somente se, k < k_lim.

b) Encontre uma estratégia para Luke que minimiza o tempo necessário para escapar quando a velocidade de Vader é 0.99 k_lim.

// Leaderboard
Quem resolveu
5 soluções corretas · Puzzle #014
1
Leonardo Martos Barbosa
2
Marlon Koga
3
V.B.
4
Lucas Gregolin Dias
5
João Matheus Del Vecchio França Barbosa
// Solução
Resolução do Puzzle #014

1 – Equivalência com o problema em 2 dimensões

A trajetória ótima de Luke se dará ao longo de um círculo de raio máximo e portanto será em 2 dimensões.

Em um dado momento, Luke escolhe um vetor de velocidade (r˙,θ˙,ϕ˙)(\dot{r}, \dot{\theta}, \dot{\phi}), expresso em coordenadas polares. Supondo que a segunda coordenada (primeiro ângulo) corresponde ao semi-círculo que contempla Luke e Darth Vader, qualquer ϕ˙\dot{\phi} não nulo é contraprodutivo – a melhor forma de ganhar distância (ou perder menos distância) é correr ao longo do semi-círculo. Deixamos como exercício para o leitor provar essa afirmação.

2 – A solução sub-ótima para klim=1+πk_{lim} = 1 + \pi

Seja kk o múltiplo da velocidade de Darth Vader.

A estratégia pode ser dividida em duas etapas:

• Primeiramente, Luke se move dentro de um círculo de raio 1/k1/k. Nesse círculo, a velocidade angluar de Luke é maior que a de Darth Vader. Por isso, Luke consegue se colocar em um ponto da circunferência de raio 1/k1/k que é diametralmente oposto ao ponto em que está Darth Vader.

• A partir deste ponto, Luke se move em linha reta até a borda do círculo de raio 1. Luke terá que percorrer uma distância de 1–1/k1 – 1/k, enquanto Darth Vader precisará percorrer uma distância de π\pi.

A condição necessária para que a estratégia de Luke funcione é que 1–1/k≤π/k1 – 1/k \leq \pi / k e é satisfeita para kk inferior a 1+π1 + \pi

3 – A solução ótima

Durante a solução, o módulo do vetor velocidade do Luke será ∣v∣|v| e para o Darth Vader será ∣k⋅v∣|k\cdot v|.

O passo (1) é inevitável em qualquer estratégia ótima de Luke. Não é difícil de argumentar que ele é necessário.

O passo (2) pode ser melhorado. Se Luke se mover segundo uma curva, de forma a ter sempre uma velocidade em direção à borda e uma outra velocidade se distanciando de Darth Vader, ele pode ser mais eficiente.

Luke terá um vetor de velocidade vv que será parametrizado em coordenadas polares como:

(r˙,θ˙)=(v⋅cos⁡α,vr⋅sin⁡α)(\dot{r}, \dot{\theta}) = \left (v \cdot \cos \alpha, \dfrac{v}{r} \cdot \sin \alpha \right)

A escolha do ângulo α\alpha em cada instante no tempo parametriza a estratégia seguida por Luke.

Consideremos que kk é um parâmetro fixado. Para um dado instante no tempo, os parâmetros do problema que vamos considerar serão os seguintes:

• rr é a distância de Luke até o centro

• θ\theta é a distância angular de Luke para Darth Vader

Defina f(r,θ)f(r, \theta) como uma booleana (1 ou 0) que diz se em uma dada configuração Luke consegue escapar de Vader. Sabemos que f(1,0)=1f(1, 0) = 1. O problema do puzzle é equivalente a determinar f(1/k,π)f\left (1/k, \pi \right).

Definimos agora:

T(r)=min⁡θθ s.t. f(r,θ)=1T(r) = \min_{\theta} {\theta \texttt{ s.t. } f(r, \theta) = 1}

Sabemos que T(1)=0T(1) = 0 e queremos saber se T(1/k)T(1/k) está bem definido.

Olhando para um micro-instante no tempo dtdt, T(r)T(r) segue a seguinte “recursão”:

T(r)=inf⁡α(T(r+v⋅cos⁡α⋅dt)+(k⋅v–vr⋅sin⁡α)⋅dt)T(r) = \inf_{\alpha} \left (T(r + v \cdot \cos \alpha \cdot dt) + \left (k \cdot v – \dfrac{v}{r} \cdot \sin\alpha \right) \cdot dt \right )

Ela considera todos os ângulos possíveis em que Luke pode se mover e qual será a nova configuração de (r,θ)(r, \theta) . Para entender a recursão, é importante entender T(r)T(r) como o maior ângulo tal que Luke consegue escapar:

• Após o movimento, Luke conseguirá escapar de um ângulo T(r+v⋅cos⁡α⋅dt)T(r + v \cdot \cos \alpha \cdot dt)

• Durante o movimento, Luke “perde” um ângulo (k⋅v–vr⋅sin⁡α)\left (k \cdot v – \dfrac{v}{r} \cdot \sin\alpha \right)

O α\alpha que maximiza a expressão de dentro do inf⁡\inf pode ser obtido derivando a expressão em função de α\alpha e é igual a:

α^=arctan⁡(−1r⋅dTdr(r))        (1)\hat{\alpha } = \arctan \left (-\dfrac{1}{r\cdot \frac{dT}{dr}(r)} \right ) \;\;\;\; (1)

Substituindo esse valor de α\alpha e reparametrizando drdr como v⋅cos⁡α⋅dtv \cdot \cos \alpha \cdot dt, chegamos à equação:

T(r)=T(r+dr)+(k–1r⋅sin⁡α)cos⁡α⋅drT(r) = T(r + dr) + \dfrac{\left (k – \dfrac{1}{r} \cdot \sin \alpha \right)}{\cos \alpha} \cdot dr

que é equivalente a:

dTdr(r)=T(r+dr)–T(r)dr=(−k+1r⋅sin⁡α)cos⁡α        (2)\frac{dT}{dr}(r) = \frac{T(r+dr) – T(r)}{dr} = \dfrac{\left (-k + \dfrac{1}{r} \cdot \sin \alpha \right)}{\cos \alpha} \;\;\;\; (2)

Unindo as equações (1)(1) e (2)(2), é possível chegar na seguinte relação:

sin⁡α=1k⋅r        (∗)\sin \alpha = \dfrac{1}{k \cdot r} \;\;\;\; (*)

Substituindo nessa equação o valor de α\alpha obtido anteriormente, chegamos a uma equação que nos permite, através de uma busca binária, obter o valor de dTdr\frac{dT}{dr} numericamente.

A partir de dTdr\frac{dT}{dr}, podemos integrar de 11 a 1/k1/k para chegar no valor de T(1/k)T(1/k). Naturalmente, TT só está definida para rr’s em que T(r)≤πT(r) \leq \pi.

Por fim, uma busca binária foi feita para achar o maior valor de kk tal que TT seja definida pela condição acima.

O valor encontrado para klimk_{lim} foi de aproximadamente:

klim=4.6033k_{lim} = 4.6033

4 – Outra solução ótima 2

Uma outra solução seria utilizar o resultado intermediário obtido na solução ótima 1.

Considerando que o passo (1) seja feito, no referencial do Darth Vader, o vetor de velocidade vv de Luke poderá ser parametrizado em coordenadas polares como:

(r˙,θ˙)=(v⋅cos⁡α,k⋅v–vr⋅sin⁡α)(\dot{r}, \dot{\theta}) = \left (v \cdot \cos \alpha, k\cdot v – \dfrac{v}{r} \cdot \sin \alpha \right)

onde o Darth Vader com o módulo do vetor velocidade de ∣k⋅v∣|k \cdot v| e α\alpha será o ângulo entre o vetor velocidade do Luke e a direção radial que passa pelo mesmo.

Pelo resultado intermediário da solução ótima 1, teremos que o α\alpha ótimo para cada instante será:

sin⁡α=1k⋅r            (∗)\sin \alpha = \dfrac{1}{k \cdot r} \;\;\;\;\;\; (*)

Logo, o vetor velocidade de Luke em relação ao Darth Vader será:

(r˙,θ˙)=(v⋅k2r2–1k⋅r,k⋅v–vr⋅1k⋅r)(\dot{r}, \dot{\theta}) = \left (v \cdot \dfrac{\sqrt{k^2r^2 – 1}}{k \cdot r}, k\cdot v – \dfrac{v}{r} \cdot \dfrac{1}{k \cdot r} \right)

Analisando a primeira coordenada:

r˙=v⋅k2r2–1k⋅r\dot{r} = v \cdot \dfrac{\sqrt{k^2r^2 – 1}}{k \cdot r}
∫0Tdrk2r2–1k⋅r=v∫0Tdt        (3)\int_{0}^{T}\dfrac{dr}{\dfrac{\sqrt{k^2r^2 – 1}}{k \cdot r}} = v \int_{0}^{T} dt \;\;\;\; (3)
k2⋅r2(t)−1k∣0T=v⋅T\left. \dfrac{ \sqrt{k^2 \cdot r^2(t) -1} }{k} \right\rvert_{0}^{T} = v \cdot T

Temos que: r(0)=1/kr(0) = 1/k e r(T)=1r(T) = 1. Partindo do raio r(0)=1/kr(0) = 1/k e seguindo uma trajetória dada pela equação (∗)(*).

k2−1k=v⋅T\dfrac{ \sqrt{k^2 -1 } }{k} = v \cdot T
T=k2−1v⋅kT = \dfrac{ \sqrt{k^2 -1 } }{v \cdot k}

Analisando a segunda coordenada:

θ˙=k⋅v–vr⋅1k⋅r\dot{\theta} = k\cdot v – \dfrac{v}{r} \cdot \dfrac{1}{k \cdot r}
∫0Tθ˙  dt=π=v⋅(k⋅T–1k⋅∫0T1r2dt)\int_{0}^{T} \dot{\theta} \; dt = \pi = v \cdot \left (k \cdot T – \dfrac{1}{k} \cdot \int_{0}^{T} \dfrac{1}{r^2} dt \right)

A partir da primeira coordenada, temos que:

k2⋅r(t)2−1k=v⋅t\dfrac{ \sqrt{k^2 \cdot r(t)^2 -1} }{k} = v \cdot t
k2⋅r(t)2−1=(v⋅t⋅k)2k^2 \cdot r(t)^2 -1 = (v \cdot t \cdot k)^2
1r2(t)=1v2t2+1k2\dfrac{1}{r^2(t)} = \dfrac{1}{v^2 t^2 + \frac{1}{k^2}}

Substituindo e integrando no tempo:

π=v⋅(k⋅T–1k⋅∫0T1v2t2+1k2dt)\pi = v \cdot \left (k \cdot T – \dfrac{1}{k} \cdot \int_{0}^{T} \dfrac{1}{v^2 t^2 + \dfrac{1}{k^2}} dt \right)
π=v⋅(k⋅T–arctan⁡(v⋅k⋅T)v)\pi = v \cdot \left (k \cdot T – \dfrac{\arctan (v \cdot k \cdot T)}{v} \right)
π=v⋅k⋅T–arctan⁡(v⋅k⋅T)\pi = v \cdot k \cdot T – \arctan (v \cdot k \cdot T)

Mas, temos pela equação (3)(3) que:

v⋅k⋅T=k2−1v \cdot k \cdot T = \sqrt{k^2 -1}

Logo,

arctan⁡(k2−1)=k2−1–π\arctan \left (\sqrt{k^2 -1} \right) = \sqrt{k^2 -1} – \pi
k2−1=tan⁡(k2−1–π)=tan⁡(k2−1)\sqrt{k^2 -1} = \tan \left ( \sqrt{k^2 -1} – \pi \right ) = \tan \left ( \sqrt{k^2 -1} \right )

Resolvendo com a menor solução real positiva de tan⁡x=x\tan x = x:

k2−1=4.49340945790906…\sqrt{k^2 -1} = 4.49340945790906…

k = 4.603338848751693…

Letra b)

Seja k=0.99⋅klimk = 0.99 \cdot k_{lim}

A estratégia será o Luke fazer o passo (1) da solução ótima 1, e seguir no passo (2) com o ângulo alpha tal que:

sin⁡α=1k⋅r\sin \alpha = \dfrac{1}{k \cdot r}

Tomando v=1v=1, o tempo que o passo (2)(2) se passará será:

T=k2−1k=0.975628717035808…T = \dfrac{ \sqrt{k^2 -1 } }{k} = 0.975628717035808…

Solução ótima 1 – Henrique Fiuza (Giant Steps)

Solução ótima 2 – Renan Ferreira (Giant Steps)

// Arquivo
Outras edições
δ
#015
Encerrado
jan. de 2026
Banco Central
24 soluções corretas
β
#013
Encerrado
dez. de 2023
Dovish It
8 soluções corretas
μ
#011
Encerrado
mar. de 2023
Empire State
16 soluções corretas
∇
#006
Encerrado
mar. de 2021
Formiga
11 soluções corretas
∮
#005
Encerrado
jan. de 2021
Blackjack
6 soluções corretas
∂
#004
Encerrado
out. de 2020
Colecionador
3 soluções corretas
λ
#003
Encerrado
jul. de 2020
Sudoku
32 soluções corretas
∑
#002
Encerrado
mai. de 2020
Chopp do Pedro
25 soluções corretas