[obm-l] RE: [obm-l] Re: [obm-l] Análise Combinatória
Obrigado Hugo. Excelente. Gostei muito da sua solução. Abç. Date: Thu, 18 Feb 2016 13:00:19 -0200 Subject: [obm-l] Re: [obm-l] Análise Combinatória From: hfernande...@gmail.com To: obm-l@mat.puc-rio.br Seja A = { x | x é anagrama de PIRAMIDAL começando por PIR, nessa ordem } e B = { x | x é anagrama de PIRAMIDAL cujas últimas 4 letras são A, D, I, L, não necessariamente nessa ordem } Queremos calcular n(A U B) = n(A) + n(B) - n(A interseção B) Calculando, temos: n(A) = P 6,2 = 6!/2! = 360 (fixo PIR e permuto AMIDAL, com repetição dos 2 A's) n(B) = P4 * P5 = 4! * 5! = 120 * 24 = 2880 ( permuto PIRAM nas cinco primeiras posições E permuto IDAL nas 4 últimas) n(A interseção B) = P2 * P4 = 2! * 4! = 48 ( fixo PIR, permuto AM nas duas posições seguintes E IDAL nas 4 últimas) Logo, n(A U B) = 2880 + 360 - 48 = 3192 Att. Hugo Fernando Marques FernandesMinistro Leigo da Igreja Episcopal Anglicana do Brasil (IEAB)Diocese Anglicana do RJ - DARJCatedral do Redentor Em 18 de fevereiro de 2016 12:09, Marcos Xavier <mccxav...@hotmail.com> escreveu: Prezados amigos, preciso de ajuda para resolver esse problema. Quantos são os anagramas da palavra PIRAMIDAL que começam por PIR, nessa ordem, ou cujas últimas 4 letras são A, D, I, L, não necessariamente nessa ordem? Gabarito: 3192. Obrigado pela ajuda. Marcos X.
[obm-l] Re: [obm-l] Análise Combinatória
Seja A = { x | x é anagrama de PIRAMIDAL começando por PIR, nessa ordem } e B = { x | x é anagrama de PIRAMIDAL cujas últimas 4 letras são A, D, I, L, não necessariamente nessa ordem } Queremos calcular n(A U B) = n(A) + n(B) - n(A interseção B) Calculando, temos: n(A) = P 6,2 = 6!/2! = 360 (fixo PIR e permuto AMIDAL, com repetição dos 2 A's) n(B) = P4 * P5 = 4! * 5! = 120 * 24 = 2880 ( permuto PIRAM nas cinco primeiras posições E permuto IDAL nas 4 últimas) n(A interseção B) = P2 * P4 = 2! * 4! = 48 ( fixo PIR, permuto AM nas duas posições seguintes E IDAL nas 4 últimas) Logo, n(A U B) = 2880 + 360 - 48 = 3192 Att. *Hugo Fernando Marques Fernandes* Ministro Leigo da Igreja Episcopal Anglicana do Brasil (IEAB) Diocese Anglicana do RJ - DARJ Catedral do Redentor Em 18 de fevereiro de 2016 12:09, Marcos Xavierescreveu: > Prezados amigos, preciso de ajuda para resolver esse problema. > > Quantos são os anagramas da palavra PIRAMIDAL que começam por PIR, nessa > ordem, ou cujas últimas 4 letras são A, D, I, L, não necessariamente nessa > ordem? > > Gabarito: 3192. > > Obrigado pela ajuda. > > Marcos X. >
[obm-l] Re: [obm-l] Análise combinatória
Gabriel: É justamente esse último 5! que eu tenho dúvidas. A permutação é circular, certo? Mesmo assim multiplicamos por 5!? Sim, percebi o erro de digitação, mas isso não é o principal. Em 10 de dezembro de 2015 17:23, Gabriel Tostesescreveu: > A respostas 45360 está correta... Numere as cadeiras de 1 a 15 e dívida em > 3 em casos: > 1-> 15 ocupada > 2-> 1 ocupada (análogo ao 1º) > 3-> 1 e 15 vazias. > > No primeiro caso temos que 1 e 14 devem estar vazias, logo, temos 4 > pessoas para distribuir nas 12 cadeiras restantes... > Como cada pessoa deve ocupar uma dessas cadeiras restam 8 vazias pra > distribuir entre as pessoas, mas entre duas pessoas deve ter ao menos > cadeira vazia, então -> 9!/5!x4!=136 > No terceiro caso temos 13 cadeiras pra colocar 5 pessoas, logo 8 vazias, > mas entre duas pessoas devemos ter uma cadeira vazia pelo menos uma vazia > -> 9!/4!x5!=136 > Total-> (2x136+136)x5!=45360 > > On Dec 10, 2015, at 16:45, Vanderlei Nemitz wrote: > > Pessoal, gostaria de uma ajuda com essa questão. Vi em um site a resposta > 45360, mas não concordo. Encontrei um valor bem menor. Obrigado! > > Vanderlei > > *Cinco pessoas devem se sentar em 15 cadeiras colocadas em torno de uma > mesa circular. De quantos modos isso pode ser feito se não deve haver > ocupação simultânea de duas cadeiras adjacentes? * > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Re: [obm-l] Análise combinatória
Sim... Dividi em casos pra "tirar" a permutacao circular. O 136 de cada caso significa 136 modos de organizar as Cadeiras em "vazias" e "com Pessoas". Temos 5! Maneiras de distribuir as Pessoas nelas. > On Dec 10, 2015, at 17:34, Vanderlei Nemitzwrote: > > Gabriel: > É justamente esse último 5! que eu tenho dúvidas. A permutação é > circular, certo? Mesmo assim multiplicamos por 5!? Sim, percebi o erro de > digitação, mas isso não é o principal. > > Em 10 de dezembro de 2015 17:23, Gabriel Tostes escreveu: >> A respostas 45360 está correta... Numere as cadeiras de 1 a 15 e dÃvida em >> 3 em casos: >> 1-> 15 ocupada >> 2-> 1 ocupada (análogo ao 1º) >> 3-> 1 e 15 vazias. >> >> No primeiro caso temos que 1 e 14 devem estar vazias, logo, temos 4 pessoas >> para distribuir nas 12 cadeiras restantes... >> Como cada pessoa deve ocupar uma dessas cadeiras restam 8 vazias pra >> distribuir entre as pessoas, mas entre duas pessoas deve ter ao menos >> cadeira vazia, então -> 9!/5!x4!=136 >> No terceiro caso temos 13 cadeiras pra colocar 5 pessoas, logo 8 vazias, mas >> entre duas pessoas devemos ter uma cadeira vazia pelo menos uma vazia -> >> 9!/4!x5!=136 >> Total-> (2x136+136)x5!=45360 >> >>> On Dec 10, 2015, at 16:45, Vanderlei Nemitz wrote: >>> >>> Pessoal, gostaria de uma ajuda com essa questão. Vi em um site a >>> resposta 45360, mas não concordo. Encontrei um valor bem menor. Obrigado! >>> >>> Vanderlei >>> >>> Cinco pessoas devem se sentar em 15 cadeiras colocadas em torno de uma mesa >>> circular. De quantos modos isso pode ser feito se não deve haver >>> ocupação simultânea de duas cadeiras adjacentes? >>> >>> -- >>> Esta mensagem foi verificada pelo sistema de antivÃrus e >>> acredita-se estar livre de perigo. >> >> -- >> Esta mensagem foi verificada pelo sistema de antivÃrus e >> acredita-se estar livre de perigo. > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Análise combinatória
Mas então é levado em consideração a posição relativa das pessoas e das cadeiras vazias? Por exemplo, se um pessoa A está nas mesmas posições relativas em relação às pessoas B, C, D, E, mas ao seu lados estão outras cadeiras vazias, a distribuição é considerada diferente? Pois caso não seja, pensei que deveríamos multiplicar por (5 - 1)! = 24. Claro que meu raciocínio pode estar falho! Em 10 de dezembro de 2015 17:45, Gabriel Tostesescreveu: > Sim... Dividi em casos pra "tirar" a permutacao circular. O 136 de cada > caso significa 136 modos de organizar as Cadeiras em "vazias" e "com > Pessoas". Temos 5! Maneiras de distribuir as Pessoas nelas. > On Dec 10, 2015, at 17:34, Vanderlei Nemitz wrote: > > Gabriel: > É justamente esse último 5! que eu tenho dúvidas. A permutação é > circular, certo? Mesmo assim multiplicamos por 5!? Sim, percebi o erro de > digitação, mas isso não é o principal. > > Em 10 de dezembro de 2015 17:23, Gabriel Tostes > escreveu: > >> A respostas 45360 está correta... Numere as cadeiras de 1 a 15 e dÃvida >> em 3 em casos: >> 1-> 15 ocupada >> 2-> 1 ocupada (análogo ao 1º) >> 3-> 1 e 15 vazias. >> >> No primeiro caso temos que 1 e 14 devem estar vazias, logo, temos 4 >> pessoas para distribuir nas 12 cadeiras restantes... >> Como cada pessoa deve ocupar uma dessas cadeiras restam 8 vazias pra >> distribuir entre as pessoas, mas entre duas pessoas deve ter ao menos >> cadeira vazia, então -> 9!/5!x4!=136 >> No terceiro caso temos 13 cadeiras pra colocar 5 pessoas, logo 8 vazias, >> mas entre duas pessoas devemos ter uma cadeira vazia pelo menos uma vazia >> -> 9!/4!x5!=136 >> Total-> (2x136+136)x5!=45360 >> >> On Dec 10, 2015, at 16:45, Vanderlei Nemitz >> wrote: >> >> Pessoal, gostaria de uma ajuda com essa questão. Vi em um site a >> resposta 45360, mas não concordo. Encontrei um valor bem menor. Obrigado! >> >> Vanderlei >> >> *Cinco pessoas devem se sentar em 15 cadeiras colocadas em torno de uma >> mesa circular. De quantos modos isso pode ser feito se não deve haver >> ocupação simultânea de duas cadeiras adjacentes? * >> >> -- >> Esta mensagem foi verificada pelo sistema de antivÃrus e >> acredita-se estar livre de perigo. >> >> >> -- >> Esta mensagem foi verificada pelo sistema de antivÃrus e >> acredita-se estar livre de perigo. >> > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Análise Combinatória
K! Esse é o tipo de questão indigna, para o ENEM. Contexto inadequado! Kkkk. Abs Nehab Em 11/08/2015 10:22, Pedro Costa npc1...@gmail.com escreveu: Uma aranha tem uma meia e um sapato paracada um de seus oito pés. De quantas maneiras diferentes a aranha pode se calçar admitindo que a meia tem que ser colocada antes do sapato? -- [image: Avast logo] https://www.avast.com/antivirus Este email foi escaneado pelo Avast antivírus. www.avast.com https://www.avast.com/antivirus -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Análise Combinatória
Boa tarde! Fez-se a restrição de que a meia deva ser calçada antes do sapato, o que é esperado, porém não se fez a restrição de que os sapatos e meias e são diferentes. Use o princípio da multiplicação. Para o primeiro pé 8 escolhas para meia e 8 para sapato para o segundo 7 escolhas para meia e 7 para sapato 8*8*7*7*1*1 = (8!)^2 Saudações, PJMS. Em 11 de agosto de 2015 10:16, Pedro Costa npc1...@gmail.com escreveu: Uma aranha tem uma meia e um sapato paracada um de seus oito pés. De quantas maneiras diferentes a aranha pode se calçar admitindo que a meia tem que ser colocada antes do sapato? -- [image: Avast logo] https://www.avast.com/antivirus Este email foi escaneado pelo Avast antivírus. www.avast.com https://www.avast.com/antivirus -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Análise combinatória
Muito obrigado a todos, excelentes respostas! Artur Costa Steiner Em 12/07/2013, às 09:34, Marcos Martinelli mffmartine...@gmail.com escreveu: Blza. Entendi agora. Obrigado. Em 12 de julho de 2013 09:29, Rogerio Ponce abrlw...@gmail.com escreveu: Ola' Marcos, eu escrevi errado. Como os blocos representam 4 elementos, que ocupam 7 casas, e' como se houvesse 93 casas livres e 4 ocupadas, com um total de 100-(2+2+2+1)+4=97 casas. Ou seja, existem binom(97,4) formas de distribuirmos os 4 blocos dentro de [1,100]. []'s Rogerio Ponce 2013/7/12 Marcos Martinelli mffmartine...@gmail.com Só não entendi essa parte: 100-(2+2+2+1)=97. Em 12 de julho de 2013 09:08, Marcos Martinelli mffmartine...@gmail.com escreveu: Legal. Em 12 de julho de 2013 09:02, Rogerio Ponce abrlw...@gmail.com escreveu: Ola' Artur, como queremos que a distancia minima entre os elementos seja de pelo menos 2, podemos imaginar que devemos distribuir , dentro do segmento [0,100], 3 blocos com comprimento 2 , e um bloco com comprimento 1 (o bloco mais 'a direita). Como existem 100-(2+2+2+1)=97 vagas, o resultado vale binom(97,4)=3464840. []'s Rogerio Ponce 2013/7/11 Artur Costa Steiner steinerar...@gmail.com Não consegui achar uma forma de resolver isto sem recorrer a um computador. Com os inteiros de 1 a 100, quantos conjuntos de 4 elementos podemos formar de modo que a diferença positiva entre dois elementos do conjunto seja maior ou igual a 2? Abraços. Artur Costa Steiner -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Análise combinatória
2013/7/12 Marcos Martinelli mffmartine...@gmail.com Seja {A_n} a quantidade de seqüências com 4 números escolhidos de 1 a n tais que a diferença positiva seja maior ou igual a 2 (n=4). Seja {B_n} a quantidade de seqüências com 3 números escolhidos de 1 a n tais que a diferença positiva seja maior ou igual a 2 (n=3). Seja {C_n} a quantidade de seqüências com 2 números escolhidos de 1 a n tais que a diferença positiva seja maior ou igual a 2 (n=2). Para sabermos quanto vale A_(n+1), devemos dividir nossa contagem em duas partes: i) escolher 4 números dentre os que vão de 1 a n tais que a diferença positiva seja maior ou igual a 2. Isto pode ser feito de A_n maneiras. ii) escolher o (n+1) como um número obrigatório a constar no nosso conjunto de 4. Após isso, escolher 3 números entre os que vão de 1 a (n-1), cuja diferença positiva seja maior ou igual a 2. Isto pode ser feito de B_(n-1) maneiras. Podemos escrever: A_(n+1) = A_n + B_(n-1) (n=4). Analogamente teremos: B_(n+1) = B_n + C_(n-1) (n=3). Pensando de maneira similar, temos também: C_(n+1) = C_n + (n-1) (n=2). Temos três séries telescópicas. Resolvendo e lembrando que a soma das colunas do triângulo de Pascal é o número binomial localizado na diagonal à direita do último elemento do somatório, obteremos: C_n = binomial (n-1,2) = (n-1).(n-2)/2! B_n = binomial (n-2,3) = (n-2)(n-3)(n-4)/3! A_n = binomial (n-3,4) = (n-3)(n-4)(n-5)(n-6)/4! Interessante a solução, ela me faz pensar o seguinte: há uma bijeção entre uma escolha (x1, x2, x3, x4) em números de 1 a n com a restrição, e uma escolha (x1, x2-1, x3-2, x4-3) para números de 1 a n-3 sem a restrição. Como este último pode ser escolhido de binomial(n-3, 4) formas, então o primeiro também poderia. -- []'s Lucas -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Análise combinatória
2013/7/12 Marcos Martinelli mffmartine...@gmail.com Mas vc conseguiu mostrar que existe mesmo a bijeção? Um representante do primeiro tera um único representante no segundo e vice-versa pois só é feita uma subtração/soma. A questão é somente se as restrições são respeitadas. x2-1 x1 sse x2-x1 = 2 x3-2 x2-1 sse x3-x2 = 2 x4-3 x3-2 sse x4-x3 = 2 x4 = n sse x4-3 = n-3 x1 = 1 sse x1 = 1 -- []'s Lucas -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Análise combinatória
Só não entendi essa parte: 100-(2+2+2+1)=97. Em 12 de julho de 2013 09:08, Marcos Martinelli mffmartine...@gmail.comescreveu: Legal. Em 12 de julho de 2013 09:02, Rogerio Ponce abrlw...@gmail.com escreveu: Ola' Artur, como queremos que a distancia minima entre os elementos seja de pelo menos 2, podemos imaginar que devemos distribuir , dentro do segmento [0,100], 3 blocos com comprimento 2 , e um bloco com comprimento 1 (o bloco mais 'a direita). Como existem 100-(2+2+2+1)=97 vagas, o resultado vale binom(97,4)=3464840. []'s Rogerio Ponce 2013/7/11 Artur Costa Steiner steinerar...@gmail.com Não consegui achar uma forma de resolver isto sem recorrer a um computador. Com os inteiros de 1 a 100, quantos conjuntos de 4 elementos podemos formar de modo que a diferença positiva entre dois elementos do conjunto seja maior ou igual a 2? Abraços. Artur Costa Steiner -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Análise combinatória
Ola' Marcos, eu escrevi errado. Como os blocos representam 4 elementos, que ocupam 7 casas, e' como se houvesse 93 casas livres e 4 ocupadas, com um total de 100-(2+2+2+1)+4=97 casas. Ou seja, existem binom(97,4) formas de distribuirmos os 4 blocos dentro de [1,100]. []'s Rogerio Ponce 2013/7/12 Marcos Martinelli mffmartine...@gmail.com Só não entendi essa parte: 100-(2+2+2+1)=97. Em 12 de julho de 2013 09:08, Marcos Martinelli mffmartine...@gmail.comescreveu: Legal. Em 12 de julho de 2013 09:02, Rogerio Ponce abrlw...@gmail.comescreveu: Ola' Artur, como queremos que a distancia minima entre os elementos seja de pelo menos 2, podemos imaginar que devemos distribuir , dentro do segmento [0,100], 3 blocos com comprimento 2 , e um bloco com comprimento 1 (o bloco mais 'a direita). Como existem 100-(2+2+2+1)=97 vagas, o resultado vale binom(97,4)=3464840. []'s Rogerio Ponce 2013/7/11 Artur Costa Steiner steinerar...@gmail.com Não consegui achar uma forma de resolver isto sem recorrer a um computador. Com os inteiros de 1 a 100, quantos conjuntos de 4 elementos podemos formar de modo que a diferença positiva entre dois elementos do conjunto seja maior ou igual a 2? Abraços. Artur Costa Steiner -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Análise combinatória
2013/7/11 Artur Costa Steiner steinerar...@gmail.com Não consegui achar uma forma de resolver isto sem recorrer a um computador. Com os inteiros de 1 a 100, quantos conjuntos de 4 elementos podemos formar de modo que a diferença positiva entre dois elementos do conjunto seja maior ou igual a 2? Utilizando da seguinte identidade: sum_{0 = k = n} kCm = (n+1)C(m+1) , onde xCy é o numero de combinações de x objetos, y a y, podemos obter uma expressão para o valor procurado. Em vez de considerar as posições, consideremos a posição inicial x e as diferenças d1, d2 e d3, de modo que os números selecionados sejam x, x+d1, x+d1+d2, x+d1+d2+d3. Se fixarmos k = d1+d2+d3, de quantas formas podemos selecionar uma tripla (d1, d2, d3)? Basta fazer uma combinação completa de k-6 em 3 pedaços e então adicionar a cada um dos 3 pedaços o +2 pra respeitar a restrição de ser = 2. O número de triplas é portanto (k-6 + 2)C2. Fixado k, podemos selecionar a posição inicial de 100-k-1 formas. Assim o número total de formas é sum_{6 = k = 99} (100 - k - 1) (k-6 +2)C2. Para nos livrarmos do k no fator podemos fazer o seguinte: (99 - 3 - (k-3)) (k-4)C2 = 96 (k-4)C2 -(k-3) (k-4)C2 = 96 (k-4)C2 - 3 (k-3)C3 E assim a expressão pode ser obtida da identidade mostrada no início com algumas manipulaçõezinhas algébricas. -- []'s Lucas -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Análise combinatória
Seja {A_n} a quantidade de seqüências com 4 números escolhidos de 1 a n tais que a diferença positiva seja maior ou igual a 2 (n=4). Seja {B_n} a quantidade de seqüências com 3 números escolhidos de 1 a n tais que a diferença positiva seja maior ou igual a 2 (n=3). Seja {C_n} a quantidade de seqüências com 2 números escolhidos de 1 a n tais que a diferença positiva seja maior ou igual a 2 (n=2). Para sabermos quanto vale A_(n+1), devemos dividir nossa contagem em duas partes: i) escolher 4 números dentre os que vão de 1 a n tais que a diferença positiva seja maior ou igual a 2. Isto pode ser feito de A_n maneiras. ii) escolher o (n+1) como um número obrigatório a constar no nosso conjunto de 4. Após isso, escolher 3 números entre os que vão de 1 a (n-1), cuja diferença positiva seja maior ou igual a 2. Isto pode ser feito de B_(n-1) maneiras. Podemos escrever: A_(n+1) = A_n + B_(n-1) (n=4). Analogamente teremos: B_(n+1) = B_n + C_(n-1) (n=3). Pensando de maneira similar, temos também: C_(n+1) = C_n + (n-1) (n=2). Temos três séries telescópicas. Resolvendo e lembrando que a soma das colunas do triângulo de Pascal é o número binomial localizado na diagonal à direita do último elemento do somatório, obteremos: C_n = binomial (n-1,2) = (n-1).(n-2)/2! B_n = binomial (n-2,3) = (n-2)(n-3)(n-4)/3! A_n = binomial (n-3,4) = (n-3)(n-4)(n-5)(n-6)/4! Em quinta-feira, 11 de julho de 2013, Lucas Prado Melo escreveu: 2013/7/11 Artur Costa Steiner steinerar...@gmail.com javascript:_e({}, 'cvml', 'steinerar...@gmail.com'); Não consegui achar uma forma de resolver isto sem recorrer a um computador. Com os inteiros de 1 a 100, quantos conjuntos de 4 elementos podemos formar de modo que a diferença positiva entre dois elementos do conjunto seja maior ou igual a 2? Utilizando da seguinte identidade: sum_{0 = k = n} kCm = (n+1)C(m+1) , onde xCy é o numero de combinações de x objetos, y a y, podemos obter uma expressão para o valor procurado. Em vez de considerar as posições, consideremos a posição inicial x e as diferenças d1, d2 e d3, de modo que os números selecionados sejam x, x+d1, x+d1+d2, x+d1+d2+d3. Se fixarmos k = d1+d2+d3, de quantas formas podemos selecionar uma tripla (d1, d2, d3)? Basta fazer uma combinação completa de k-6 em 3 pedaços e então adicionar a cada um dos 3 pedaços o +2 pra respeitar a restrição de ser = 2. O número de triplas é portanto (k-6 + 2)C2. Fixado k, podemos selecionar a posição inicial de 100-k-1 formas. Assim o número total de formas é sum_{6 = k = 99} (100 - k - 1) (k-6 +2)C2. Para nos livrarmos do k no fator podemos fazer o seguinte: (99 - 3 - (k-3)) (k-4)C2 = 96 (k-4)C2 -(k-3) (k-4)C2 = 96 (k-4)C2 - 3 (k-3)C3 E assim a expressão pode ser obtida da identidade mostrada no início com algumas manipulaçõezinhas algébricas. -- []'s Lucas -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] RE: [obm-l] Re: [obm-l] Análise Combinatória
Onde estou errando?n(intersecção de dois) = ?AA e BB por exemplo.Escolho 4 posições (para essas 4 letras) entre 10 possíveis:C10,4 = 210Para cada uma delas vale AABB ou BBAADepois faço 6!/2^3Dai encontro 210.2.6!/2^3 8!/2^3 Date: Sun, 24 Feb 2013 17:35:56 -0800 From: cysh...@yahoo.com Subject: [obm-l] Re: [obm-l] Análise Combinatória To: obm-l@mat.puc-rio.br Inclusão-exclusão. Sendo A, B, C, D, E os conjuntos dos anagramas com As, Bs, Cs, Ds, Es seguidos, temos que calcular 10!/2^5 - n(A U B U C U D U E). Mas n(A) = n(B) = ... = n(E) = 9!/2^4, n(interseção de dois) = 8!/2^3, n(interseção de três) = 7!/2^2, n(interseção de quatro) = 6!/2 e n(interseção dos cinco) = 5!. Aí o total é 10!/2^5 - 5.9!/2^4 + 10.8!/2^3 - 10.7!/2^2 + 5.6!/2 - 5!, e aí é fazer a conta. Não acho que haja uma fórmula bonitinha no caso geral, como é de praxe nos problemas de inclusão-exclusão. []'s Shine From: Artur Costa Steiner steinerar...@gmail.com To: obm-l@mat.puc-rio.br obm-l@mat.puc-rio.br Sent: Sunday, February 24, 2013 8:31 PM Subject: Re: [obm-l] Análise Combinatória Acho que podemos raciocinar assim: Para a 1a posição, a partir da esquerda, temos 5 opções de letra. Escolhida uma, restam 4 possibilidades para a segunda posição. E assim, até a 10a posição. Se não cometi nenhum engano, vai haver 5 x 4^9 modos atendendo ao desejado. Abraços Artur Costa Steiner Em 24/02/2013, às 19:27, Anderson Weber anderswe...@bol.com.br escreveu: Boa noite, amigos. Tem-se 10 letras: AA BB CC DD EE. De quantos modos podemos permutá-las, tal que não haja duas letras consecutivas iguais? Um abraço. Anderson = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Análise Combinatória
Desculpa, eu não fui muito claro na hora de fazer as contas (eu devia estar com pressa na hora que escrevi o outro e-mail). Aí vai: Para calcular a interseção de dois, ou seja, as sequências com AA e BB, trate AA e BB como blocos. Aí precisamos calcular a quantidade de anagramas com 8 símbolos (dois Cs, dois Ds, dois Es, o bloco AA e o bloco BB). Como três símbolos repetem, a quantidade é 8!/2^3. Os outros são parecidos. O que você fez, escolher 4 posições entre 10, pode fazer com que os As e/ou os Bs fiquem separados. Por exemplo, se você escolher as posições 1, 2, 4 e 6 e AABB, sua sequência fica, inicialmente, AA_B_B_,_,_,_. Os As ficaram juntos, mas os Bs não. Outro exemplo é _B_B_,_A_A_. Por isso o seu resultado é maior: você está contando sequências a mais. []'s Shine From: marcone augusto araújo borges marconeborge...@hotmail.com To: obm-l@mat.puc-rio.br Sent: Monday, February 25, 2013 11:51 AM Subject: [obm-l] RE: [obm-l] Re: [obm-l] Análise Combinatória Onde estou errando? n(intersecção de dois) = ? AA e BB por exemplo. Escolho 4 posições (para essas 4 letras) entre 10 possíveis:C10,4 = 210 Para cada uma delas vale AABB ou BBAA Depois faço 6!/2^3 Dai encontro 210.2.6!/2^3 8!/2^3 Date: Sun, 24 Feb 2013 17:35:56 -0800 From: cysh...@yahoo.com Subject: [obm-l] Re: [obm-l] Análise Combinatória To: obm-l@mat.puc-rio.br Inclusão-exclusão. Sendo A, B, C, D, E os conjuntos dos anagramas com As, Bs, Cs, Ds, Es seguidos, temos que calcular 10!/2^5 - n(A U B U C U D U E). Mas n(A) = n(B) = ... = n(E) = 9!/2^4, n(interseção de dois) = 8!/2^3, n(interseção de três) = 7!/2^2, n(interseção de quatro) = 6!/2 e n(interseção dos cinco) = 5!. Aí o total é 10!/2^5 - 5.9!/2^4 + 10.8!/2^3 - 10.7!/2^2 + 5.6!/2 - 5!, e aí é fazer a conta. Não acho que haja uma fórmula bonitinha no caso geral, como é de praxe nos problemas de inclusão-exclusão. []'s Shine From: Artur Costa Steiner steinerar...@gmail.com To: obm-l@mat.puc-rio.br obm-l@mat.puc-rio.br Sent: Sunday, February 24, 2013 8:31 PM Subject: Re: [obm-l] Análise Combinatória Acho que podemos raciocinar assim: Para a 1a posição, a partir da esquerda, temos 5 opções de letra. Escolhida uma, restam 4 possibilidades para a segunda posição. E assim, até a 10a posição. Se não cometi nenhum engano, vai haver 5 x 4^9 modos atendendo ao desejado. Abraços Artur Costa Steiner Em 24/02/2013, às 19:27, Anderson Weber anderswe...@bol.com.br escreveu: Boa noite, amigos. Tem-se 10 letras: AA BB CC DD EE. De quantos modos podemos permutá-las, tal que não haja duas letras consecutivas iguais? Um abraço. Anderson = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] Análise Combinatória
Inclusão-exclusão. Sendo A, B, C, D, E os conjuntos dos anagramas com As, Bs, Cs, Ds, Es seguidos, temos que calcular 10!/2^5 - n(A U B U C U D U E). Mas n(A) = n(B) = ... = n(E) = 9!/2^4, n(interseção de dois) = 8!/2^3, n(interseção de três) = 7!/2^2, n(interseção de quatro) = 6!/2 e n(interseção dos cinco) = 5!. Aí o total é 10!/2^5 - 5.9!/2^4 + 10.8!/2^3 - 10.7!/2^2 + 5.6!/2 - 5!, e aí é fazer a conta. Não acho que haja uma fórmula bonitinha no caso geral, como é de praxe nos problemas de inclusão-exclusão. []'s Shine From: Artur Costa Steiner steinerar...@gmail.com To: obm-l@mat.puc-rio.br obm-l@mat.puc-rio.br Sent: Sunday, February 24, 2013 8:31 PM Subject: Re: [obm-l] Análise Combinatória Acho que podemos raciocinar assim: Para a 1a posição, a partir da esquerda, temos 5 opções de letra. Escolhida uma, restam 4 possibilidades para a segunda posição. E assim, até a 10a posição. Se não cometi nenhum engano, vai haver 5 x 4^9 modos atendendo ao desejado. Abraços Artur Costa Steiner Em 24/02/2013, às 19:27, Anderson Weber anderswe...@bol.com.br escreveu: Boa noite, amigos. Tem-se 10 letras: AA BB CC DD EE. De quantos modos podemos permutá-las, tal que não haja duas letras consecutivas iguais? Um abraço. Anderson = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[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
[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] RE: [obm-l] análise combinatória, problema do elevador
Você sabe calcular a quantidade de soluções positivas de a1 + a2 + a3 + a4 +... + an = k ? Se não, aqui vai uma breve demonstração. Faça 1+1+1+1+1+1+1...+1, com k uns, temos que substituir n-1 + por vírgulas, de modo que cada vírgula delimita uma variável, ex: 1+1+1+1, 1+1, 1, temos k=7, a1 = 4 , a2=2 e a3=1 Temos C(k-1, n-1) maneiras de fazer isso No caso de soluções não negativas, Seja a1 + a2 + a3 + a4 +... + an = k , Faça ci = ai+1, temos c1 + c2 + c3 + c4 +... + cn = k +n, que tem C(k+n-1, n-1) soluções positivas -- Voltando ao problema, Como elas são indistinguiveis, o problema se dá em callcular a quantidade de pessoas que saiu por andar. Seja a a quantidade de pessoas que saiu no primeiro9 andar, b a do segundo, etc Temos a+b+c+d+e+f = 8, com a,b, c, d, e, f inteiros não negativosA quantidade de soluções é C(13, 5) = 13.12.11.10.9/5.4.3.2.1 = 1287 Se distinguissemos mulher e homem teríamos, C(10, 5) para homens e C(8, 5) para as mlheres Total = 210*56 = 11760 (se eu não errei as contas) []'sJoão Date: Mon, 2 Apr 2012 15:27:41 -0300 Subject: [obm-l] análise combinatória, problema do elevador From: claudin...@gmail.com To: obm-l@mat.puc-rio.br Prezados, alguém poderia me ajudar neste problema? Um elevador parte do andar térreo com 8 pessoas (o operador não está incluso) as quais saem do elevador através dos andares 1,2,…,6 (último andar). Se as pessoas são indistingüíveis de quantas maneiras o operador pode observar suas saídas? De quantas maneiras se entre as 8 pessoas, 3 são mulheres e 5 são homens? Desde já agradeço, -- *Claudinei Margarida de Morais* Engenheiro de Minas Pós-Graduação em sistemas Mínero-Metalúrgicos mestrando em engenharia de minas (lavra de minas) E-mail: claudin...@gmail.com Cel: (31) 9339-4977 = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] Análise Combinatória - mais um
Acho que a primeira fórmula seria C(u-w, w-1). 2011/9/12 João Maldonado joao_maldona...@hotmail.com: Olá, Queria saber como provar a que a quantidade de soluções inteiras positivas de um sistema com w variáveis da forma x1 + x2 +...+ xw = u é C(u-1, w-1) E que a quantidade de soluções inteiras não negativas é C(w+u-1, w-1) []'s João -- Henrique = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] Análise Combinatória - mais um
Ops, na verdade seria o que você colocou mesmo. 2011/9/13 Henrique Rennó henrique.re...@gmail.com: Acho que a primeira fórmula seria C(u-w, w-1). 2011/9/12 João Maldonado joao_maldona...@hotmail.com: Olá, Queria saber como provar a que a quantidade de soluções inteiras positivas de um sistema com w variáveis da forma x1 + x2 +...+ xw = u é C(u-1, w-1) E que a quantidade de soluções inteiras não negativas é C(w+u-1, w-1) []'s João -- Henrique -- Henrique = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] Análise Combinatória - mais um
Seja a equação linear com coeficientes unitários x1 + x2 +...+ xw = u Escrevemos: 1 + 1 + 1 + ... + 1 = u (u parcelas iguais a 1). Cada solução inteira e positiva dessa equação corresponde a escolha de w-1 sinais mais dentre o u-1 existentes na igualdade acima. Por exemplo, a solução x1=x2=x3=...=x(w-1)=1 e xw=u-w+1 pode ser vista como: 1 *+* 1 *+* 1 *+* ... *+* 1 +1 +1... + 1 = u (onde escolhemos os primeiros w-1 sinais de mais) Ora, podemos fazer isso de C(u-1,w-1) maneiras distintas. Logo, existem C(u-1,w-1) soluções inteiras e positivas da equação. Para soluções inteiras não negativas, fazemos, para cada i variando de 1 a w yi = xi-1 Agora, a equação fica: y1 - 1 + y2 - 1 +...+ yw - 1 = u Daí, y1 + y2 + ... + yw = u+w Note que cada solução inteira positiva da equação acima corresponde uma solução não negativa da equação original. Mas já sabemos que a equação acima possui C(u+w-1, w-1) soluções inteiras positivas. Assim, a equação original possui C(u+w-1, w-1) soluções inteiras não negativas. Não sei se chega a ser uma demonstração o que escrevi, mas é uma boa maneira de ver essas fórmulas. Abraços. Hugo. Em 12 de setembro de 2011 17:11, João Maldonado joao_maldona...@hotmail.com escreveu: Olá, Queria saber como provar a que a quantidade de soluções inteiras positivas de um sistema com w variáveis da forma x1 + x2 +...+ xw = u é C(u-1, w-1) E que a quantidade de soluções inteiras não negativas é C(w+u-1, w-1) []'s João
[obm-l] RE: [obm-l] Re: [obm-l] Análise Combinatória - mais um
Valeu Hugo, Mas só pra ver se eu entendi, se fossem as soluções inteiras = -1, seria C(u+ 2w-1, w-1)? []'sJoão Date: Tue, 13 Sep 2011 15:55:09 -0300 Subject: [obm-l] Re: [obm-l] Análise Combinatória - mais um From: hfernande...@gmail.com To: obm-l@mat.puc-rio.br Seja a equação linear com coeficientes unitários x1 + x2 +...+ xw = u Escrevemos: 1 + 1 + 1 + ... + 1 = u (u parcelas iguais a 1). Cada solução inteira e positiva dessa equação corresponde a escolha de w-1 sinais mais dentre o u-1 existentes na igualdade acima. Por exemplo, a solução x1=x2=x3=...=x(w-1)=1 e xw=u-w+1 pode ser vista como: 1 + 1 + 1 + ... + 1 +1 +1... + 1 = u (onde escolhemos os primeiros w-1 sinais de mais) Ora, podemos fazer isso de C(u-1,w-1) maneiras distintas. Logo, existem C(u-1,w-1) soluções inteiras e positivas da equação. Para soluções inteiras não negativas, fazemos, para cada i variando de 1 a w yi = xi-1 Agora, a equação fica: y1 - 1 + y2 - 1 +...+ yw - 1 = uDaí, y1 + y2 + ... + yw = u+w Note que cada solução inteira positiva da equação acima corresponde uma solução não negativa da equação original. Mas já sabemos que a equação acima possui C(u+w-1, w-1) soluções inteiras positivas. Assim, a equação original possui C(u+w-1, w-1) soluções inteiras não negativas. Não sei se chega a ser uma demonstração o que escrevi, mas é uma boa maneira de ver essas fórmulas. Abraços. Hugo. Em 12 de setembro de 2011 17:11, João Maldonado joao_maldona...@hotmail.com escreveu: Olá, Queria saber como provar a que a quantidade de soluções inteiras positivas de um sistema com w variáveis da formax1 + x2 +...+ xw = ué C(u-1, w-1) E que a quantidade de soluções inteiras não negativas é C(w+u-1, w-1) []'sJoão
[obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Análise Combinatória - mais um
Isso mesmo. Nesse caso, você aplicaria mudança de variáveis: yi = xi-2 Em geral, para soluções inteiras maiores ou iguais a p, você deve aplicar a mudança de variável yi=xi+p-1 Abraços. Hugo Em 13 de setembro de 2011 19:55, João Maldonado joao_maldona...@hotmail.com escreveu: Valeu Hugo, Mas só pra ver se eu entendi, se fossem as soluções inteiras = -1, seria C(u+ 2w-1, w-1)? []'s João -- Date: Tue, 13 Sep 2011 15:55:09 -0300 Subject: [obm-l] Re: [obm-l] Análise Combinatória - mais um From: hfernande...@gmail.com To: obm-l@mat.puc-rio.br Seja a equação linear com coeficientes unitários x1 + x2 +...+ xw = u Escrevemos: 1 + 1 + 1 + ... + 1 = u (u parcelas iguais a 1). Cada solução inteira e positiva dessa equação corresponde a escolha de w-1 sinais mais dentre o u-1 existentes na igualdade acima. Por exemplo, a solução x1=x2=x3=...=x(w-1)=1 e xw=u-w+1 pode ser vista como: 1 *+* 1 *+* 1 *+* ... *+* 1 +1 +1... + 1 = u (onde escolhemos os primeiros w-1 sinais de mais) Ora, podemos fazer isso de C(u-1,w-1) maneiras distintas. Logo, existem C(u-1,w-1) soluções inteiras e positivas da equação. Para soluções inteiras não negativas, fazemos, para cada i variando de 1 a w yi = xi-1 Agora, a equação fica: y1 - 1 + y2 - 1 +...+ yw - 1 = u Daí, y1 + y2 + ... + yw = u+w Note que cada solução inteira positiva da equação acima corresponde uma solução não negativa da equação original. Mas já sabemos que a equação acima possui C(u+w-1, w-1) soluções inteiras positivas. Assim, a equação original possui C(u+w-1, w-1) soluções inteiras não negativas. Não sei se chega a ser uma demonstração o que escrevi, mas é uma boa maneira de ver essas fórmulas. Abraços. Hugo. Em 12 de setembro de 2011 17:11, João Maldonado joao_maldona...@hotmail.com escreveu: Olá, Queria saber como provar a que a quantidade de soluções inteiras positivas de um sistema com w variáveis da forma x1 + x2 +...+ xw = u é C(u-1, w-1) E que a quantidade de soluções inteiras não negativas é C(w+u-1, w-1) []'s João
[obm-l] Re: [obm-l] ANÁLISE COMBINATÓRIA
Bem, para o 2, dou uma dica: divida o intervalo [0,1] em n partes, e pense onde cairiam as partes fracionárias dos Kx. Em 27/07/11, Marcelo Costamat.mo...@gmail.com escreveu: *1 - Prove que dado qualquer conjunto de dez inteiros positivos de dois dígitos cada, é possível obter dois subconjuntos disjuntos cujos elementos têm a mesma soma. 2 - Sejam x um número real e n um inteiro positivo. Mostre que entre os números x, 2x, 3x, . . ., (n – 1)x, existe um cuja distância a algum inteiro é, no máximo, 1/n. AGRADEÇO DESDE JÁ VOSSA ATENÇÃO * -- /**/ 神が祝福 Torres = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] RE: [obm-l] Análise Combinatória e Probabilidade
Sobre a questao 1,acho que tenho uma ideia razoavel,mas pensando apenas em inteiros POSITIVOS. Na divisao de um inteiro positivo por 100 ha 100 restos possiveis(0,1,2...,98,99) Se vc subtrai dois numeros com restos iguais, o resultado tem resto zero e é divisivel por 100, e a questao esta resolvida Entao suponha 52 numeros que deixam restos diferentes quando divididos por 100 Acontece que se vc pega numeros que deixam restos com soma 100(43 e 57,por exemplo),a soma deses numeros dá um multiplo de 100,ai acaba.Caso contrario, veja que o o resto 1 exclui o resto 99,o resto 2 exclui o resto 98...e cada um dos restos possiveis exclui um unico resto e dois restos distintos excluem restos distintos Dai,para escolher 52 restos diferentes vc tem que eliminar outros 52,o que é impossivel,ja que so ha 100 restos possiveis. Se alguem puder esclarecer melhor,agradeço muito Abraços. From: mat.mo...@gmail.com Date: Thu, 21 Jul 2011 20:51:24 -0300 Subject: [obm-l] Análise Combinatória e Probabilidade To: obm-l@mat.puc-rio.br 1) Prove que em qualquer conjunto de 52 inteiros existe um par de inteiros cuja soma ou diferença é divisível por 100. 2) Prove que dado qualquer conjunto de dez inteiros positivos de dois dígitos cada, é possível obter dois subconjuntos disjuntos cujos elementos têm a mesma soma. 3) Sejam x um número real e n um inteiro positivo. Mostre que entre os números x, 2x, 3x, . . ., (n – 1)x, existe um cuja distância a algum inteiro é, no máximo, 1/n. 4) Tem-se n urnas. Bolas são colocadas ao acaso nas urnas, uma de cada vez, até que alguma urna receba duas bolas. Qual é a probabilidade de colocarmos exatamente p bolas nas urnas?
[obm-l] RE: [obm-l] RE: [obm-l] Análise Combinatória e Probabilidade
Na verdade vale para qualquer número E Z Um número pode ser da forma 100k, 100k+-1, 100k+-2, ...100k+-48, 100 k+-49, 100k+50podemos escolher somente 1 número de cada forma 100k +- n, senão a soma é divisível por 100. temos 51 maneiras de fazer isso, por isso tempos que com 52 números pelo menos 1 vai ter soma ou subtração divisível por 100. Já para a questão 4 A primeira urna não importa. Para p=2, temos 1.(1/n)Para p = 3, temos 1. (n-1)/n.2/nPara p = 4, temos 1.(n-1)/n.(n-2)/n.3/nPara p = p, temos 1.(n-1)/n(n-2)/n...(n-p+2)/n.p/n = [(n-1)!/ (n-p+1)!] (p-1)/n^ (p-1) From: marconeborge...@hotmail.com To: obm-l@mat.puc-rio.br Subject: [obm-l] RE: [obm-l] Análise Combinatória e Probabilidade Date: Sat, 23 Jul 2011 18:21:06 + Sobre a questao 1,acho que tenho uma ideia razoavel,mas pensando apenas em inteiros POSITIVOS. Na divisao de um inteiro positivo por 100 ha 100 restos possiveis(0,1,2...,98,99) Se vc subtrai dois numeros com restos iguais, o resultado tem resto zero e é divisivel por 100, e a questao esta resolvida Entao suponha 52 numeros que deixam restos diferentes quando divididos por 100 Acontece que se vc pega numeros que deixam restos com soma 100(43 e 57,por exemplo),a soma deses numeros dá um multiplo de 100,ai acaba.Caso contrario, veja que o o resto 1 exclui o resto 99,o resto 2 exclui o resto 98...e cada um dos restos possiveis exclui um unico resto e dois restos distintos excluem restos distintos Dai,para escolher 52 restos diferentes vc tem que eliminar outros 52,o que é impossivel,ja que so ha 100 restos possiveis. Se alguem puder esclarecer melhor,agradeço muito Abraços. From: mat.mo...@gmail.com Date: Thu, 21 Jul 2011 20:51:24 -0300 Subject: [obm-l] Análise Combinatória e Probabilidade To: obm-l@mat.puc-rio.br 1) Prove que em qualquer conjunto de 52 inteiros existe um par de inteiros cuja soma ou diferença é divisível por 100. 2) Prove que dado qualquer conjunto de dez inteiros positivos de dois dígitos cada, é possível obter dois subconjuntos disjuntos cujos elementos têm a mesma soma. 3) Sejam x um número real e n um inteiro positivo. Mostre que entre os números x, 2x, 3x, . . ., (n – 1)x, existe um cuja distância a algum inteiro é, no máximo, 1/n. 4) Tem-se n urnas. Bolas são colocadas ao acaso nas urnas, uma de cada vez, até que alguma urna receba duas bolas. Qual é a probabilidade de colocarmos exatamente p bolas nas urnas?
[obm-l] Re: [obm-l] ANÁLISE COMBINATÓRIA!
*Um exame consta de 4 provas. Os graus em cada matéria variam de 0 a 10, aproximados até décimos. Qual o número mínimo de candidatos que nos permitirá afirmar a existência de dois que tenham obtido notas idênticas? * É uma aplicação do chamado Princípio da Casa de Pombos. Existem 101 graus possíveis (incluindo o grau 0) em cada prova. Logo, existem 101^4 graus possíveis nas quatro provas combinadas. Assim, o número pedido é 101^4+1. *Quantos milhares sem algarismos repetidos podem ser formados com 2 algarismos pares e 2 ímpares significativos?* Escolher dois algarismos pares significativos distintos: C(4,2) Escolher dois algarismos ímpares significativos distintos: C(5,2) Formas de escolher os quatro algarimos: C(4,2)*C(5,2) Para cada escolha anterior, há 4! formas de montar o milhar (permutações). Então, a resposta será: 4! * C(4,2) * C(5,2). Depois faço os outros. Abraços. Hugo. 2009/6/29 Jorge Luis Rodrigues e Silva Luis jorgelrs1...@hotmail.com Olá, Pessoal! Um exame consta de 4 provas. Os graus em cada matéria variam de 0 a 10, aproximados até décimos. Qual o número mínimo de candidatos que nos permitirá afirmar a existência de dois que tenham obtido notas idênticas? Quantos milhares sem algarismos repetidos podem ser formados com 2 algarismos pares e 2 ímpares significativos? Em quantas permutações dos algarismos 1, 2, 3, 4, 5 e 6 os equidistantes dos extremos somam 7? Quantos diferentes colares usando 13 pedras distintas podem ser feitos se virar o colar ao invés de rodar? Qual o número de maneiras que podemos colocar quatro bolas indistingüíveis em seis compartimentos separados? A propósito, quantos números tem todos os seus dígitos de igual paridade? Afinal! Qual o maior número de interseções de 5 circunferências? Abraços! -- Novo Internet Explorer 8: mais rápido e muito mais seguro. Baixe agora, é grátis!http://brasil.microsoft.com.br/IE8/mergulhe/?utm_source=MSN%3BHotmailutm_medium=Taglineutm_campaign=IE8
[obm-l] Re: [obm-l] Análise combinatória
ENGENHARIA é uma palavra com 10 letras, das quais os E se repete 2 vezes, o N se repete 2 vezes e o A se repete 2 vezes, assim teremos a formação de 10!/2!.2!.2! anagramas. --- Em dom, 5/10/08, Marcelo Costa [EMAIL PROTECTED] escreveu: De: Marcelo Costa [EMAIL PROTECTED] Assunto: [obm-l] Análise combinatória Para: obm-l@mat.puc-rio.br Data: Domingo, 5 de Outubro de 2008, 11:52 Alguém poderia me dar uma luz nessa? Quantos são os anagramas da palavra ENGENHARIA Novos endereços, o Yahoo! que você conhece. Crie um email novo com a sua cara @ymail.com ou @rocketmail.com. http://br.new.mail.yahoo.com/addresses
Re: [obm-l] Re: [obm-l] Análise Combinatória : dúvida...
Valeu Gustavo pela atenção! Gustavo Duarte [EMAIL PROTECTED] escreveu: Acho que está certo, eu tb resolveria assim !! - Original Message - From:clebervieira To: obm-l@mat.puc-rio.br Sent: Wednesday, April 09, 2008 9:53PM Subject: [obm-l] Análise Combinatória:dúvida... Amigos gostaria da opinião de vcs sobre a resolução que fiz doseguinte problema: Um dia pode ter uma de sete classificações: MB(muitobom), B(bom), O(ótimo), P(péssimo), S(sofrível) e T(terrivel). Os dias de umasemana são: domingo, segunda, terça, quarta,quinta, sexta e sábado. Duassemanas se dizem distintas se dois dias de mesmo nome têm classificaçõesdistintas. Quantas semanas distintas, segundo o critério dado,existem? a) 7!b) 7^2c)7*7!d) 7^7e) (7^7)! Minharesolução foi a seguinte: segunda = 7 possib. terça = 7 possib. quarta =7 possib. quinta=7 possib. sexta = 7 possib. sábado = 7 possib. domingo =7 possib. Como cadaclassificação de um dia da semana é independente dos outros dias e como cadadia da semana tem 7 possibilidades, teremos 7^7 semanas distintas. Desde jáagradeço. - Abra sua conta no Yahoo!Mail, o único sem limite de espaço para armazenamento! - Abra sua conta no Yahoo! Mail, o único sem limite de espaço para armazenamento!
[obm-l] Re: [obm-l] Análise Combinatória: dúvida...
Acho que está certo, eu tb resolveria assim !! - Original Message - From: cleber vieira To: obm-l@mat.puc-rio.br Sent: Wednesday, April 09, 2008 9:53 PM Subject: [obm-l] Análise Combinatória: dúvida... Amigos gostaria da opinião de vcs sobre a resolução que fiz do seguinte problema: Um dia pode ter uma de sete classificações: MB(muito bom), B(bom), O(ótimo), P(péssimo), S(sofrível) e T(terrivel). Os dias de uma semana são: domingo, segunda, terça, quarta,quinta, sexta e sábado. Duas semanas se dizem distintas se dois dias de mesmo nome têm classificações distintas. Quantas semanas distintas, segundo o critério dado, existem? a) 7!b) 7^2c) 7*7!d) 7^7e) (7^7)! Minha resolução foi a seguinte: segunda = 7 possib. terça = 7 possib. quarta =7 possib. quinta =7 possib. sexta = 7 possib. sábado = 7 possib. domingo =7 possib. Como cada classificação de um dia da semana é independente dos outros dias e como cada dia da semana tem 7 possibilidades, teremos 7^7 semanas distintas. Desde já agradeço. -- Abra sua conta no Yahoo! Mail, o único sem limite de espaço para armazenamento!
[obm-l] Re: [obm-l] Análise combinatória
com 1 porta aberta temos 5 opções com 2 portas..C5,2 =10 opç com 3 portas ..C5,3 = 10 opç com 4 portas...C5,4 = 5 opç com todas as portas abertas1 opção.logo são 31 opções. Cx,y é combinação de x elementos agrupados y a y ou que é melhor, o número binomial x,y. Em tempo : leia sobre propriedades do triângulo de pascal , que temos 2^5 -1 = 31. Espero ter ajudado !! - Original Message - From: Bruna Carvalho To: obm-l@mat.puc-rio.br Sent: Friday, March 16, 2007 8:57 PM Subject: [obm-l] Análise combinatória Uma sala possui 5 portas. De quantos modos podemos deixar essa sala aberta? -- Bjos, Bruna
[obm-l] Re: [obm-l] Análise combinatória
Olá, cada porta pode estar aberta ou fechada.. entao temos 2^5 = 32 possibilidades.. em 1 delas, todas estao fechadas... logo, existem 31 maneiras de deixar a sala aberta.. abraços, Salhab - Original Message - From: Bruna Carvalho To: obm-l@mat.puc-rio.br Sent: Friday, March 16, 2007 8:57 PM Subject: [obm-l] Análise combinatória Uma sala possui 5 portas. De quantos modos podemos deixar essa sala aberta? -- Bjos, Bruna
[obm-l] RE: [obm-l] Análise combinatória!
Ola Vanderlei e demais colegas desta lista ... OBM-L, ( Escreverei sem acentos ) Vou apenas evidenciar o padrao que voce procura. Os detalhes voce completa. Para facilitar a compreensao, vamos nos fixar num campeonado de turno único com 10 equipes, a saber : A, B, C, ..., J. Os calculos, entretanto, serao feitos supondo um numero generico e par de equipes, 2N. Alem disso, declaro que usarei a notacao BINOM(N,P) para representar o numero de combinacoes de P elementos que se pode fazer usando um conjunto com N elementos. Seja Ri a i-esima rodada. Voce calculou corretamente o valor de R1. Agora, para prosseguir, perguntamos : de quantas maneiras podemos montar a primeira partida da segunda rodada ? Claramente : BINOM(2N,2) N, pois de BINOM(2N,2) precisamos retirar as N partidas já realizadas na primeira rodada. De quantas maneiras podemos montar a segunda partida da segunda rodada ? Bom, podemos pensar assim : retiramos de 2N as duas equipes usadas na primeira partida, o que da 2N-2 e sobre este numero calculamos BINOM(2N-2,2) N. Ocorre que ao retirarmos duas equipes de 2N estamos tambem retirando a possibilidade de ocorrer duas partidas da primeira rodada ... Exemplo : primeira rodada : (A,B),(C,D),(E,F),(G,H),(I,J) primeira partida da segunda rodada : (A,C). As combinacoes de 2 elementos sobre B,D,E,F,G,H,I,J excluem a possibilidade das partidas (A,B) e (C,D) da primeira rodada pois A,C já foram usadas na primeira partida da segunda rodada. O calculo correto, portanto, e : BINOM(2N-2,2) (N-2). Evidentemente que para a i-esima partida da segunda rodada sera : BINOM(2N-2i + 2,2) (N 2i + 2) Para 2N=10, o produtorio sera : R2=(1/5!)*[(BINOM(10,2)5)*(BINOM(8,2)3)*(BINOM(6,2)-1)*BINOM(4,2)*BINOM(2,2)] Para o calculo da primeira partida da terceira rodada basta fazer BINOM(2N,2) 2N, pois precisamos retirar N partidas da primeira rodada e N partidas da segunda rodada. Para a segunda partida da terceira rodada BINOM(2N-2,2)-2*(N-2), pois precisamso retirar (N-2) partidas da primeira rodada e (N-2) partidas da segunda rodada e assim sucessivamente. Se Pij e a i-esima partida da j-esima rodada entao podemos monta-la de : Pij= BINOM(2N-2i+2,2) (J-1)*(N-2) O numero de maneiras de montar esta rodada sera entao : Rj = (1/N!)*[ PRODUTORIO(i variando de 1 a N) Pij ] E claro que o numero de maneiras de organizar o campeonato, pelo principio multiplicativo da Analise Combinatoria, e o produto : R1*R2*...*R2n-1 E esse o padrao que voce esta procurando. E interessante perceber que voce SENTE que há um padrao, apenas não esta sabendo FALAR sobre ele ( the one that I can feel, I can express ! ) Espero ter sido util. Um Abraco a todos Paulo Santa Rita 7,2000,220406 From: [EMAIL PROTECTED] Reply-To: obm-l@mat.puc-rio.br To: obm-l@mat.puc-rio.br Subject: [obm-l] Análise combinatória! Date: Fri, 21 Apr 2006 12:50:21 + (GMT) Caros colegas, estou com um problema que penso ser difícil. Imagine, para ficar mais fácil, um campeonato brasileiro de futebol com 10 equipes por exemplo e que jogam em turno único. De quantas maneiras diferentes a tabela poderia ser montada??? Eu sei que a primeira rodada poderia ser feita de 945 maneiras diferentes, pois (C10,2.C8,2.C6,2.C4,2.C2,2)/5! = 945, onde Cn,p é o números de combinações simples de n elementos tomados p a p. A segunda rodada perderia várias destas possibilidades, pois um mesmo jogo não pode ocorrer mais de uma vez, mesmo variando todos os demais. Como são 9 rodadas, a cada rodada perderíamos várias outras possibilidades também. Não estou conseguindo observar o padrão a cada rodada. Eu dei um exemplo numérico, mas é claro que se alguém souber um resultado genéniro seria legal. Alguém tem alguma idéia??? Obrigado! Vanderlei _ Seja um dos primeiros a testar o Windows Live Messenger Beta a geração do seu MSN Messenger. http://imagine-msn.com/minisites/messenger/default.aspx?locale=pt-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 =
[obm-l] Re: [obm-l] Análise Combinatória
Oi, Carlos: Eh que o seu enunciado foi um pouco longo, o que pode ter feito com que a maioria das pessoas desistisse de le-lo ateh o fim. O baralho tem: 4 A: 4 pontos cada 4 K: 3 pontos cada 4 Q: 2 pontos cada 4 J: 1 ponto cada 36 numeros: 0 pontos cada. Voce quer saber o numero de maos de 13 cartas cuja soma eh 12 pontos. Isso eh igual ao numero de solucoes do sistema: 4*(a1+a2+a3+a4) + 3*(k1+k2+k3+k4) + 2*(q1+q2+q3+q4) + (j1+j2+j3+j4) = 12; a1+a2+a3+a4+k1+k2+k3+k4+q1+q2+q3+q4+j1+j2+j3+j4+n1+n2+ ... +n36 = 13, onde o universo das 52 variaveis eh igual a {0,1}. Isso eh igual ao coeficiente de x^12*y^13 na expansao de: (1+4x^4y+6x^8y^2+4x^12y^3)* (1+4x^3y+6x^6y^2+4x^9y^3+x^12y^4)* (1+4x^2y+6x^4y^2+4x^6y^3+x^8y^4)* (1+4xy+6x^2y^2+4x^3y^3+x^4y^4)*(1+y+y^2+y^3+y^4+y^5+y^6+y^7+y^8+y^9+y^10) Repare que x controla a soma dos pontos e y o numero de cartas. Infelizmente, eu estou de ferias no Rio de Janeiro, sem acesso a qualquer tipo de software matematico, de modo que nao vou conseguir dar a resposta numerica que voce deseja (fazer na mao nem pensar!) []s, Claudio. De: [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Cópia: Data: Mon, 5 Jul 2004 13:31:12 -0300 (ART) Assunto: Re: [obm-l] Análise Combinatória ninguém vai me ajudar Carlos Pereira [EMAIL PROTECTED] wrote: Me deparei com a questâo abaixo, e só soube respondê-la testando todas as possíveis formas de combinar os valores e somar 12 pontos ... "Não se assuste: não é preciso saber jogar bridge para entender o argumento que vamos usar. Nesse jogo, um baralho de 52 cartas é dividido, ao acaso, entre 4 jogadores, cada um recebendo uma "mão" de 13 cartas. Há um esquema de contar pontos para as cartas que é o seguinte: um Ás vale 4 pontos, um Rei vale 3 pontos, uma Dama vale 2 pontos e um Valete vale 1 pontos. As demais cartas valem zero pontos. Digamos que José recebeu a mão de cima (sortudo!), que vale 37 pontos, e João recebeu a mão de baixo (coitado!), que vale zero pontos. Alguém pode pensar que a mão de José é muito menos provável que a de João, mas não é. Um jogador de bridge pode não concordar, mas, ambas são igualmente prováveis! Há algo, porém, que distingue as duas: o número de pontos. A questão certa, então, não é saber a probabilidade de cada mão. Ambas são igualmente prováveis. A questão é saber qual é a probabilidade de receber uma mão com 37 pontos ou de receber uma mão de zero pontos. Agora, a coisa é diferente. Só existem 4 mãos diferentes que valem 37 pontos. Todas elas são como a mão da figura de cima, apenas trocando o naipe do valete. Já uma mão de zero pontos é qualquer mão sem nenhum ás ou carta de figura. O número de mãos possíveis com zero pontos é da ordem de 2,3 bilhões! Para fazer uma mão de zero pontos basta tirar os 4 ases e as 12 figuras de um baralho (16 cartas) e separar uma mão de 13 cartas a partir das 36 cartas restantes. O número de mãos distintas será a combinação de 36 cartas, tomadas 13 a 13: C3613 = 36! / ((36-13)! 13!) = 2.310.789.600 Para facilitar nossa conversa, vamos usar os termos microestado e macroestado, como Boltzmann fazia. Qualquer uma dessas 2,3 bilhões de mãos será um microestado do macroestado correspondente a zero pontos. Isto é, o macroestado zero pontos tem 2,3 bilhões de microestados, enquanto o macroestado 37 pontos tem apenas 4 microestados. Agora, é fácil entender porque uma mão de zero pontos é mais provável que uma mão de muitos pontos: ela tem muito mais microestados. Podemos, agora, definir a ENTROPIA de uma pontuação no bridge como sendo o número de mãos diferentes com essa pontuação. Ou, equivalentemente, essa entropia será o número de microestados em um macroestado. A entropia da mão de zero pontos (macroestado) é cerca de 2,3 bilhões (número de microestados), enquanto a entropia da mão de 37 pontos é apenas 4. Como exercício, você pode calcular a entropia de uma mão de 12 pontos. " É isso eu não consegui determinar de quantas formas eu posso ter uma mão (13 cartas) somando-se 12 pontos ? Yahoo! Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis! Yahoo! Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!
[obm-l] Re: [obm-l] Re: [obm-l] Análise Combinatória
^12+2184*x^13*y^10+2184*x^1 3*y^11+4504*x^21*y^12+1048*x^25*y^9+944*x^23*y^8+1290*x^28*y^13+1304*x^11*y^ 9+268*x^7*y^13+96*x^5*y^9+96*x^5*y^10+4*x^32*y^11+16*x^30*y^10+y^6+x^4*y^14+ 25*x^4*y^13+327*x^8*y^14+24*x^28*y^9+4*x^36*y^15+64*x^31*y^11+16*x^26*y^8+44 5*x^8*y^11+445*x^8*y^12+112*x^29*y^10+128*x^27*y^9+112*x^25*y^8+24*x^34*y^13 +16*x^35*y^14+64*x^23*y^7+16*x^33*y^12+896*x^29*y^13+51*x^4*y^9+51*x^4*y^11+ 47*x^4*y^12+51*x^4*y^10+170*x^6*y^12+148*x^6*y^13+4*x*y^11+170*x^6*y^10+170* x^6*y^11+4*x*y^8+4*x*y^9+4*x*y^10+10*x^2*y^10+10*x^2*y^11+6*x^2*y^12+4*x*y^6 +4*x*y^7+4*x^3*y^13+10*x^2*y^7+10*x^2*y^8+10*x^2*y^9+24*x^3*y^8+24*x^3*y^9+2 4*x^3*y^10+24*x^3*y^11+20*x^3*y^12+1716*x^12*y^13+1712*x^12*y^14+284*x^7*y^1 0+284*x^7*y^11+284*x^7*y^12+952*x^10*y^13+952*x^10*y^12+1286*x^28*y^12+1648* x^27*y^11+1616*x^26*y^10+580*x^30*y^13+872*x^29*y^12+344*x^31*y^13+194*x^32* y^14+3649*x^16*y^12+3649*x^16*y^13+3649*x^16*y^14+1304*x^11*y^12+1304*x^11*y ^13+2680*x^14*y^12+2680*x^14*y^13+2680*x^14*y^14+2680*x^14*y^11+664*x^9*y^12 +664*x^9*y^13+664*x^9*y^10+664*x^9*y^11+4060*x^17*y^14+4060*x^17*y^15+4060*x ^17*y^12+4060*x^17*y^13+4611*x^20*y^14+4611*x^20*y^16+4611*x^20*y^15+3176*x^ 15*y^14+4611*x^20*y^13+4370*x^18*y^12+4370*x^18*y^13+4370*x^18*y^14+4370*x^1 8*y^15+4504*x^21*y^14+4504*x^21*y^15+4504*x^21*y^16+3399*x^24*y^15+3399*x^24 *y^16+3399*x^24*y^17+96*x^5*y^11+96*x^5*y^12+3425*x^20*y^18+3413*x^16*y^16+2 161*x^16*y^17+2184*x^13*y^13+2612*x^14*y^7+2184*x^13*y^14+439*x^8*y^13+3649* x^16*y^15+1868*x^13*y^6+4346*x^18*y^16+3746*x^18*y^17+4*x^10*y^17+64*x^5*y^1 3+16*x^5*y^14+6*x^8*y^16+98*x^8*y^15+28*x^7*y^15+156*x^7*y^14+904*x^10*y^14+ 544*x^10*y^15+128*x^10*y^16+1276*x^11*y^6+824*x^10*y^5+56*x^6*y^14+4*x^6*y^1 5+268*x^9*y^15+572*x^9*y^14+4509*x^20*y^17+3972*x^17*y^16+2996*x^17*y^17+262 8*x^14*y^15+100*x^32*y^12+80*x^33*y^13+1984*x^14*y^16+1280*x^11*y^14+2056*x^ 13*y^15+2744*x^15*y^16+3160*x^15*y^15+40*x^34*y^14+188*x^32*y^13+224*x^30*y^ 11+2948*x^15*y^7+y^7+439*x^8*y^5+256*x^7*y^4+3621*x^16*y^8+1483*x^12*y^15+96 *x^33*y^14+256*x^31*y^12+664*x^9*y^6+976*x^11*y^15 Procurando o coeficiente de x^12*y^13 encontramos 1716. Boas férias! []s, Rafael - Original Message - From: claudio.buffara To: obm-l Sent: Monday, July 05, 2004 3:52 PM Subject: [obm-l] Re: [obm-l] Análise Combinatória Oi, Carlos: Eh que o seu enunciado foi um pouco longo, o que pode ter feito com que a maioria das pessoas desistisse de le-lo ateh o fim. O baralho tem: 4 A: 4 pontos cada 4 K: 3 pontos cada 4 Q: 2 pontos cada 4 J: 1 ponto cada 36 numeros: 0 pontos cada. Voce quer saber o numero de maos de 13 cartas cuja soma eh 12 pontos. Isso eh igual ao numero de solucoes do sistema: 4*(a1+a2+a3+a4) + 3*(k1+k2+k3+k4) + 2*(q1+q2+q3+q4) + (j1+j2+j3+j4) = 12; a1+a2+a3+a4+k1+k2+k3+k4+q1+q2+q3+q4+j1+j2+j3+j4+n1+n2+ ... +n36 = 13, onde o universo das 52 variaveis eh igual a {0,1}. Isso eh igual ao coeficiente de x^12*y^13 na expansao de: (1+4x^4y+6x^8y^2+4x^12y^3)* (1+4x^3y+6x^6y^2+4x^9y^3+x^12y^4)* (1+4x^2y+6x^4y^2+4x^6y^3+x^8y^4)* (1+4xy+6x^2y^2+4x^3y^3+x^4y^4)*(1+y+y^2+y^3+y^4+y^5+y^6+y^7+y^8+y^9+y^10) Repare que x controla a soma dos pontos e y o numero de cartas. Infelizmente, eu estou de ferias no Rio de Janeiro, sem acesso a qualquer tipo de software matematico, de modo que nao vou conseguir dar a resposta numerica que voce deseja (fazer na mao nem pensar!) []s, Claudio. = 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 =
[obm-l] Re: [obm-l] análise combinatória
Sejam x, y, z, t as quatro pessoas em questão, teremos: x + y + z + t = 20 Para contar o número de soluções dessa equação, tais sendo inteiras e positivas, faz-se: 23!/(3!20!) = 1771 maneiras diferentes .. Curiosidade: algum país deste mundo (ou de outro) usa notas de R$ 333,33. Dá inveja de tanta criatividade... Abraços, Rafael de A. Sampaio - Original Message - From: seanjr [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, March 27, 2004 5:59 PM Subject: [obm-l] análise combinatória De qts maneiras diferentes é possível distribuir 20 notas de R$333,33 para 4 pessoas? = 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 =
[obm-l] Re: [obm-l] análise combinatória
Obrigado. Vc é meu chará e R$ é a moeda imaginária, rafaéis, de uma nação insular na costa de Passárgada. Lar do Coelhinho da páscoa. =P --- Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.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 =
[obm-l] Re: [obm-l] Re: [obm-l] análise combinatória
Contar o número de soluções da equação x + y + z + t = 20, tais sendo inteiras e *não-negativas*, como muito bem me lembrou o Prof. Morgado, equivale ao número de combinações completas de 4 elementos escolhidos 20 a 20, sendo que tais elementos (pessoas) podem aparecer repetidamente: uma mesma pessoa pode receber mais de uma nota, ou mesmo, nenhuma. Representando as combinações completas (ou, como preferem outros, combinações com repetição) por *C(n,k), temos que: *C(n,k) = C(n+k-1,k) = (n+k-1)!/(k!(n-1)!) Assim: *C(4,20) = 23!/(20!3!) = 1771. Abraços, Rafael de A. Sampaio - Original Message - From: Douglas Drumond [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, March 27, 2004 8:53 PM Subject: Re: [obm-l] Re: [obm-l] análise combinatória Rafael escreveu: Sejam x, y, z, t as quatro pessoas em questão, teremos x + y + z + t = 20 Para contar o número de soluções dessa equação, tais sendo inteiras e positivas, faz-se: 23!/(3!20!) = 1771 maneiras diferentes Por que? Nao consegui entender o porque de 23!/(3!20!) = 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 =
[obm-l] Re: [obm-l] Re: [obm-l] análise combinatória
Ahhh, agora faz sentido lar do Coelhinho da Páscoa, claro...! Ainda assim, duas pequenas correções sobre o que você escreveu: - Chará escreve-se com 'x', portanto, você, provavelmente, é meu *xará*; - Passárgada escreve-se com apenas um 's', veja: Pasárgada. Sim, não é só de Matemática que gosto na vida, felizmente... ;-) Abraços, Rafael de A. Sampaio - Original Message - From: seanjr [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, March 27, 2004 10:50 PM Subject: [obm-l] Re: [obm-l] análise combinatória Obrigado. Vc é meu chará e R$ é a moeda imaginária, rafaéis, de uma nação insular na costa de Passárgada. Lar do Coelhinho da páscoa. =P = 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 =
[obm-l] Re:[obm-l] análise combinatória
Olá pessoal, Vejam a questão: (SANTA CASA- SP) Existem 4 estradas de rodagem e 3 estradas de ferro e ntre as cidades A e B. Quantos são os diferentes percursos para fazer as viagens de ida e volta entre A e B, utilizando rodovia e trem, obr igatoriamente, em qualquer ordem? Resp: 24 Creio que o Principio fundamental da contagem cai bem neste problema. maneiras para ir de A para B de trem 9ferrovia): 4 maneiras para ir de A para B de carro( rodagem)trem : 3 Como é ida e volta - temos : (4.3) . 2= 24. um abraço. Amurpe. bs: Eu usei combinação e cheguei a um resultado muito al to. Sera que não precisava ter usado combinação simples? __ E-mail Premium BOL Antivírus, anti-spam e até 100 MB de espaço. Assine já! http://email.bol.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 é [EMAIL PROTECTED] =
[obm-l] Re:[obm-l] análise combinatória
Olá pessoal, Vejam a questão: (SANTA CASA- SP) Existem 4 estradas de rodagem e 3 estradas de ferro en tre as cidades A e B. Quantos são os diferentes percursos para fazer as viagens de ida e volta entre A e B, utilizando rodovia e trem, obri gatoriamente, em qualquer ordem? Resp: 24 Tem-se dois casos: 1)ida de rodovia e volta de ferrovia 2)ida de ferrovia e volta de rodovia 1) 4 rodovias para ida multiplicado por 3 ferrovias de volta= 4x3=12 2) 3 ferrovias de ida multiplicado por 4 rodovias de volta= 3x4=12 somando: 12+12=24 __ E-mail Premium BOL Antivírus, anti-spam e até 100 MB de espaço. Assine já! http://email.bol.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 é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] análise combinatória
Um códogo é determinado pela escolha das cores de 6 barras a primeira barra pode ser escolhida de 2 cores, a segunda pode ser escolhida de 2 cores e assim por diante até a 6a barra que pode ser escolhida de 2 cores. Como a escolha da cor de uma barra não interfere na escolha da cor das outras barras o total de códigos será o produto 2^6 = 64. Porém o enunciado descarta a possibilidade de um código conter todas asbarras brancas e todas as barras pretas portanto do total devemos descontar estas duas possibilidades e a resposta fica então 64 - 2 = 62. A "fórmula" que vc colocou na mensagem original dá o total de maneiras que vc pode escolher p objetos dentre n e nào tem nada a ver com o exercício. []'s MP - Original Message - From: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Tuesday, January 14, 2003 9:41 PM Subject: [obm-l] análise combinatória Olá pessoal, Alguém consegue resolver estre problema de análise combinatória: (U.C SALVADOR) Um código para leitura ótica é constituído por 6 barras brancas ou pretas. Nenhum código tem barras de uma só cor. Veja dois exemplos desses códigos: Obs: Vou descrever como são estes exemplos: Imagine dois retângulos, em que cada um é formado por 6 listas verticais, para facilitar a descrição vamos ordenar as listas, ou seja, a 1º (da esquerda para direita), depois 2º...6º lista. Imagine que o primeiro retangulo esta pintado assim: 2º lista e 5º lista (ambas de preto) e o restante de branco. Agora, imagine o segundo retangulo (código de barras) com a 1º, 2º e 5º lista sendo pretas e as restantes brancas. Dúvida: Por quê podem ser formados 62 (segundo meu gabarito) códigos, distintos entre si? Eu tentei aplicar cn,p=n!/(n-p)!p! mas não cheguei no resultado. Será que é arranjo?