Solução do Giant Puzzle #13 – Dovish It

Parabéns a todos que se desafiaram a solucionar o Giant Puzzle #13! 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. Andre Costa
2. Gustavo Aldama Mourão Soares Pereira
3. Igor Dias
4. Ivan Petrin
5. Leonardo Martos Barbosa
6. Lucas De Andrade Santos Duarte
7. Lucas Giacone
8. Victor Marques Moreno

 

Imagine que você está em um salão de um restaurante fechado. Um pássaro entra pela janela e começa a voar aleatoriamente por cima das mesas. Você quer saber qual a probabilidade de sua mesa ser “premiada”.

Vamos modelar o problema da seguinte maneira. Imagine que o restaurante tem n mesas enfileiradas em linha reta e que a janela pela qual o pássaro entrou está na mesa 1. Considere que, após o pássaro entrar, as janelas e portas estão todas fechadas.

Considere que o pássaro se move em intervalos de 1 segundo e que, no instante t, ele tem 50% de probabilidade de ficar onde está e 50% de se mover para uma mesa vizinha. Por exemplo, se ele está sobrevoando a mesa 3, ele tem 50% de probabilidade de ficar na mesa 3, 25% de ir para a mesa 4 e 25% de ir para a mesa 2. No caso de ele estar sobrevoando a mesa n ou a mesa 1, ele tem 50% de probabilidade de ficar na mesma mesa e 50% de probabilidade de ir para a única mesa vizinha.

(a) Suponha que o restaurante tem 5 mesas (n=5). Supondo que uma mesa foi “premiada” após exatamente 10 segundos, qual é a probabilidade de ter sido a mesa de número 5?
(b) Defina p(t, k) como: “supondo que uma mesa foi “premiada” após exatamente t segundos, qual a probabilidade de ter sido a mesa k.” Qual o menor valor de t tal que p(t, 5) está entre 12% e 13%?

 

Solução

Considere um vetor $P(t)$ em que a entrada $k$ é $p(t, k)$, a probabilidade de se estar em $k$ no instante $t$. Pode-se definir uma matriz de transição para a dinâmica do problema, em que a entrada $(i,j)$ é a probabilidade de irmos da casa $j$ para a $i$ em um passo: $$A = \begin{pmatrix} p_{1 \rightarrow 1} & p_{2 \rightarrow 1} & p_{3 \rightarrow 1} & \dots & p_{n \rightarrow 1} \\ p_{1 \rightarrow 2} & p_{2 \rightarrow 2}& p_{3 \rightarrow 2} & \dots & p_{n \rightarrow 2} \\ & & \vdots & & \\ p_{1 \rightarrow n} & p_{2 \rightarrow n} & p_{3 \rightarrow n} & \dots & p_{n \rightarrow n} & \end{pmatrix}$$ De modo que podemos resolver $P(t)$ recursivamente:

$$P(t+1) = A P(t) \implies P(t)=A^tP(0)$$

Para $n=5$, temos $$A=\begin{pmatrix} 0.5 & 0.25 & 0 & 0 & 0 \\ 0.5 & 0.5 & 0.25 & 0 & 0 \\ 0 & 0.25 & 0.5 & 0.25 & 0 \\ 0 & 0 & 0.25 & 0.5 & 0.5 \\ 0 & 0 & 0 & 0.25 & 0.5 \\ \end{pmatrix} \quad \text{e} \quad P(0) = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix}$$

Calculando em um computador, obtemos: $$P(10)= \begin{pmatrix} 0.1766 \\ 0.3226 \\ 0.2495 \\ 0.1774 \\ 0.0739 \end{pmatrix}$$ Portanto, a resposta do item a) é $7.39 \%$

Para o item b), calculamos $P(t)$ para $t=1, 2, 3, …$
O primeiro valor de $t$ para o qual $p(t, 5)$ está entre $0.12$ e $0.13$ é $t=25$.

Por que a probabilidade de acabarmos nas pontas aparenta convergir para metade da probabilidade de acabarmos no meio quando $t \rightarrow \infty$?
Para $t=25$, por exemplo, o vetor de probabilidades fica $$P(25) = \begin{pmatrix} 0.1298 \\ 0.2567 \\ 0.25 \\ 0.2433 \\ 0.1202 \end{pmatrix}$$ Entenderemos melhor a dinâmica do problema se nos livrarmos da assimetria nas pontas: ao invés de considerar que as mesas 1 e n só tem um vizinho, estenda o salão infinitamente de modo que todos tenham dois vizinhos: $$1 \:\: 2 \:\: 3 \:\: \cdots (n-1) \:\: n$$ $$\Downarrow$$ $$\:\:\:\:\:\:\:\:\: \cdots \:\: 3 \:\: 2 \:\: 1 \:\: 2 \:\: 3 \:\: \cdots (n-1) \:\: n \:\: (n-1) \:\: \cdots$$ Isto é, cada mesa terá infinitas “cópias virtuais", de modo que, por exemplo, quando o pássaro vai da mesa 1 para a mesa 2 do restaurante, no salão estendido ele tem a opção de ir para a mesa 2 ou para a 2 virtual. Assim, podemos considerar que o pássaro sempre vai para esquerda, direita ou fica parado com probabilidades de 25%, 25% e 50%, respectivamente.

Mais formalmente, associamos cada mesa do restaurante a um subconjunto dos inteiros, de modo que quando o pássaro estiver sobre a mesa $k$, o pássaro virtual estará sobre algum dos inteiros associados à mesa $k$. O diagrama abaixo ilustra parte do salão estendido para $n=5$: o eixo $y$ apresenta a mesa no salão normal e o eixo $x$, os inteiros associados no salão estendido.

Agora fica evidente o por quê da probabilidade do pássaro estar nas pontas converge para metade da probabilidade de estar em uma mesa do meio: cada período da associação $\text{mesa} \leftrightarrow \text{inteiro}$ tem apenas 1 inteiro associado às mesas 1 e $n$, mas dois inteiros associados às mesas do meio (visualmente, um na “subida" e outro na “descida").

Na verdade, o salão virtual nos dá muito mais que mera intuição sobre a dinâmica do problema. Com a devida diligência, podemos calcular $p(t, k)$ explicitamente para qualquer par $t, k$.

Para tanto, vamos introduzir a função geratriz do movimento do pássaro: $$F_t(x)=x^1(0.5x^0 + 0.25x^1 +0.25 x^{-1})^t$$ Essa série nos é útil pois o coeficiente do termo $x^k$ em sua expansão é exatamente $\overline{p}(t,k)$, a probabilidade do pássaro acabar sobre a mesa virtual $k$ após $t$ segundos: $$F_t(x)=\sum_{k}{a_k x^k} \quad \text{:} \quad a_k=\overline{p}(t,k)$$ Portanto, para acharmos $p(t,k)$, basta somar os coeficientes $a_k \prime$ de todos os inteiros $k^{\prime}$ associados à mesa k: $$p(t,k)=\sum_{k^{\prime} \text{assoc.} k}{\overline{p}(t,k^{\prime})}=\sum_{k^{\prime} \text{assoc.} k}{a_{k \prime }}$$ Vamos explorar um pouco melhor $F_t(x)$: $$F_t(x)=x^1(0.5x^0 + 0.25x^1 +0.25 x^{-1})^t = x^1\frac{(2x+x^2+1)^t}{2^{2t}x^t}$$ $$\implies F_t(x)=\frac{(x+1)^{2t}}{2^{2t}x^{t-1}}=\sum_{k}{a_k x^k}$$

No caso particular de $n=5$ e $k=5$, os inteiros associados à mesa 5 são os inteiros da forma $8x+5$ (Verifique você mesmo!). Portanto: $$p(t, 5)=\sum_{k=8x+5}{a_kx^k}$$ Mas como achamos a soma de um subconjunto dos coeficientes de uma série?
A soma do conjunto de todos os coeficientes é fácil: $$\sum_k{a_k}=\sum_k{a_k1^k}=F_t(1)=\frac{(1+1)^{2t}}{2^{2t}1^{t-1}}=1$$ Para o nosso subconjunto, podemos usar uma ideia parecida: substituir valores de x em $F_t(x)$ para ficarmos só com coeficientes, mas de forma que os coeficientes que não são da forma $8x+5$ “sumam". Podemos fazer isso se olharmos para uma série ligeiramente diferente, $G(x)=x^3F_t(x)$, e utilizarmos a oitava raiz primitiva da unidade $\zeta=e^{\frac{2\pi i}{8}}=cis(\frac{2\pi}{8})$.

O poder de $\zeta$ reside no fato de que $$(\zeta^i)^0+(\zeta^i)^1+\dots+(\zeta^i)^7=\frac{\zeta^{8i}-1}{\zeta^i-1} =\begin{cases} 0 & \text{se 8 não divide i} \\ 8 & \text{se 8 divide i} \end{cases}$$ Logo, $$\frac{G(\zeta^0)+G(\zeta^1)+\dots G(\zeta^7)}{8}=\sum_{k=8x+5}{a_k} \quad \text{onde} \quad G(x)=\frac{(x+1)^{2t}}{2^{2t}x^{t-4}}$$ pois os únicos termos de $G$ que “sobrevivem" são aqueles que multiplicam potências de x múltiplas de 8, isto é, exatemente os $a_{8x+5}$. Vamos às contas: $$G(\zeta^0)=G(1)=\frac{(1+1)^{2t}}{2^{2t}1^{t-4}}=1$$ $$G(\zeta^4)=G(-1)=\frac{(1-1)^{2t}}{2^{2t}(-1)^{t-4}}=0$$ $$G(\zeta^2)=G(i)=\frac{(i+1)^{2t}}{2^{2t}i^{t-4}}=\frac{2^tcis(\frac{\pi}{4}2t)}{2^{2t}i^{t-4}} \overset{t=25}{=}\frac{cis(\frac{\pi}{2})}{2^{25}i^1}=\frac{1}{2^{25}}$$ $$\text{De maneira similar,} \quad G(\zeta^6)=\frac{1}{2^{25}}$$ Para $G(\zeta)$, foquemos no numerador $(\zeta+1)^{2t}$: $$(\zeta+1)=(cis(2\pi/8)+1)=((\frac{\sqrt{2}}{2}+1)+\frac{\sqrt{2}}{2} i)=$$ $$\sqrt{2+\sqrt{2}}(\frac{\sqrt{2+\sqrt{2}}}{2}+\frac{\sqrt{2-\sqrt{2}}}{2} i)=\sqrt{2+\sqrt{2}} \:\: cis(\frac{\pi}{8})$$ $$\implies (\zeta+1)^{2t}=(2+\sqrt{2})^t \:\: cis(\frac{\pi}{8}2t)$$ $$G(\zeta^1)=\frac{(\zeta+1)^{2t}}{2^{2t}\zeta^{t-4}}=\frac{(2+\sqrt{2})^t}{2^{2t}}\frac{cis(\frac{\pi}{8}2t)}{cis(\frac{2\pi}{8}(t-4))} \overset{t=25}{=} -\frac{(2+\sqrt{2})^{25}}{4^{25}}$$ $$\text{De maneira similar,} \quad G(\zeta^7)= -\frac{(2+\sqrt{2})^{25}}{4^{25}} \quad \text{e} \quad G(\zeta^3)=G(\zeta^5)= -\frac{(2-\sqrt{2})^{25}}{4^{25}}$$ Portanto, $$\sum_{k=8x+5}{a_k} = \frac{G(\zeta^0)+G(\zeta^1)+\dots G(\zeta^7)}{8} = \frac{1+0+2(\frac{1}{2^{25}}-\frac{(2+\sqrt{2})^{25}}{4^{25}}-\frac{(2-\sqrt{2})^{25}}{4^{25}})}{8}$$ $$\implies p(25, 5)=\frac{1}{8}-\frac{1}{4} \frac{(2+\sqrt{2})^{25}+(2-\sqrt{2})^{25}-2^{25}}{4^{25}} = 0.12022793196…$$ A fórmula geral para qualquer $t$ da forma $8x+1$ fica $$p(t, 5)=\frac{1}{8}-\frac{1}{4} \frac{(2+\sqrt{2})^{t}+(2-\sqrt{2})^{t}-2^{t}}{4^{t}}$$

Resolução: Olavo Longo – Giant Steps