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
