[obm-l] Análise Combinatória
Caros colegas solicito ajuda na resolução do seguinte problema: Três russos, três biolerussos e três ucranianos vão ser organizados em uma fila. Determine quantas filas existem que não contêm dois conterrâneos em posição consecutiva. Dois colegas apresentaram resolução, um encontrou, para resposta, 174x3!x3!x3!=37.584, outro colega chegou a:283 824 (via o Princípio da Inclusão-Exclusão) Qualquer ajuda será muito útil. Obrigado. Osmundo Bragança
[obm-l] Re: [obm-l] Análise Combinatória
Certamente nao eh a segunda resposta... :) Digo, para arrumar as nacionalidades, voce tem 3 opcoes para o primeiro, 2 para o segundo, etc., para um total de 3.2^8=768 possibilidades. Mas isto estah errado, eh claro -- muitas dessas escolhas sao impossiveis, como por exemplo RBRBRBRUR, que teria 5 russos -- nao vale. Entao estou dizendo que sao MENOS que 768 possibilidades para a ordenacao das nacionalidades. Portanto, sao menos que 768.3!.3!.3! filas (permutando os individuos dentro de cada nacionalidade). Nao estou resolvendo o problema, mas sei que a resposta eh (bem!) menos que 768.6^3=165888. Faltou exclusao na inclusao-exclusao. :) :) :) Abraco, Ralph P.S.: Vou resolver o problema de um jeito computacional feio. Faco isso para mostrar que aas vezes vale a pena botar um pouco de algebra, fazer tudo ficar mecanico, e mandar brasa! R(a,b,c)=numero de filas COMECANDO COM UM RUSSO que tem a russos, b bielorussos e c ucranianos, contando soh nacionalidades, sem ter nacionalidades consecutivas B(a,b,c)=numero de filas COMECANDO COM UM BIELO etc etc U(a,b,c)=comecando com UCRANIANO Por outro lado, por simetria, R(a,b,c)=R(a,c,b)=B(b,a,c)=B(b,c,a)=U(c,a,b)=U(c,b,a), certo? Entao, uma fila comecando por R tem que continuar com B ou com U, usando um russo a menos: R(a,b,c)=B(a-1,b,c)+U(a-1,b,c)=R(b,a-1,c)+R(c,b,a-1) Esta recorrencia nao eh das piores se os numeros forem pequenos! Com coragem, isto mata o problema: R(3,3,3)=R(3,2,3)+R(3,3,2)=2R(3,3,2)=2.(R(3,2,2)+R(2,3,2))= =2.(2.R(2,2,2)+R(3,1,2)+R(2,3,1))=2.(4.R(2,2,1)+R(1,2,2)+R(2,1,2)+R(3,1,1)+R(1,3,1))= =2.(R(3,1,1)+5.R(2,2,1)+R(1,3,1)+R(1,2,2)) Agora que soh tem 5 fulanos na fila, acho que jah dah para calcular cada um pensando direto: R(3,1,1)=2 porque soh tem 3 lugares para por os russos nas 5 posicoes. Entao eh RURBR ou RBRUR. R(2,2,1)=R(2,1,1)+R(1,2,1)=4+1=5 (4=permutacoes de RBU sem comecar por R; 1=RBUB). R(1,3,1)=0 (haveria dois B consecutivos!) R(1,2,2)=2 (RBUBU ou RUBUB, soh) Entao R(3,3,3)=2.(2+25+2)=58 O que queremos eh R(3,3,3)+U(3,3,3)+B(3,3,3)=3.58=174 Minto, o que REALMENTE queremos eh isso vezes 3!.3!.3!. Eh, concordo com a primeira resposta. 2012/9/16 Osmundo Bragança barz...@dglnet.com.br Caros colegas solicito ajuda na resolução do seguinte problema: Três russos, três biolerussos e três ucranianos vão ser organizados em uma fila. Determine quantas filas existem que não contêm dois conterrâneos em posição consecutiva. Dois colegas apresentaram resolução, um encontrou, para resposta, 174x3!x3!x3!=37.584, outro colega chegou a:283 824 (via o Princípio da Inclusão-Exclusão) Qualquer ajuda será muito útil. Obrigado. Osmundo Bragança
Re: [obm-l] Análise Combinatória
Bom podemos fazer por inclusão e exclusão sim , mas acho que fica um pouco grande olha: Vamos considerar que sejam AAABBBCCC e façamos todos os anagramas onde nao existam letras iguais juntas e ao final multiplicaremos por 3!x3!x3!. Vamos contar todas as permutações que possuem dois AA juntos , que é só considerar que os dois AA sejam um único bloco. aí dará 8!/3!x3!=1120 e tirar os casos em que aparecem 3 A's juntos o tipo AAA que do mesmo jeito fica 7!/3!x3!=140 1120-140=980. Vamos contar aquelas em que aparecem dois A e dois B juntos contaremos (AA)A(BB)BCCC 7!/3!=840, e retiramos aqueles em que aparecem AAA e BB que dará 6!/3!=120 e depois retiramos aqueles em que aparecem AA e BBB que tambem dará 120 e acrescentaremos aqueles em que aparecem AAA e BBB que é (AAA)(BBB)CCC e dará 5!/3!=20 , assim dará 840-2x120+20=620. Agora amos ao procedimento final contar quantos anagramas aparecem AA BB e CC (AA)(BB)(CC)ABC que dará 6! e precisamos retirar os que ocorrem AAA ,BB e CC e depois o mesmo para AA,BBB e CC e o mesmo para AA , BB e CCC 5!x3=360 assim fica 720-360=360, porém precisamos colocar os que aparecem AA, BBB, e CCC, o mesmo para AAA,BBB e CC e os que contém AAA, BB e CCC que dará 4!x3=72 entao fica 360+72=432 e finalizando precisamos retirar aqueles em que aparecem AAA, BBB e CCC que é 3!=6 assim resultado dá 432-6=426. Agora podemos finalizar o problema fazendo 3x980-3x620+426=1506, e retiramos de todos os anagrams possíveis que são 9!/3!x3!x3!=1680, resposta final será 1680-1506=174 ou seja 174x(3!)^3=37584 modos distintos.Um dos seus colegas acertou o resultado Valeu, um abraço do Douglas Oliveira!! On Sun, 16 Sep 2012 10:08:40 -0300, Osmundo Bragança wrote: Caros colegas solicito ajuda na resolução do seguinte problema: Três russos, três biolerussos e três ucranianos vão ser organizados em uma fila. Determine quantas filas existem que não contêm dois conterrâneos em posição consecutiva. Dois colegas apresentaram resolução, um encontrou, para resposta, 174x3!x3!x3!=37.584, outro colega chegou a:283 824 (via o Princípio da Inclusão-Exclusão) Qualquer ajuda será muito útil. Obrigado. Osmundo Bragança
[obm-l] RES: [obm-l] Re: [obm-l] Análise Combinatória
Muitíssimo obrigado caro Ralph. Esta lista continua utilíssima para muitos professores. Um abraço. Osmundo. _ De: owner-ob...@mat.puc-rio.br [mailto:owner-ob...@mat.puc-rio.br] Em nome de Ralph Teixeira Enviada em: domingo, 16 de setembro de 2012 12:22 Para: obm-l@mat.puc-rio.br Assunto: [obm-l] Re: [obm-l] Análise Combinatória Ah, errei uma bobagem. Era: R(a,b,c)=R(a,c,b)=B(b,a,c)=B(c,a,b)=U(b,c,a)=U(c,b,a) a chave eh que o numero a tem que ficar na mesma posicao relativa em cada funcao. Mas dali para frente, estah correto assim mesmo. Abraco, Ralph 2012/9/16 Ralph Teixeira ralp...@gmail.com Certamente nao eh a segunda resposta... :) Digo, para arrumar as nacionalidades, voce tem 3 opcoes para o primeiro, 2 para o segundo, etc., para um total de 3.2^8=768 possibilidades. Mas isto estah errado, eh claro -- muitas dessas escolhas sao impossiveis, como por exemplo RBRBRBRUR, que teria 5 russos -- nao vale. Entao estou dizendo que sao MENOS que 768 possibilidades para a ordenacao das nacionalidades. Portanto, sao menos que 768.3!.3!.3! filas (permutando os individuos dentro de cada nacionalidade). Nao estou resolvendo o problema, mas sei que a resposta eh (bem!) menos que 768.6^3=165888. Faltou exclusao na inclusao-exclusao. :) :) :) Abraco, Ralph P.S.: Vou resolver o problema de um jeito computacional feio. Faco isso para mostrar que aas vezes vale a pena botar um pouco de algebra, fazer tudo ficar mecanico, e mandar brasa! R(a,b,c)=numero de filas COMECANDO COM UM RUSSO que tem a russos, b bielorussos e c ucranianos, contando soh nacionalidades, sem ter nacionalidades consecutivas B(a,b,c)=numero de filas COMECANDO COM UM BIELO etc etc U(a,b,c)=comecando com UCRANIANO Por outro lado, por simetria, R(a,b,c)=R(a,c,b)=B(b,a,c)=B(b,c,a)=U(c,a,b)=U(c,b,a), certo? Entao, uma fila comecando por R tem que continuar com B ou com U, usando um russo a menos: R(a,b,c)=B(a-1,b,c)+U(a-1,b,c)=R(b,a-1,c)+R(c,b,a-1) Esta recorrencia nao eh das piores se os numeros forem pequenos! Com coragem, isto mata o problema: R(3,3,3)=R(3,2,3)+R(3,3,2)=2R(3,3,2)=2.(R(3,2,2)+R(2,3,2))= =2.(2.R(2,2,2)+R(3,1,2)+R(2,3,1))=2.(4.R(2,2,1)+R(1,2,2)+R(2,1,2)+R(3,1,1)+R (1,3,1))= =2.(R(3,1,1)+5.R(2,2,1)+R(1,3,1)+R(1,2,2)) Agora que soh tem 5 fulanos na fila, acho que jah dah para calcular cada um pensando direto: R(3,1,1)=2 porque soh tem 3 lugares para por os russos nas 5 posicoes. Entao eh RURBR ou RBRUR. R(2,2,1)=R(2,1,1)+R(1,2,1)=4+1=5 (4=permutacoes de RBU sem comecar por R; 1=RBUB). R(1,3,1)=0 (haveria dois B consecutivos!) R(1,2,2)=2 (RBUBU ou RUBUB, soh) Entao R(3,3,3)=2.(2+25+2)=58 O que queremos eh R(3,3,3)+U(3,3,3)+B(3,3,3)=3.58=174 Minto, o que REALMENTE queremos eh isso vezes 3!.3!.3!. Eh, concordo com a primeira resposta. 2012/9/16 Osmundo Bragança barz...@dglnet.com.br Caros colegas solicito ajuda na resolução do seguinte problema: Três russos, três biolerussos e três ucranianos vão ser organizados em uma fila. Determine quantas filas existem que não contêm dois conterrâneos em posição consecutiva. Dois colegas apresentaram resolução, um encontrou, para resposta, 174x3!x3!x3!=37.584, outro colega chegou a:283 824 (via o Princípio da Inclusão-Exclusão) Qualquer ajuda será muito útil. Obrigado. Osmundo Bragança
[obm-l] RES: [obm-l] Análise Combinatória
Muitíssimo obrigado caro Douglas Oliveira. Um abraço do colega Osmundo Bragança. _ De: owner-ob...@mat.puc-rio.br [mailto:owner-ob...@mat.puc-rio.br] Em nome de douglas.olive...@grupoolimpo.com.br Enviada em: domingo, 16 de setembro de 2012 12:33 Para: obm-l@mat.puc-rio.br Assunto: Re: [obm-l] Análise Combinatória Bom podemos fazer por inclusão e exclusão sim , mas acho que fica um pouco grande olha: Vamos considerar que sejam AAABBBCCC e façamos todos os anagramas onde nao existam letras iguais juntas e ao final multiplicaremos por 3!x3!x3!. Vamos contar todas as permutações que possuem dois AA juntos , que é só considerar que os dois AA sejam um único bloco. aí dará 8!/3!x3!=1120 e tirar os casos em que aparecem 3 A's juntos o tipo AAA que do mesmo jeito fica 7!/3!x3!=140 1120-140=980. Vamos contar aquelas em que aparecem dois A e dois B juntos contaremos (AA)A(BB)BCCC 7!/3!=840, e retiramos aqueles em que aparecem AAA e BB que dará 6!/3!=120 e depois retiramos aqueles em que aparecem AA e BBB que tambem dará 120 e acrescentaremos aqueles em que aparecem AAA e BBB que é (AAA)(BBB)CCC e dará 5!/3!=20 , assim dará 840-2x120+20=620. Agora amos ao procedimento final contar quantos anagramas aparecem AA BB e CC (AA)(BB)(CC)ABC que dará 6! e precisamos retirar os que ocorrem AAA ,BB e CC e depois o mesmo para AA,BBB e CC e o mesmo para AA , BB e CCC 5!x3=360 assim fica 720-360=360, porém precisamos colocar os que aparecem AA, BBB, e CCC, o mesmo para AAA,BBB e CC e os que contém AAA, BB e CCC que dará 4!x3=72 entao fica 360+72=432 e finalizando precisamos retirar aqueles em que aparecem AAA, BBB e CCC que é 3!=6 assim resultado dá 432-6=426. Agora podemos finalizar o problema fazendo 3x980-3x620+426=1506, e retiramos de todos os anagrams possíveis que são 9!/3!x3!x3!=1680, resposta final será 1680-1506=174 ou seja 174x(3!)^3=37584 modos distintos.Um dos seus colegas acertou o resultado Valeu, um abraço do Douglas Oliveira!! On Sun, 16 Sep 2012 10:08:40 -0300, Osmundo Bragança wrote: Caros colegas solicito ajuda na resolução do seguinte problema: Três russos, três biolerussos e três ucranianos vão ser organizados em uma fila. Determine quantas filas existem que não contêm dois conterrâneos em posição consecutiva. Dois colegas apresentaram resolução, um encontrou, para resposta, 174x3!x3!x3!=37.584, outro colega chegou a:283 824 (via o Princípio da Inclusão-Exclusão) Qualquer ajuda será muito útil. Obrigado. Osmundo Bragança
[obm-l] exercício
Seja R um anel associativo cujos únicos ideais a direita são R e (0). Prove que R é um anel de divisão ou que R é um anel com um número primo de elementos no qual ab = 0 para todo a, b em R. Se R tem 1, consegui fazer. Seja a0. Tomei o ideal a direita aR, aR 0 pois a pertence a aR. Assim aR=R, portanto existe b tal que ab=1. Da mesma forma considero bR e chego que bR=R portanto existe c tal que bc=1.Assim ab=1 = (ab)c=1c = a(bc)=c = a(1)=c = a=c. Portanto ab=ba=1. Mas supondo que R não tem 1 não consegui terminar o exercício. Alguém tem alguma ideia?
