Solução do Giant Puzzle #14 – Star Wars

Parabéns a todos que se desafiaram a solucionar o Giant Puzzle #14! Admiramos imensamente aqueles que se arriscam a pensar fora da caixa e a encontrar soluções criativas para problemas complexos.

Conseguiram resolver esse puzzle:

1. Marlon Koga
2. V.B.
3. Lucas Gregolin Dias
4. João Matheus Del Vecchio França Barbosa

 

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.

 

Solução

 

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

(ṙ,θ̇,ϕ̇)(\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:

1. 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/kque é diametralmente oposto ao ponto em que está Darth Vader.

2. 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:

(ṙ,θ̇)=(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θθ 𝚜.𝚝. 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:

(ṙ,θ̇)=(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á:

(ṙ,θ̇)=(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:

ṙ=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⋅k T = \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)2 k^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 + \dfrac{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

tanx=x\tan x = x

:

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

k=4.603338848751693… 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)