Solução do Giant Puzzle #7 – Kombucha

Parabéns a todos que se desafiaram a solucionar o Giant Puzzle #7!

Conseguiram resolver este puzzle:

  1. Igor Magalhães
  2. Gustavo Queiroz

O Problema

N amigos estão sentados numa mesa redonda, onde cada cadeira é numerada de 1 a N no sentido horário.

Existe uma caneca de Kombucha na mesa que inicialmente se encontra com a pessoa sentada na cadeira 1.

Sabe-se que toda vez que uma pessoa bebe um pouco do Kombucha, ela passa a caneca para a pessoa sentada à sua direita com probabilidade n/(N+1) e para a pessoa à sua esquerda com probabilidade (N-n+1)/(N+1), onde n é o número de sua cadeira.

Considere que o ato de uma pessoa passar uma caneca leva uma unidade de tempo.

a) Suponha que, caso a pessoa que recebe a caneca já tenha provado o Kombucha antes, ela apenas repassa a caneca no sentido em que recebeu. Calcule o número esperado de unidades de tempo passadas de forma que todos na mesa tenham provado o Kombucha para N=30 e N=500.

b) Suponha que, caso a pessoa que recebe a caneca já tenha provado o Kombucha antes, ela prova o Kombucha novamente e passa para a pessoa à sua direita com probabilidade n/(N+1) e para a pessoa à sua esquerda com probabilidade (N-n+1)/(N+1). Calcule o número esperado de unidades de tempo passadas de forma que todos na mesa tenham provado o Kombucha para N=10 e N=30.

Foi solicitado que as respostas fossem enviadas em notação científica com 7 casas de precisão.

 

A Solução

Item A

Definimos o estado j pela tripla (prev, ext1, ext2), sendo prev o último nó ativo (em que se precisou decidir ir pela esquerda ou direita) anterior ao nó atual, ext1 o nó de menor numeração já visitado, e ext2 o nó de maior numeração já visitado. Além disso, nj significa o número de nós visitados até chegar ao estado j (único para cada estado).

Dado um estado j, há mais de um valor possível para tj ( a quantidade de tempo decorrida do início até se chegar no estado j).

Seja X o número de passos do estado atual S até o final, o valor esperado para o número de passos que se leva do estado j até um estado terminal é denotado por E[X|S=j] = Ej. Dessa forma, pode-se escrever

Usando probabilidade total:

Por outro lado, se j’ e  j” são os estados alcançados partindo de j mantendo e invertendo, respectivamente, o último sentido, então

 

Mas, da forma como definimos os estados, p ( tj = k | S = j) = p ( t’j = k + 1 | S = j’ ) = p ( t”j = k + nj | S = j” ). Dessa forma,

Com isso, é formado um sistema de equações lineares. Basta implementar a solução no python. Observação: para N = 50 é preciso usar matrizes esparsas, pois há 495015 diferentes estados (não terminais).

Item B

Definimos e estado j pela quádrupla (current, prev, ext1, ext2), sendo current o nó atual, prev o último nó visitado antes do nó atual, ext1 o nó de menor numeração já visitado e ext2 o nó de maior numeração já visitado.

Para os estados em que é possível decidir qual o próximo estado,

sendo e(j) e d(j), respectivamente, os estados obtidos a partir do estado j e passando a caneca para a esquerda e direita (cujas probabilidades são, respectivamente, pe(j) e pd(j).

Para os estados em que o próximo estado está determinado,

sendo next(j) o estado posterior a j.

Dessa forma, temos um sistema linear, e basta implementar a solução no python.

 

– Solução submetida por Igor Magalhães

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses cookies to improve your browsing, the data is stored for analysis and production of content tailored to your interest. By clicking accept you agree to store cookies on your device. To learn more, read our Privacy Policy.