Re: [obm-l] Xadrez

["Fabio Dias Moreira" <fabio@xxxxxxxxxxxxxxxxxxx>]

Claudio Buffara said:
> on 07.05.04 19:16, Welma Pereira at welma_mat@hotmail.com wrote:
>
>> Alguém poderia me ajudar com um problema sobre xadrez envolvendo
>> cadeia de Markov?
>>
>> O problema é o seguinte
>>
>> Um rei se mexe em um tabuleiro de xadrez escolhendo com a mesma
>> probabilidade um dos lances possiveis.Qual a probabilidade que após um
>> número grande de lances o rei se encontre em uma das 4 casas
>> centrais(d4,e4,d5,e5)? e  Qual a probabilidade que se encontre em um
>> dos 4 cantos(a1,h1,a8,h8)?
>>
> Forme a matriz de transicao P desse sistema (uma matriz 64x64), calcule
> P^n e veja o que acontece quando n -> infinito.
>
> Por exemplo, numere os quadrados do tabuleiro da seguinte forma:
> 01  02  03  ...  07  08
> 09  10  11  ...  15  16
> ..  ..  ..  ...  ..  ..
> 57  58  59  ...  63  64
>
> Em seguida, calcule p(i,j) = probabilidade do rei ir do quadrado i ao
> quadrado j.
>
> Por exemplo:
> p(k,k) = 0, para todo k; p(1,2) = 1/3; p(3,10) = 1/5; p(10,11) = 1/8;
> p(10,12) = 0.
>
> Eh meio sacal de fazer no braco, mas com um computador eh bem facil
> preencher a matriz P e calcular P^n para n grande.
> [...]

Na realidade, dá para fazer algo mais esperto: o tabuleiro de xadrez
possui dois eixos de simetria e um centro de simetria, logo conjuntos de 4
(ou até de 8) casas têm associações naturais, logo só é necessária uma
matriz 10x10:

01233210
14566541
25788752
36899863
36899863
25788752
14566541
01233210

Além disso, se lim A^n quando n->inf vale B, então AB = B, logo B é uma
matriz cujas colunas são todas autovetores de A, logo é possível obter uma
resposta exata para o valor dessas probabilidades.

[]s,

-- 
Fábio "ctg \pi" Dias Moreira


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