Parabéns a todos que se desafiaram a solucionar o Giant Puzzle #7!
Conseguiram resolver este puzzle:
- Igor Magalhães
- 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
