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

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

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