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,