RE: [obm-l] permutacap caotica..

["LEANDRO L RECOVA" <leandrorecova@xxxxxxx>]

Paulo,

Parabens pelo email. Achei sensacional sua colocacao !

Leandro
Los Angeles, CA.


>From: "Paulo Santa Rita" <paulosantarita@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: RE: [obm-l] permutacap caotica..
>Date: Thu, 12 Oct 2006 18:17:44 +0000
>
>Ola Vinicius e demais
>colegas desta lista ... OBM-L,
>(escreverei sem acentos)
>
>Vou aproveitar este feriado para responder esta solicitacao com 
>tranquilidade.
>
>1) DEFINICAO
>
>Uma permutacao de elementos e dita caotica se nenhum de seus elementos 
>ocupa a posicao
>
>original, vale dizer, fixamos previamente uma particular permutacao que 
>imnplicitamente
>
>especifica as posicoes originais originais dos elementos e procuramos 
>determinar de quantas
>
>maneiras podemos permutar estes mesmos elementos de maneira que nenhum 
>deles permaneca em
>
>sua posicao original. Exemplificando :
>
>EXEMPLO 1
>
>Vamos considerar a permutacao ABCD, tomada como o referencial ( inercial ? 
>). A permutacao ACDB nao e
>
>caotica pois o elemento "A" mantem a posicao original. Ja a permutacao DABC 
>e caotica, pois
>
>nenhum elemento mantem a posicao original.
>
>2) ASPECTOS HISTORICOS
>
>As PERMUTACOES CAOTICAS surgiram num problema proposto ao Euler numa carta 
>que o Nicolau
>
>Bernoulli lhe remeteu. Em linhas gerais o problema era assim ...
>
>( Nicolau propoe a Euler ) De quantas maneiras N cartas, duas a duas 
>distintas,  podem ser
>
>colocadas em N envelopes com destinatarios previamente preenchidos de 
>maneira que nenhuma
>
>destinatario receba a carta que corretamente  deveria lhe ter sido remetida 
>?
>
>O Euler gastou algum tempo para resolver o problema, mas a solucao que ele 
>encontrou e
>
>longa, grosseira e sem inteligencia. Mas ...  a solucao do Nicolau ... 
>Belissima ! Faz jus
>
>tanto a tradicao da familia Bernoulli quanto a tradicao dos Nicolau's que 
>conhecemos ...
>
>Eis o TRUQUE DO NICOLAU :
>
>
>3) EQUACAO FUNCIONAL
>
>Para facilitar a esposicao, FIXE no lado esquerdo a permutacao ABCDEFG. 
>Seja C(7) o numero
>
>total de permutacoes caoticas. Agora, com o lado direito IMAGINE dois casos 
>:
>
>(1) Todas as permutacoes caoticas nas quais a letra "A" esta na posicao da 
>letra "B" e a
>
>letra "B" esta na posicao da letra "A". Quantas permutacoes caoticas sao 
>possiveis ?
>
>Claramente : C(5), pois apenas iremos permutar caoticamente as 5 outras 
>letras restante
>
>(2) Todas as permutacoes caoticas nas quais a letra "A" esta na posicao da 
>letra "B" e a
>
>letra "B" NAO ESTA na posicao da letra "A". Quantas permutacoes sao 
>possiveis ? Aqui comeca
>
>o TRUQUE DO NICOLAU ... a letra "B" tera 5 posicoes para ocupar e as demais 
>letras tambem,
>
>vale dizer, tudo sucede como se estivessemos permutando caoticamente 6 
>elementos. Logo, a
>
>resposta e C(6).
>
>Ora, os casos (1) e (2) encerram TODAS as permutacoes caoticas nas quais a 
>letra "A" esta na
>
>posicao da letra "B", isto e, o total de permutacoes em que a letra "A" 
>esta na posicao da
>
>letra "B" e C(5) + C(6). Agora,  colocando a letra "A" sucessivamente nas 
>posicoes das letra
>
>"C", ...,"G" e repetindo para cada caso os raciocinios (1) e (2) acima e 
>facil ver que :
>
>C(7) = 6*( C(5) + C(6) )
>
>Esta tecnica, obviamente, pode ser extendida para o caso de N elementos. 
>Assim :
>
>C(N) = (N-1) * [ C(N-2) + C(N-1) ]
>
>Que e a "equacao funcional" para as permutacoes caoticas.
>
>
>4) FORMULA EXPLICITA
>
>Em geral, o estudante iniciante busca uma formula explicita, fechada, com a 
>qual fica facil
>
>fazer computacoes diretas. E facil obter uma tal expressao. Eis como :
>
>C(N) = (N-1) * [ C(N-2) + C(N-1) ]
>C(N) - N*C(N-1) = -[c(N-1) - (n-1)*C(N-2) ]
>
>substituindo N sucessivamente por 3, 4, ... ate N, teremos :
>
>C(3) - 3*C(2) = -[ C(2) - 2*C(1) ]
>C(4) - 4*C(3) = -[ C(3) - 3*C(2) ]
>...
>C(N) - N*C(N-1) = -[c(N-1) - (n-1)*C(N-2) ]
>
>Multiplicando membro a membro estas N-2 igualdades e eliminado os fatores 
>iguasi que estao nos dois lados do sinal de igualdade :
>
>C(N) - N*C(N-1) = [(-1)^(N-2)]*[C(2) - 2*C(1) ]
>Como obviamente C(1)=0, C(2)=1 e (-1)^(N-2) = (-1)^N :
>
>C(N) - N*C(N-1) = (-1)^N
>
>Dividindo tudo por N! teremos :
>
>C(N)/N!   +   C(N-1)/(N-1)!   =   [(-1)^N]/N!
>
>Substituindo N por 2, 3, ... ate N e somando as N-1 equacoes, vem :
>
>C(N) = (N!)*{ 1/2!  -   1/3!   +   1/4!   - ... + [(-1)^N]/N! }
>
>Que e a formula explicita para permutacoes caoticas
>
>
>5) ALEM DE EULER E NICOLAU
>
>
>Alguem ja disse que "Os matematicos nao nascem, eles surgem". Sem entrar no 
>merito ou interpretacao do aforismo, me parece que ele encerra uma grande 
>dose de verdade ... quantos de nos nao tem alguma historia singela de 
>(RE)descobertas e pesquisas cientificas quando ainda era uma crianca ? 
>Olhando para a historia, para a vida de alguns colegas matematicos e para 
>mim mesmo, parece-me que tal fenomeno e mais a regra que a excecao ...
>
>Neste problema de Matematica Elementar e possivel exercitar esta ALMA ou 
>ESPIRITO que se admira e se maravilha diante do desconhecido e sem receios 
>ou frescuras se lanca em especulacoes e pesquisas solitarias. O confronto 
>com o desconhecido, com o misterio, e uma das mais empolgantes facetas da 
>investigacao ...
>
>PROBLEMA : Sejam dadas DUAS permutacoes caoticas, digamos, ABCDEFG e 
>BCDEFGA. Quantas permutacoes SIMULTANEAMENTE caoticas em relacao as duas 
>podemos construir ?
>
>Euler e Nicolau, pelo que sei, nao resolveram esta questao e nem ao menos 
>citaram-na, o que a torna muito mais interessante. Digamos que eles 
>resolveram O CASO 1, isto e, quanto fixamos apenas uma permutacao. O 
>problema se refere ao caso 2. Poedemos portanto por :
>
>C(N,1) = (N!)*{ 1/2!  -   1/3!   +   1/4!   - ... + [(-1)^N]/N! }
>
>Qual a expressao para C(N,2), a resposta do problema proposto ? Bom, 
>claramente que C(N,N-1)=1. Assim, ja temos dois dados :
>
>C(N,1) = (N!)*{ 1/2!  -   1/3!   +   1/4!   - ... + [(-1)^N]/N! }
>C(N,N-1) = 1 = (N!)*{ 1/N!}
>
>Isto sugere que para o caso P, a expressao tem a forma :
>
>C(N,P) = (N!)*{ 1/P! - ... [(-1)^f(N)]/N! }
>
>Este caminho e o PRIMEIRO CAMINHO : tentar descobrir atraves da FORMULA 
>EXPLICITA a cara da expressao para o caso P.
>
>Um SEGUNDO CAMINHO seria tentar reformar ou generalizar o raciocinio do 
>Nicolau e chegar a uma EQUACAO FUNCIONAL tal como ele chegou. Essa linha de 
>investigacao tambem parece promissora, pois pode suceder que uma expressao 
>explicita dependa de alguma relacao mantida entre os elementos das 
>permutacoes fixas em relacoes as quais buscamos as caoticas
>
>Note que este problema esta diretamente ligado a questao dos QUADRADOS 
>LATINOS que, ate onde eu sei, ainda e uma questao em aberto da Matematica 
>elementar. Mas o mais importante aqui nao e resolver o problema. E muito 
>mais tentar e lancar a esta aventura do pensamento, a este contato e 
>confrontacao com o desconhecido que e quase ou muito proxima da experiencia 
>religiosa, quando sabemos que DO OUTRO LADO existe algo real, belo e 
>verdadeiro e que com a nossa mente nos podemos descerrar.
>
>Um Abraco a Todos
>Paulo Santa Rita
>5,1513,120906
>
>>From: vinicius aleixo <viniciusaleixo@yahoo.com.br>
>>Reply-To: obm-l@mat.puc-rio.br
>>To: obm-l@mat.puc-rio.br
>>Subject: [obm-l] permutacap caotica..
>>Date: Wed, 11 Oct 2006 22:04:07 -0300 (ART)
>>
>>   Quantos anagramas da palavra VESTIBULAR não possuem nenhuma letra em 
>>sua
>>   posição original?
>>
>>
>>   Alguem poderia aproveitar e me explicar como funciona essa tal de 
>>permutacao caotica?de onde veio, como deduzo a formula e talz...
>>
>>
>>   vlw!
>>
>>   vinicius
>>
>>
>>---------------------------------
>>  Novidade no Yahoo! Mail: receba alertas de novas mensagens no seu 
>>celular. Registre seu aparelho agora!
>
>_________________________________________________________________
>Insta-le já o Windows Live Messenger. A nova geração do messenger. 
>http://get.live.com/messenger/overview
>
>=========================================================================
>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
=========================================================================