[obm-l] Re: [obm-l] Dúvida de Combinatoria e PUTNAM

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

Ola Leonardo,
Tudo Legal ?

O problema esta mal formulado... Para ver isso, suponha N=3. Pelo enunciado 
do problema deveriamos formar N/2=1.5 grupos ! Um absurdo, pois neste 
contexto nao tem sentido falar em FRACAO DE GRUPO !

Todavia, da sua segunda pergunta ( O que Permutacao Caotica ) e possivel 
deduzir o que voce quer ...

Tendo N-casais ( marido e mulher )de quantas maneiras diferentes pode-se 
formar N grupos, cada grupo com duas pessoas, de formar que em nenhum dos 
grupos um marido fique com sua mulher ?

A solucao deste problema e uma das aplicacoes das permutacoes caoticas.

Considere 3 letras, ABC, e suponha que esta disposicao inicial seja a 
posicao natural ( ou referencial ) de cada uma das letras : TODA PERMUTACAO 
DESTAS TRES LETRAS NA QUAL NENHUMA LETRA OCUPA SUA POSICAO NATURAL E DITA 
UMA PERMUTACAO CAOTICA.

Assim, sao exemplos de permutacoes caoticas :
BCA, CAB

Nao sao exemplos de permutacoes caoticas :
ACB ... ( pois a letra "A" esta na posicao natural )
CBA ... ( pois a letra "B" esta na posicao natural )

E importante perceber que :

O conceito de permutacao caotica depende de uma permutacao considerada 
natural ou referencial, em relacao a qual decidimos se uma outra permutacao 
dada e caotica ou nao.

Quem primeiro abordou as permutacoes caoticas foi Nicolau Bernoulli, que 
propos o problema a Euler. Este ultimo se interessou pela questao e a 
resolveu de uma outra forma, diferente da de Nicolau. Se chamaramos de PC(N) 
o numero de permutacoes caoticas de N objetos, dois a dois distintos, e 
possivel provar que :

PC(N) = N!(1/2!  -   1/3!  + ... +-  1/N!)

A titulo de exemplo, com 3 letras nos podemos formar :

PC(3) = 3!(1/2! - 1/3!) = 3 - 1 = 2 permutacoes caoticas

Bom, agora que voce sabe o que e permutacao caotica e conhece a formula com 
que as calculamos, voce pode resolver a reformulacao do seu problema. 
Imagine a disposicao :

H1,H2,H3,...,Hn
M1,M2,M3,...,Mn

Ou seja, cada homem sobre a sua mulher, o que vamos considerar a disposicao 
natural ( e legal ! ). Qualquer permutacao caotica dos homens fara com que 
nao existe ao menos um grupo onde um homem estara sobre a sua mulher, ou 
seja, a formulacao correta de seu problema se resolve calculando-se o numero 
de permutacoes caoticas.

Finalmente, e importante registrar que o nosso muito estimado Prof Morgado, 
membro desta lista, publicou um livro de Analise Combinatoria onde ele 
aborda este tema e muitos outros mais, tais como os Lemas de Kaplanski. Em 
minha opiniao, este livro e o que ha de melhor sobre o tema, aqui no Brasil. 
E acredito que todo estudante que deseja entender corretamente este tema 
basta estudar por este livro.

Um Abraco a Todos
Paulo Santa Rita
5,1515,010802

Em Tempo : Acabo de receber uma mensagem do Prof Jonh Scholes no qual ele me 
autoriza traduzir e divulgar todo o material PUTNAM. Vou fazer as traducoes 
e disponibilizar para todos, como material de treinamento e incentivo para 
as olimpiadas universitarias.









>From: "leonardo mattos" <leonar_matt@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: [obm-l] Dúvida de Combinatoria
>Date: Thu, 01 Aug 2002 03:42:09 +0000
>
>
>
>Tendo n-casais(marido e mulher)de quantas maneiras diferentes pode-se 
>formar n/2 grupos de tal forma q em que cada grupo contenha 2 pessoas,ou 
>seja,não importa a ordem.Uma maneira seria 
>[(H1,M1),(H2,M2),(H3,M3)...,(Hn,Mn)].
>
>O que é permutação caótica?
>
>
>
>
>
>_________________________________________________________________
>Converse com seus amigos online, faça o download grátis do MSN Messenger: 
>http://messenger.msn.com.br
>
>=========================================================================
>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
>O administrador desta lista é <nicolau@mat.puc-rio.br>
>=========================================================================




_________________________________________________________________
Converse com seus amigos online, faça o download grátis do MSN Messenger: 
http://messenger.msn.com.br

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================