> 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 =========================================================================