On Fri, Feb 06, 2004 at 06:04:25PM -0200, Nicolau C. Saldanha wrote: > > Cinco pessoas suspeitas de crime estão mantendo encontro secreto... ... > 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:
O que eu descobri experimentalmente com este programa é que bandido(n) = 1/(1+harmonic(n-1)) ~= 1/log(n) onde harmonic(n) = 1 + 1/2 + ... + 1/n. Relembrando, bandido(n) é a probabilidade de que o líder seja capturado se tanto ele quanto a polícia adotarem as estratégias ótimas como eu descrevi na mensagem anterior. []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 =========================================================================