Re: [obm-l] VELHO PROBLEMA SOB NOVA ROUPAGEM

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

> Cinco pessoas suspeitas de crime estão mantendo encontro secreto no porão de 
> um edifício. Do lado de fora, um policial, com ordens de seguir o chefe do 
> bando, espera que eles se dispersem. O policial sabe que o homem em que está 
> interessado é o mais alto do grupo, e tal é o único meio de que dispõe para 
> distingui-lo dos demais. Por medida de cautela, os homens reunidos abandonam
> o edifício um de cada vez. O intervalo entre saídas sucessivas é tão grande
> que, se o policial esperar pelo próximo, antes de seguir qualquer deles,
> perderá a oportunidade de acompanhá-lo. Se os suspeitos deixam o encontro em
> ordem aleatória, qual a melhor estratégia a ser adotada pelo policial?  Se
> adotar a melhor estratégia, qual a possibilidade de ser efetivamente o chefe
> a pessoa que ele vier a seguir?

Minha interpretação deste primeiro item do problema é que ele é igual
ao problemas dos números na urna. A estratégia do policial deve ser
a de deixar fugir os primeiros i suspeitos e a partir daí pegar
o primeiro que for mais alto do que os i que fugiram no início.
Estamos com isso supondo que o policial não tem nenhuma noção da altura
média dos suspeitos, o que como alguém observou é um pouco artificial.
Este problema foi discutido recentissimamente, não vou repetir:
o melhor valor de i é aproximadamente n/e (onde n é o número de bandidos)
e a probabilidade de que o líder dos bandidos seja preso é aprox. 1/e.

> Agora, entretanto, o líder sabe da existência do 
> policial. (Contudo, o líder não o diz a seus companheiros por ter tido culpa 
> no atrair o policial.) Os membros da quadrilha saem aleatóriamente, tal como 
> antes o fizeram, mas o líder escolhe o momento de sair. Quais as melhores 
> estratégias que o policial e o líder podem escolher e, presumindo que as 

Minha interpretação aqui é a seguinte. O fato de que a polícia está
esperando do lado de fora, e o fato de que eles vão seguir uma estratégia
conforme a discutida acima é conhecimento comum entre polícia e líder
dos bandidos (o líder sabe que a polícia está lá, a polícia sabe que ele
sabe, ele sabe que a polícia sabe que ele sabe e assim por diante).
O valor de i não é conhecido pelo líder dos bandidos, claro:
a polícia selecionará, no último instante, para que o líder não descubra,
o valor de i aleatoriamente entre 0 e n-1 (com uma certa distribuição
de probabilidades que depois veremos qual é, e que não é a uniforme).
O líder dos bandidos escolhe um número j, também entre 0 e n-1,
deixa sairem j dos seus companheiros antes dele e então sai.
Ele escolhe j sem saber quais serão os j companheiros que irão antes dele.
O valor de j também é escolhido aleatoriamente no último instante.

A pergunta é: quais as distribuições de probabilidade que polícia e
líder dos bandidos devem usar para que:

* Se a polícia sabe a distribuição de probabilidade que o líder
  dos bandidos vai usar (mas não j, o resultado do sorteio),
  ela percebe que a sua estratégia e a melhor possível, ou seja,
  a que torna máxima a probabilidade de captura.

* Se o líder dos bandidos sabe a distribuição de probabilidade que 
  a polícia vai usar (mas não i, o resultado do sorteio),
  ele percebe que a sua estratégia e a melhor possível, ou seja,
  a que torna mínima a probabilidade de captura.

Podemos montar uma matriz nxn A cuja entrada (i,j) indica a probabilidade
de captura se polícia toma i e bandido toma j. É fácil ver que
A[i,j] = i/j se 0 < i <= j, A[0,0] = 1 e A[i,j] = 0 caso contrário.
Para n = 5,

     [   1    0    0    0    0   ]
     [   0    1   1/2  1/3  1/4  ]
 A = [   0    0    1   2/3  2/4  ]
     [   0    0    0    1   3/4  ]
     [   0    0    0    0    1   ]

Sejam u e v em R^5 vetores com coordenadas não negativas e soma das
coordenadas igual a 1: u e v representam as distribuições de
probabilidade para i e j, respectivamente. A probabilidade de captura é

p = u^t A v.

Queremos encontrar um ponto de sela para a função p. Um pouco de cálculo
nos dá
u = [12/37, 12/37, 6/37, 4/37, 3/37] 
v = [12/37, 6/37, 4/37, 3/37, 12/37] 
e
p = 12/37.

Segue abaixo um programinha em maple para calcular esta probabilidade
para outros valores de n. As fórmulas são um pouco diferentes pq o maple
prefere indexar a partir de 1.


bandido := proc(N) local i, j, p, A, B, C, z, u1, v1:
A := array(1..N,1..N,sparse):
B := array(1..N,1..N,sparse):
C := array(1..N,1..N,sparse):
z := array(1..N): for i to N do z[i] := 1: od:
A[1,1] := 1: B[1,1] := 1: C[1,1] := 1:
for i from 2 to N do for j from i to N do
        A[i,j] := (i-1)/(j-1): B[i,j] := (i-1)/(j-1): C[i,j] := (i-1)/(j-1):
od: od:
for i from 2 to N do for j to N do
        B[j,i] := B[j,i] + 1:
        C[i,j] := C[i,j] + 1:
od: od:
u1 := linsolve(transpose(C),z):
v1 := linsolve(B,z):
p := multiply(transpose(u1),A,v1):
end proc:

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================