Re: [obm-l] O JOGO DE RENCONTRE! - CORREÇÃO

[kleinad@xxxxxxxxxx]

Como prometi, aqui vai a "explicacao".

Como disse anteriormente, esse problema equivale a determar quantas das
permutações da matriz identidade nxn possuem ao menos um elemento não nulo
na diagonal.

Existe apenas uma matriz com n elementos 1 na diagonal, e não existe uma com
n - 1 elementos não nulos na diagonal sem que tenha o n-ésimo.

Para n - 2 elemtos não nulos (frase que passarei a abreviar por T - 2),
basta sabermos de quantas formas podemos escolher 2 das n colunas --> C(n,2)
= n!/(2!*(n - 2)!)

T - M em geral:
Precisamos combinar pares K_i, K_j, com i dif. de j. Como AQUI não importa
a "ordem" (pois queremos apenas determinar o número de matrizes possíveis,
ficando a ordem do jogo subentendida nos pares (linha=rodada,
coluna=numero)), podemos CHAMAR um elemento de k_1 e o que lhe associa de
k_m, pegar outro k_2 e CHAMAR seu associado de k_(m-1) e assim por diante,
sendo que estes m correspondem as m colunas em permutação entre elas.

Este k_i, k_j significa uma permutação entre a coluna i e a coluna j da
matriz identidade.

Quando chegamos a (m + 1)/2 (se m for ímpar) ou m/2 (se m for par), o número
de opções para a correspondência seguinte se repete. Por exemplo, para m = 5:

k_1 --> 4 opções
k_2 --> 3 opções
k_3 --> 3 opções
k_4 --> 2 opções
k_5 --> 1 opção

Deste modo, o termo geral é, para m colunas sem 1 na diagonal:

para m par:
T - 2A: (2A - 1)!*A*C(n, 2A), com A >=1 desde que possível

para m ímpar:
T - (2B + 1): (2B)!*B*C(n, 2B + 1), com B >=1 desde que possível

para m = 0 (é a própria matriz identidade) --> 1 opção

Como temos n! arrumações possíveis, basta considerarmos a some de tudo e
dividir por n!

S_a = Somatório de { (2A - 1)!*A*C(n, 2A) }, A variando de 1 ao inteiro
menor ou igual a (n - 1)/2 --> S_a corresponde aos termos pares

S_b = Somatório de { (2B)!*B*C(n, 2B + 1) }, B variando de 1 ao inteiro
menor ou igual a (n - 2)/2 --> S_b corersponde aos termos impares

+ 1, que é o "termo" zero

Assim, S = [1/(n!)]*[ 1 + S_a + S_b ], que na mensagem anterior eu
simplifiquei para S_a e S_b, e espero eu que de forma correta....


kleinad@webcpd.com escreveu:
>
>COrreçãozinha, em que eu troquei a ordem para não confundir sobre de que é o
>fatorial:
>
>Mais tarde eu espero conseguir explicar, mas creio que a solução é
>
>S = (1/n!)*[ 1 + S_a + S_b ], em que
>
>>>> S_a = Somatório de { A*(n!)/[ (n - 2A)!*2A ] }, com A variando de 1 até
>o inteiro menor ou igual a (n - 1)/2
>
>
>>>> S_b = Somatório de { B*(n!)/[ (n - 2B - 1)!*(2B + 1) ] }, com B variando
>de 1 até o inteiro menor ou igual a (n - 2)/2
>
>Claro que, para incorporar S_a, devemos ter n >=3 , e, para incorporar S_b,
>devemos ter n >= 4.
>
>=========================================================================
>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
>=========================================================================
>

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