Re: [obm-l] Analise combinatoria - quantas comissoes?
On Tue, Jul 10, 2007 at 04:28:10PM -0300, Paulo Santa Rita wrote: > Ola Carissimo Prof Nicolau edemais colegas desta lista ... OBM-L, > Em primeiro lugar me permita explicar o teor da sua critica aos > nossosleitores para que todos possam entender... > 1) ESCLARECIMENTO DA CRITICA > Considerem duas pessoas - Isaac e Vitor - e um "ano" de 3 dias. Umvetor do > tipo (DIA1,DIA2,DIA3) vai representar o "ano". Como podemocorrer os > aniversarios destas 2 pessoas ao longo deste "ano" ? Assim: > (Isaac, Vitor, 0) , (Vitor, Isaac, 0)(Isaac, 0, Vitor) , (Vitor, 0, > Isaac)(0, Isaac, Vitor) , ((0, Vitor, Isaac) > (Isaac e Vitor, 0, 0), (0, Isaac e Vitor, 0) e ( 0, 0, Isaac e Vitor) > Considerando equiprovavel as possibilidades, a probababilidade de cadauma > seria 1/9, obvio. Entretanto, considerando que as possibilidade > de(Isaac,Vitor,0) e (Vitor, Isaac,0) corresponde A MESMA SOLUCAO (1,1,0)da > equacao : > X1 + X2 + X3 = 2 > Segue que a probabilidade da solucao (1,1,0) e o dobro, isto e, e 2/9.Acho > que deixei claro a CRITICA CRITERIOSA que o Carissimo ProfNicolau faz. Até aqui tudo bem, isto é exatamente o que eu tentei dizer. > 2) COMO EU LI O PROBLEMA > As solucoes (Isaac, Vitor,0) e (Vitor,Isaac,0) sao diferente porqueeles > nasceram em dias diferentes. Mas, suponha que eles nasceram nomesmo dia. Um > poderia ter nascido antes do outro. Neste caso : > (Isaac e Vitor,0,0) e (Vitor e Isaac,0,0) seriam diferente, pois, > naprimeira 3-upla, Isaac nasceu antes do Vitor, o contrario tendoocorrido > na segunda 3-upla. Portanto, a solucao (2,0,0) tambemrepresentaria duas > possibilidades. > Portanto, eu considerei INTENCIONALMENTE irrelevante a diferenca deordem, > o que implica considerar equiprovaveis as diversas solucoes de > X1 + X2 + ... + X365 = 200 Não acho convincente esta sua leitura do problema. Não vejo como a presença ou ausência da hora de nascimento na certidão de nascimento possa afetar a resposta do problema. Para mim o problema pode ser reformulado assim: Considere um dado com N = 365 faces. Jogue o dado M = 200 vezes e tabule quantas vezes A[i] sai a resposta i. Tome m = max A[i]. Qual a probabilidade de que A[1] = m? Ou equivalentemente: Obtenha a lista A como acima. Ordene a lista A, tome seu máximo m e conte quantas vezes aparece o valor m; chamemos este número de Y. Qual a esperança da variável aleatória Y? Escrevi um programa maple para simular esta última versão do problema: jojo := proc(N,M) local i, j, roll, A, As, m, Y: roll := rand(1..N): A := array(1..N,sparse): for i to M do j := roll(): A[j] := A[j] + 1: od: As := sort(convert(A,list)): m := As[-1]: Y := 1: for j from 2 to M do if (As[-j] < m) then break: else Y := Y+1: fi: od: return(Y); end; a := array(1..25000): for i to 25000 do a[i] := jojo(365,200): od: (Aqui espere um pouco até o computador/programa rodar esta coisa 25000 vezes) pp := 0: for i to 25000 do pp := pp + q^a[i]: od: sort(pp); 41383635 332815 14 13 12 2 q + q + q + q + 5 q + q + q + 7 q + 20 q + 68 q 11109 8 7 6 5 + 159 q + 375 q + 685 q + 1092 q + 1605 q + 1788 q + 1837 q 4 3 2 + 1505 q + 1553 q + 3656 q + 10638 q (Note que temos um máximo local em Y = 5. Pelos exemplos que eu vi isto ocorre quando o máximo é 3. O máximo global em Y = 1 corresponde a um máximo mais alto.) pd := diff(pp,q): subs(q=1,pd); 81750 evalf(%/25000); 3.27000 Bom, esta é a resposta aproximada. Ou melhor, a resposta é isso dividido por 365. > 3) COMO ATENDER A EXIGENCIA DA CRITICA > Considerando que a ordem dos nascimento em um mesmo dia saoirrelevantes e > atendendo somente a diferencas de dias, como computar onumero de > possibilidades para uma particular solucao numerica ? > Vou mostrar isso atraves de um exemplo. > Considere a solucao : (5,4,3,1,1,1,0,0) de X1 + X2 + ...+ X8 = 15. Aquantas > possibilidades ela corresponde ? Facil : do total de 15pessoas escolho 5 > para colocar na primeira posicao, BI(15,5). Sobram10 pessoas, das quais > escolho 4 para colocar na segunda posicao,BI(10,4). Sobram 6 pessoas, das > quais escolho 3 para colocar naterceira posicao, BI(6,3). A seguir permuto > as tres posicoescorrespondem aos 1's. Isso da : > T=Bi(15,5) * Bi(10,4) * Bi(6,3) * 3! > Como vemos, e facil fazer a computacao. O problema ( que ja etrabalhoso ) > vai apenas ficar mais trabalhoso. Eu gosto muito depensar, mas detesto > fazer calculos. Acho que isto que você está esboçando é correto para valores menores de M e N mas para os valores dados no problema é incrivelmente trabalhoso. > 4) ESTENDENDO O PROBLEMA > Usando o mesmo contexto e considerando as solucoes de > X1 + X2 + ... + X365 = 200 > equiprovaveis ( considere nascimentos de 200 coelhos albinos ) qual > aprobabilidade que num determinado d
Re: [obm-l] Analise combinatoria - quantas comissoes?
Ola Carissimo Prof Nicolau edemais colegas desta lista ... OBM-L, Em primeiro lugar me permita explicar o teor da sua critica aos nossosleitores para que todos possam entender... 1) ESCLARECIMENTO DA CRITICA Considerem duas pessoas - Isaac e Vitor - e um "ano" de 3 dias. Umvetor do tipo (DIA1,DIA2,DIA3) vai representar o "ano". Como podemocorrer os aniversarios destas 2 pessoas ao longo deste "ano" ? Assim: (Isaac, Vitor, 0) , (Vitor, Isaac, 0)(Isaac, 0, Vitor) , (Vitor, 0, Isaac)(0, Isaac, Vitor) , ((0, Vitor, Isaac) (Isaac e Vitor, 0, 0), (0, Isaac e Vitor, 0) e ( 0, 0, Isaac e Vitor) Considerando equiprovavel as possibilidades, a probababilidade de cadauma seria 1/9, obvio. Entretanto, considerando que as possibilidade de(Isaac,Vitor,0) e (Vitor, Isaac,0) corresponde A MESMA SOLUCAO (1,1,0)da equacao : X1 + X2 + X3 = 2 Segue que a probabilidade da solucao (1,1,0) e o dobro, isto e, e 2/9.Acho que deixei claro a CRITICA CRITERIOSA que o Carissimo ProfNicolau faz. 2) COMO EU LI O PROBLEMA As solucoes (Isaac, Vitor,0) e (Vitor,Isaac,0) sao diferente porqueeles nasceram em dias diferentes. Mas, suponha que eles nasceram nomesmo dia. Um poderia ter nascido antes do outro. Neste caso : (Isaac e Vitor,0,0) e (Vitor e Isaac,0,0) seriam diferente, pois, naprimeira 3-upla, Isaac nasceu antes do Vitor, o contrario tendoocorrido na segunda 3-upla. Portanto, a solucao (2,0,0) tambemrepresentaria duas possibilidades. Portanto, eu considerei INTENCIONALMENTE irrelevante a diferenca deordem, o que implica considerar equiprovaveis as diversas solucoes de X1 + X2 + ... + X365 = 200 3) COMO ATENDER A EXIGENCIA DA CRITICA Considerando que a ordem dos nascimento em um mesmo dia saoirrelevantes e atendendo somente a diferencas de dias, como computar onumero de possibilidades para uma particular solucao numerica ? Vou mostrar isso atraves de um exemplo. Considere a solucao : (5,4,3,1,1,1,0,0) de X1 + X2 + ...+ X8 = 15. Aquantas possibilidades ela corresponde ? Facil : do total de 15pessoas escolho 5 para colocar na primeira posicao, BI(15,5). Sobram10 pessoas, das quais escolho 4 para colocar na segunda posicao,BI(10,4). Sobram 6 pessoas, das quais escolho 3 para colocar naterceira posicao, BI(6,3). A seguir permuto as tres posicoescorrespondem aos 1's. Isso da : T=Bi(15,5) * Bi(10,4) * Bi(6,3) * 3! Como vemos, e facil fazer a computacao. O problema ( que ja etrabalhoso ) vai apenas ficar mais trabalhoso. Eu gosto muito depensar, mas detesto fazer calculos. 4) ESTENDENDO O PROBLEMA Usando o mesmo contexto e considerando as solucoes de X1 + X2 + ... + X365 = 200 equiprovaveis ( considere nascimentos de 200 coelhos albinos ) qual aprobabilidade que num determinado dia "d" NAO SEJA EXTREMO, isto e,nao seja maximo e nem seja minimo ? Um AbracaoPaulo Santa Rita3,0F1A,100707 Em 10/07/07, Nicolau C. Saldanha<[EMAIL PROTECTED]> escreveu:> Oi Paulo,>> Desculpe-me por criticar uma solução incompleta,> mas se eu bem entendi a sua solução acho que você erra> ao considerar equiprováveis as várias soluções de X1 + ... + X365 = 200.>> Para não nos perdermos, aqui vai de novo o problema original:>> > Imagine-se num grupo de 200 pessoas, e imagine que todos os anos tenham 365> > dias (isto é: ignore a existência de anos bissextos). Seja f: {dias} -> N> > tal que f(d) = número de aniversariantes no dia d. Seja d_0 o dia de seu> > aniversário. Qual é a probabilidade de que f(d_0) seja um máximo da> > função f?>> Vamos trocar os números: são duas pessoas e o "ano" tem 3 dias.> Temos as possibilidades:> (2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)> mas elas *não* são equiprováveis!> As três primeiras têm probabilidade 1/9 cada> e as três últimas probabilidade 2/9 cada.> Entendo que o "você" do problema não é membro do! grupo de pessoas.> A probabilidade de que f(d_0) seja um máximo nada mais é do que a prob> de que X1 seja máximo que é de 5/9, correspondente aos casos (2,0,0),> (1,1,0) e (1,0,1). Observe que nestes dois últimos casos f(d_0) é> um máximo empatado com outro máximo.>> Isto coincide com a sua solução?>> []s, N.>> On Mon, Jul 09, 2007 at 04:50:46PM -0300, Paulo Santa Rita wrote:> > Ola Pessoal,> >> > Tentarei fazer um esboco melhor. Os detalhes voces preenchem. Como> > estou escrevendo ao mesmo tempo que faco outras coisas, pode haver> > algum erro de calculo, corrijam por favor. Para facilitar o> > entendimento da minha solucao vou resolver previamente uma outra> > questao. Considere a equacao :> >> > X1 + X2 + X3 = 12> >> > Quantas solucoes inteiras e não-negativas tem esta equacao tais que> > para todo i=1,2,3 tenhamos Xi =< 7 ? Facil. Seja Yi= 7 – Xi, i=1,2,3.> > Segue que Xi = 7 – Yi. Daqui :> >> > (7-Y1) + (7-Y2) + ( 7-Y3) = 12 => Y1 + Y2 + Y3 = 9> >! > E facil encontrar quantas solucoes inteiras e não negati! vas tem esta> > ultima equacao. Existe ate uma formulazinha que da o valor direto. E> > igualmente facil perceber que a toda solucao desta ultima equacao> > cor
Re: [obm-l] Analise combinatoria - quantas comissoes?
Oi Paulo, Desculpe-me por criticar uma solução incompleta, mas se eu bem entendi a sua solução acho que você erra ao considerar equiprováveis as várias soluções de X1 + ... + X365 = 200. Para não nos perdermos, aqui vai de novo o problema original: > Imagine-se num grupo de 200 pessoas, e imagine que todos os anos tenham 365 > dias (isto é: ignore a existência de anos bissextos). Seja f: {dias} -> N > tal que f(d) = número de aniversariantes no dia d. Seja d_0 o dia de seu > aniversário. Qual é a probabilidade de que f(d_0) seja um máximo da > função f? Vamos trocar os números: são duas pessoas e o "ano" tem 3 dias. Temos as possibilidades: (2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1) mas elas *não* são equiprováveis! As três primeiras têm probabilidade 1/9 cada e as três últimas probabilidade 2/9 cada. Entendo que o "você" do problema não é membro do grupo de pessoas. A probabilidade de que f(d_0) seja um máximo nada mais é do que a prob de que X1 seja máximo que é de 5/9, correspondente aos casos (2,0,0), (1,1,0) e (1,0,1). Observe que nestes dois últimos casos f(d_0) é um máximo empatado com outro máximo. Isto coincide com a sua solução? []s, N. On Mon, Jul 09, 2007 at 04:50:46PM -0300, Paulo Santa Rita wrote: > Ola Pessoal, > > Tentarei fazer um esboco melhor. Os detalhes voces preenchem. Como > estou escrevendo ao mesmo tempo que faco outras coisas, pode haver > algum erro de calculo, corrijam por favor. Para facilitar o > entendimento da minha solucao vou resolver previamente uma outra > questao. Considere a equacao : > > X1 + X2 + X3 = 12 > > Quantas solucoes inteiras e não-negativas tem esta equacao tais que > para todo i=1,2,3 tenhamos Xi =< 7 ? Facil. Seja Yi= 7 – Xi, i=1,2,3. > Segue que Xi = 7 – Yi. Daqui : > > (7-Y1) + (7-Y2) + ( 7-Y3) = 12 => Y1 + Y2 + Y3 = 9 > > E facil encontrar quantas solucoes inteiras e não negativas tem esta > ultima equacao. Existe ate uma formulazinha que da o valor direto. E > igualmente facil perceber que a toda solucao desta ultima equacao > corresponde uma, e somente uma, solucao para a equacao original. > Assim, a questao original esta respondida e e facilmente generalizavel > para um numero arbitrario de incognitas ... > > Voltando ao problema original, seja Xi o numero de pessoas que fazem > aniversario no dia i, i podendo variar no intervalo 1 =< i =< 365. > Assim, qualquer configuracao possivel pode ser imaginada como uma > solucao inteira não-negativa da equacao : > > X1 + X2 + ... + X365 = 200 > > Queremos saber em quantas destas solucoes o valor de Xi e maximo. Seja > Xi um valor arbitrario A tal que 1 =< a =< 200. Entao : > > Xi = A => X1 + X2 + ... + A + ... + X365 = 200 > X1 + X2 + ... + Xi-1 + Xi+1 + ... + X365 = 200 – A > > Procuramos as solucoes inteiras e não negativas desta ultima equacao > para as quais tenhamos Xk =< A, coisa que já aprendemos a fazer la em > cima. Fazendo "A" variar de 1 ate 200 e somando tudo chegamos ao total > de solucoes nas quais no dia "i" ocorreu um maximo. Seja T este total. > Agora, achamos o total de solucoes inteiras e não-negativas da equacao > : > > X1 + X2 + ... + X365 = 200 > > Seja V o total de solucoes. A probabilidade procurada e T/V. > > FIM DO PRIMEIRO ESBOCO > > > > > Para que o problema fique consistente, vou supor que apenas 7 homens e > 4 mulheres são simultameamente fluentes em frances e Phd em > Matematica. O total de comissoes possivel e, obviamente : > > T = BINOM(53,10) * BINOM(47,10) > > 1) NO MAXIMO 7 PESSOAS SAO FLUENTES EM FRANCES > > Deste total vou retirar todas as comissoes nas quais no maximo 7 > pessoas são fluentes em frances. Para ver como e possivel fazer isso, > considere o par (H,M) onde H+M = 7, H e o total de homens e M o total > de mulheres fluentes em frances : > > (H1,M1)=(7,0)=>U1= BINOM(28,3)*BINOM(25,7)*BINOM(43,10) > (H1,M1)=(6,1)=>U2=BINOM(28,4)*BINOM(25,6)*BINOM(43,9)*BINOM(4,1) > ... > (H1,M1)=(3,4)=>U5= ... ( complete aqui) > > Agora consideramos o caso em que H+M = 6. Seguira um montao de > calculos. Depois consideramos o caso em que H+M=5 e assim > sucessicamente. No final calculamos o somatorio de todos os Ui > > 2) NO MAXIMO 10 PESSOAS SAO PHD EM MATEMATICA > > (H2,M2)=(10,0) => V1=BINOM(37,10)*BINOM(26,10) > (H2,M2)=(9,1)=> V2=BINOM(21,1)*BINOM(32,9)*BINOM(21,1)*BINOM(26,9) > ... (complete aqui) > > e aqui fazemos um raciocinio absolutamente semelhante ao caso acima. > No final calculamos o somatorio de todos os Vi > > A unica pergunta não obvia e a seguinte : quantas comissoes existem > tais que, simultaneamente, existam no maximo 7 pessoas fluentes em > frances e no maximo 10 pessoas com Ph"D" em Matematica ? Se existe > alguma inteligencia neste problema ela esta aqui. O resto que vimos > acima e trivial e truculento. > > Se a resposta a pergunta e "nao", entao a resposta ao nosso problema e : > > R = T – somatorio Ui - somatorio Vi > > Se a resposta for "sim", seja W o total de comiss
Re: [obm-l] Analise combinatoria - quantas comissoes?
Ola Pessoal, Tentarei fazer um esboco melhor. Os detalhes voces preenchem. Como estou escrevendo ao mesmo tempo que faco outras coisas, pode haver algum erro de calculo, corrijam por favor. Para facilitar o entendimento da minha solucao vou resolver previamente uma outra questao. Considere a equacao : X1 + X2 + X3 = 12 Quantas solucoes inteiras e não-negativas tem esta equacao tais que para todo i=1,2,3 tenhamos Xi =< 7 ? Facil. Seja Yi= 7 – Xi, i=1,2,3. Segue que Xi = 7 – Yi. Daqui : (7-Y1) + (7-Y2) + ( 7-Y3) = 12 => Y1 + Y2 + Y3 = 9 E facil encontrar quantas solucoes inteiras e não negativas tem esta ultima equacao. Existe ate uma formulazinha que da o valor direto. E igualmente facil perceber que a toda solucao desta ultima equacao corresponde uma, e somente uma, solucao para a equacao original. Assim, a questao original esta respondida e e facilmente generalizavel para um numero arbitrario de incognitas ... Voltando ao problema original, seja Xi o numero de pessoas que fazem aniversario no dia i, i podendo variar no intervalo 1 =< i =< 365. Assim, qualquer configuracao possivel pode ser imaginada como uma solucao inteira não-negativa da equacao : X1 + X2 + ... + X365 = 200 Queremos saber em quantas destas solucoes o valor de Xi e maximo. Seja Xi um valor arbitrario A tal que 1 =< a =< 200. Entao : Xi = A => X1 + X2 + ... + A + ... + X365 = 200 X1 + X2 + ... + Xi-1 + Xi+1 + ... + X365 = 200 – A Procuramos as solucoes inteiras e não negativas desta ultima equacao para as quais tenhamos Xk =< A, coisa que já aprendemos a fazer la em cima. Fazendo "A" variar de 1 ate 200 e somando tudo chegamos ao total de solucoes nas quais no dia "i" ocorreu um maximo. Seja T este total. Agora, achamos o total de solucoes inteiras e não-negativas da equacao : X1 + X2 + ... + X365 = 200 Seja V o total de solucoes. A probabilidade procurada e T/V. FIM DO PRIMEIRO ESBOCO Para que o problema fique consistente, vou supor que apenas 7 homens e 4 mulheres são simultameamente fluentes em frances e Phd em Matematica. O total de comissoes possivel e, obviamente : T = BINOM(53,10) * BINOM(47,10) 1) NO MAXIMO 7 PESSOAS SAO FLUENTES EM FRANCES Deste total vou retirar todas as comissoes nas quais no maximo 7 pessoas são fluentes em frances. Para ver como e possivel fazer isso, considere o par (H,M) onde H+M = 7, H e o total de homens e M o total de mulheres fluentes em frances : (H1,M1)=(7,0)=>U1= BINOM(28,3)*BINOM(25,7)*BINOM(43,10) (H1,M1)=(6,1)=>U2=BINOM(28,4)*BINOM(25,6)*BINOM(43,9)*BINOM(4,1) ... (H1,M1)=(3,4)=>U5= ... ( complete aqui) Agora consideramos o caso em que H+M = 6. Seguira um montao de calculos. Depois consideramos o caso em que H+M=5 e assim sucessicamente. No final calculamos o somatorio de todos os Ui 2) NO MAXIMO 10 PESSOAS SAO PHD EM MATEMATICA (H2,M2)=(10,0) => V1=BINOM(37,10)*BINOM(26,10) (H2,M2)=(9,1)=> V2=BINOM(21,1)*BINOM(32,9)*BINOM(21,1)*BINOM(26,9) ... (complete aqui) e aqui fazemos um raciocinio absolutamente semelhante ao caso acima. No final calculamos o somatorio de todos os Vi A unica pergunta não obvia e a seguinte : quantas comissoes existem tais que, simultaneamente, existam no maximo 7 pessoas fluentes em frances e no maximo 10 pessoas com Ph"D" em Matematica ? Se existe alguma inteligencia neste problema ela esta aqui. O resto que vimos acima e trivial e truculento. Se a resposta a pergunta e "nao", entao a resposta ao nosso problema e : R = T – somatorio Ui - somatorio Vi Se a resposta for "sim", seja W o total de comissoes nesta condicoes. Entao a resposta ao nosso problema e : R = T – somatorio Ui - somatorio Vi + W Eu afirmo que a resposta e "nao". Para ver isso claramente, consideremos : A -> homens que so dominam matematica B->homens que so dominam frances C-> homens que dominam frances e matematica D->mulheres que so dominam frances E->mulheres que so dominam matematica F-> mulheres que dominam frances e matematica. Queremos solucoes que : A+B+C =10 D+E+F=10 B+C+D+F =< 7 ( no maximo 7 pessoas dominam frances ) A+C+E+F =< 10 ( no maximo 10 ph"D" em matematica ) somando as duas ultimas equacoes ( e considerando o valor das duas primeiras ) : 20 + C + F =< 17 ... ABSURDO ! Pois C >=0 e F >= 0 Assim, a resposta ao nosso problema e : R = T – somatorio Ui - somatorio Vi FIM DO SEGUNDO ESBOCO A todos, com os melhores votos de paz profunda, sou Paulo Santa Rita 2,1604,090707 Em 09/07/07, Paulo Santa Rita<[EMAIL PROTECTED]> escreveu: Ola Artur e demais colegas desta lista ... OBM-L, O primeiro problema ( das comissoes com 10 homens e 10 mulheres ) me parece impossivel por combinatoria ou por qualquer outro metodo simplesmente porque e inconsistente : 21 + 25 + 12 = 57 > 53 ... O mesmo para as mulheres ! Se nao fosse essa limitacao e facil fazer por combinatoria. Quanto ao segundo, e trivial. Vou apenas esbocar a solucao. Por favor, complete os detalhes : X1, X2, ..., X365 sao os dias do ano. As solucoes inteira
Re: [obm-l] Analise combinatoria - quantas comissoes?
Ola Artur e demais colegas desta lista ... OBM-L, O primeiro problema ( das comissoes com 10 homens e 10 mulheres ) me parece impossivel por combinatoria ou por qualquer outro metodo simplesmente porque e inconsistente : 21 + 25 + 12 = 57 > 53 ... O mesmo para as mulheres ! Se nao fosse essa limitacao e facil fazer por combinatoria. Quanto ao segundo, e trivial. Vou apenas esbocar a solucao. Por favor, complete os detalhes : X1, X2, ..., X365 sao os dias do ano. As solucoes inteiras nao negativas de X1 + X2 + ... + X365 = 200 podem ser vistas como as imagens da funcao f que voce cita. Assim, a titulo de exemplo, a solucao (200,0,0,...,0) significa que todas as pessoas fizeram aniversario no primeiro dia do ano. O numero de solucoes inteiras e nao-negativas da equacao acima e bem conhecido. Fixando-se, a titulo de exemplificacao, na variavel X1, precisamos determinar em quantas solucoes ela tem o valor maximo . Assim : Formato : (200,0,0,...,0) -> 1 solucao Formato : (199,1,0,...,0) -> 364 solucoes formato : (198,1,1,0,...,0) -> binom(264,2) -> solucoes Agora e so ir decendo ate 100, pois e impossivel algu outro dia ter mais que 100 aniversariantes dado que ha somente 200 pessoas. ABAIXO DE 100 : Solucoes com 99 na posicao 1 mas que ocupam 3 lugares, tipo (99,99,2,...,0) tambem satirsfazem as condicoes impostas. Isso da um total de binom(364,2), solucoes som 99 na posicao 1 e que ocupam 4 lugares, tipo (99,98,1,1,0,0,...,0) tambem satisfazem e assim sucessivamente. Fixado um Numero < 100 basta considerar os casos em que os dias nos quais nao ocorre aniversario impossibilita ocorrer um maximo em outro local diferente do primeiro. Agora retiramos do total de solucoes de X1 + X2 + ...+X365=200 as solucoes que tem maximo em X1 ( na primeira posicao ) isso da a probabilidade para o dia 1. Por simetria, vale para qualquer dia. O primeiro problema tambem e simples, mas trabalhoso. O total de comissoes e : T = BINOM(53,10)*BINOM(47,10) Agora basta retirar do total acima as comissoes impossiveis, tipo, todas aquelas nas quais no maximo 7 pessoas sao fluentes em frances ( facil de calcular ) e assim sucessivamente Um Abracao pra todos Paulo Santa Rita 2,1201,090707 Em 02/07/07, Artur Costa Steiner<[EMAIL PROTECTED]> escreveu: Eu resolvi este problema montando equacoes nas variaveis envolvidas e recorrendo a um algorimo de programacao inteira. Talvez haja uma solucao por analise combinatoria, mas me pareceu complicado. Numa empresa ha 100 funcionarios, 53 homens, 47 mulheres. Dentre os homens, 21 sao fluentes em Frances mas nao sabem Matematica, 25 tem Phd em matematica mas nao falam Frances e 12 sao fluentes em Frances e tem Phd em Matematica. Dentre as mulheres, 26 sao fluentes em Frances mas nao sabem matematica, 17 tem PHD em matematica mas nao falam Frances e 9 sao fluentes em Frances e tem Phd em matematica. O gerente quer formar uma comissao de 20 pessoas com os seguinte critérios: Tem que haver 10 homens e 10 mulheres. Pelo menos 8 pessoas tem que ser fluentes em Frances. Pelo menos 11 pessoas tem que ter Phd em matematica. Atendendo a tais criterios, quantas comissoes podem ser formadas? Artur = 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 =
Re: [obm-l] Analise combinatoria - quantas comissoes?
Olá Artur! Gostaria de confirmar alguns dados do problema, pois acho que não entendi direito. Sejam: F,~M - pessoas fluentes em Francês e não sabem Matemática (não tem PHD em Matemática) ~F,M - pessoas que não falam Francês (não são fluentes) e sabem Matemática (tem PHD em Matemática) F,M - pessoas fluentes em Francês e tem PHD em Matemática Os três conjuntos seriam disjuntos, não? Uma pessoa em F,~M não sabe Matemática, portanto não estaria em ~F,M nem em F,M. Uma pessoa em ~F,M não tem fluência em Francês, portanto não estaria em F,~M nem em F,M. Uma pessoa em F,M não estaria em F,~M (por saber Matemática) nem em ~F,M (por ser fluente em Francês). Dessa forma, somando a quantidade de pessoas fornecidas para cada conjunto (homens ou mulheres) deveríamos ter o número total (ou menos, caso houvessem pessoas do conjunto ~F,~M), mas essa soma excede os números fornecidos pelo problema: 21+25+12 > 53 e 26+17+9 > 47. Intrepretei erradamente os dados? On 7/2/07, Artur Costa Steiner <[EMAIL PROTECTED]> wrote: Eu resolvi este problema montando equacoes nas variaveis envolvidas e recorrendo a um algorimo de programacao inteira. Talvez haja uma solucao por analise combinatoria, mas me pareceu complicado. Numa empresa ha 100 funcionarios, 53 homens, 47 mulheres. Dentre os homens, 21 sao fluentes em Frances mas nao sabem Matematica, 25 tem Phd em matematica mas nao falam Frances e 12 sao fluentes em Frances e tem Phd em Matematica. Dentre as mulheres, 26 sao fluentes em Frances mas nao sabem matematica, 17 tem PHD em matematica mas nao falam Frances e 9 sao fluentes em Frances e tem Phd em matematica. O gerente quer formar uma comissao de 20 pessoas com os seguinte critérios: Tem que haver 10 homens e 10 mulheres. Pelo menos 8 pessoas tem que ser fluentes em Frances. Pelo menos 11 pessoas tem que ter Phd em matematica. Atendendo a tais criterios, quantas comissoes podem ser formadas? Artur = 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 = -- Henrique
Re: [obm-l] Analise combinatoria - quantas comissoes?
Tenho um outro problema, para o qual nunca cheguei a uma solução. A mim me parece impossível de calcular a resposta manualmente. Imagine-se num grupo de 200 pessoas, e imagine que todos os anos tenham 365 dias (isto é: ignore a existência de anos bissextos). Seja f: {dias} -> N tal que f(d) = número de aniversariantes no dia d. Seja d_0 o dia de seu aniversário. Qual é a probabilidade de que f(d_0) seja um máximo da função f? Generalize: seja p o número total de pessoas, e k o número de dias num ano. A mesma f, o mesmo d_0 e a mesma pergunta. Abraço Bruno 2007/7/2, Artur Costa Steiner <[EMAIL PROTECTED]>: Eu resolvi este problema montando equacoes nas variaveis envolvidas e recorrendo a um algorimo de programacao inteira. Talvez haja uma solucao por analise combinatoria, mas me pareceu complicado. Numa empresa ha 100 funcionarios, 53 homens, 47 mulheres. Dentre os homens, 21 sao fluentes em Frances mas nao sabem Matematica, 25 tem Phd em matematica mas nao falam Frances e 12 sao fluentes em Frances e tem Phd em Matematica. Dentre as mulheres, 26 sao fluentes em Frances mas nao sabem matematica, 17 tem PHD em matematica mas nao falam Frances e 9 sao fluentes em Frances e tem Phd em matematica. O gerente quer formar uma comissao de 20 pessoas com os seguinte critérios: Tem que haver 10 homens e 10 mulheres. Pelo menos 8 pessoas tem que ser fluentes em Frances. Pelo menos 11 pessoas tem que ter Phd em matematica. Atendendo a tais criterios, quantas comissoes podem ser formadas? Artur = 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 = -- Bruno França dos Reis email: bfreis - gmail.com gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key icq: 12626000 e^(pi*i)+1=0
Re: [obm-l] Analise combinatoria - quantas comissoes?
Olá Artur, realmente, nao encontrei uma solucao por combinatoria.. acho que fiz semelhante a voce, recorrendo a equacoes (nao cheguei a resolve-las.. mas nao vi outro modo).. quem sabe alguem aqui tenha uma boa ideia? pra mim, a grande dificuldade foi fixar 10 homens e 10 mulheres... abracos, Salhab On 7/2/07, Artur Costa Steiner <[EMAIL PROTECTED]> wrote: Eu resolvi este problema montando equacoes nas variaveis envolvidas e recorrendo a um algorimo de programacao inteira. Talvez haja uma solucao por analise combinatoria, mas me pareceu complicado. Numa empresa ha 100 funcionarios, 53 homens, 47 mulheres. Dentre os homens, 21 sao fluentes em Frances mas nao sabem Matematica, 25 tem Phd em matematica mas nao falam Frances e 12 sao fluentes em Frances e tem Phd em Matematica. Dentre as mulheres, 26 sao fluentes em Frances mas nao sabem matematica, 17 tem PHD em matematica mas nao falam Frances e 9 sao fluentes em Frances e tem Phd em matematica. O gerente quer formar uma comissao de 20 pessoas com os seguinte critérios: Tem que haver 10 homens e 10 mulheres. Pelo menos 8 pessoas tem que ser fluentes em Frances. Pelo menos 11 pessoas tem que ter Phd em matematica. Atendendo a tais criterios, quantas comissoes podem ser formadas? Artur = 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 =
Re:[obm-l] Analise Combinatoria
De:[EMAIL PROTECTED] Para:obm-l@mat.puc-rio.br Cópia: Data:Mon, 12 Feb 2007 22:21:10 + (GMT) Assunto:[obm-l] Analise Combinatoria > Estou com muita dificuldade em resolver esta questao, e gostaria muito de > ajuda. > > 1) Depois de ter dado um curso, um professor resolve se despedir de seus 7 > alunos oferecendo, durante 7 dias consecutivos, 7 jantares para cada 3 > alunos. De quantos modos ele pode fazer os convites se ele nao deseja que um > mesmo par de alunos compareça a mais de um jantar? Resp:151.200 > > Obrigado por enquanto. Chame os alunos de 1, 2, 3, 4, 5, 6 e 7. Cada aluno deve jantar exatamente uma vez com cada um dos 6 colegas e deve ser acompanhado por exatamente 2 colegas em cada jantar. Logo, participa de 6/2 = 3 jantares. Tomemos o aluno 1. Num dos jantares ele necessariamente encontrará o aluno 2. O terceiro aluno deste jantar pode ser escolhido de 5 maneiras distintas. Digamos que o aluno 3 seja escolhido. Assim, um dos jantares será {1,2,3}. Num segundo jantar, 1 necessariamente encontrará 4. O terceiro participante deste jantar pode ser escolhido de 3 maneiras distintas (dentre 5, 6 e 7). Digamos que seja o aluno 5. Assim, o segundo jantar de 1 será {1,4,5} O terceiro jantar de 1 será necessariamente {1,6,7}. Vejamos agora o segundo jantar do aluno 2 (o primeiro foi {1,2,3}). Ele necessariamente encontrará o aluno 4. Digamos que seja nesse jantar. O terceiro participante desse jantar pode ser escolhido de 2 maneiras distintas (só pode ser 6 ou 7). Digamos que seja 6. Isso implica que o segundo jantar de 2 será {2,4,6}. O terceiro jantar de 2 será necessariamente {2,5,7}. Repare que, a essa altura, o aluno 4 já participou dos jantares {1,4,5} e {2,4,6}. Logo, o terceiro jantar de 4 será necessariamente {3,4,7}. Mas, nesse caso, como 3 já participou de {1,2,3} e {3,4,7}, o seu terceiro jantar só pode ser {3,5,6}. Em suma, temos os 7 jantares: {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, (3,4,7} e {3,5,6}. A fim de determiná-los, tivemos que escolher: i) dentre 5 alternativas para o primeiro jantar de 1; ii) dada a primeira escolha, dentre 3 alternativas para o segundo jantar de 1, e iii) dadas as duas escolhas anteriores, dentre 2 alternativas para o segundo jantar de 2. Total = 5*3*2 = 30 alternativas. (ou seja, existem 30 conjuntos distintos de 7 jantares cada nas condições do enunciado) Finalmente, como os jantares podem acontecer em qualquer ordem durante os 7 dias, o número total de maneiras do professor dar os 7 jantares é igual a 30*7! = 30*5040 = 151200. []s, Claudio.
Re: [obm-l] analise combinatoria
A condição é que todos os n elementos do conjunto A devem possuir uma e só uma imagem. Se A={a1,...,an} e B={b1,...,br}, então existem r escolhas para a imagem de a1, r escolhas para a imagem de a2, ... , r escolhas para a imagem de an. Temos então r.r.r.r. ... .r, com n fatores r. Logo, r^n funções. Um abraço, João Luís. - Original Message - From: ivanzovisk To: obm-l Sent: Saturday, November 11, 2006 9:31 PM Subject: [obm-l] analise combinatoria A e B são conjuntos tais que #A=n e #B=r. Quantas funções f de A em B existem?
Re: [obm-l] analise combinatoria
Todos os n elementos de A devem ser relacionados com um elemento do conjunto B.Determinando a ordem do conjunto A como (a1,a2,a3,...,an), devo criar um (b1,b2,b3,...,bn) com os elementos de B. É necessario apenas escolher as sequencias do conjunto B. A unica condicao para um determinado elemento da segunda sequencia é pertencer ao conjunto B. Teremos r possibilidades para cada um dos termos da sequencia, e portanto o numero de funcoes será r^n.Iuri On 11/11/06, ivanzovisk <[EMAIL PROTECTED]> wrote: A e B são conjuntos tais que #A=n e #B=r. Quantas funções f de A em B existem?
Re: [obm-l] analise combinatoria
Ola pessoal do grupo poderiam me ajudar com esta questão? escola naval 2001 Considere uma progressão geométrica de razão maior do que 1 em que três de seus termos consecutivos representam as medidas dos lados de um triângulo retângulo. Se o primeiro termo dessa progressão geométrica é 64, então seu décimo terceiro termo vale: = 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 =
Re: [obm-l] analise combinatoria
obrigado mas no numero 2 houve um pequeno erro onde 2 bolas: 5*3 + 3*2 + 5*2 = 15+6+10 = 31 e nao 21 como esta no resultado mas mesmo assim muito obrigado ontem eu tava malzao e nao onsegui pensa nisso brigadao mesmo - Original Message - From: "Davi de Melo Jorge Barbosa" <[EMAIL PROTECTED]> To: Sent: Monday, May 09, 2005 11:21 PM Subject: Re: [obm-l] analise combinatoria 1- n = 9 * 9 * 8 = 648 (o primeiro numero nao pode ser 0) 2- Pode-se pedir: 1 bola: 5 + 3 + 2 = 10 maneiras 2 bolas: 5*3 + 3*2 + 5*2 = 15 + 6 + 10 = 21 maneiras 3 bolas: 5*3*2 = 30 maneiras total: 10 + 21 + 30 = 61 maneiras distintas. deve ser isso. On 5/9/05, RAfitcho <[EMAIL PROTECTED]> wrote: No sistema decimal de numeração, os números inteiros entre 100 e 999 que possuem algarismos diferentes constituem um conjunto com n elementos. O valor de n é: A) 720 B) 648 C) 576 D) 504 Em uma lanchonete, os sorvetes são divididos em três grupos: o vermelho, com 5 sabores; o amarelo, com 3 sabores; e o verde, com 2 sabores. Pode-se pedir uma casquinha com 1, 2 ou 3 bolas, mas cada casquinha não pode conter 2 bolas de um mesmo grupo. O número de maneiras distintas de se pedir uma casquinha é A) 71 B) 86 C) 131 D) 61 = 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 =
Re: [obm-l] analise combinatoria
1- n = 9 * 9 * 8 = 648 (o primeiro numero nao pode ser 0) 2- Pode-se pedir: 1 bola: 5 + 3 + 2 = 10 maneiras 2 bolas: 5*3 + 3*2 + 5*2 = 15 + 6 + 10 = 21 maneiras 3 bolas: 5*3*2 = 30 maneiras total: 10 + 21 + 30 = 61 maneiras distintas. deve ser isso. On 5/9/05, RAfitcho <[EMAIL PROTECTED]> wrote: > No sistema decimal de numeração, os números inteiros entre 100 e 999 que > possuem algarismos diferentes constituem um conjunto com n elementos. O > valor de n é: > > A) 720 B) 648 C) 576 D) 504 > > > Em uma lanchonete, os sorvetes são divididos em três grupos: o vermelho, com > 5 sabores; o amarelo, com 3 sabores; e o verde, com 2 sabores. > > Pode-se pedir uma casquinha com 1, 2 ou 3 bolas, mas cada casquinha não pode > conter 2 bolas de um mesmo grupo. > > O número de maneiras distintas de se pedir uma casquinha é > > A) 71 > > B) 86 > > C) 131 > > D) 61 > > > > = 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 =
Re: [obm-l] Analise Combinatoria - Probleminha...
Seja z um inteiro não nulo tal que z=(a1)^x.(a2)y.(a3) ^z. ... (an)^t , todos ai primos entre si, o conjunto {a1, a2, ... , an} é único, ou seja, z tem fatoração única logo {1}={1, 1} mais estranho né.. pq 1 não é primo, logo não admite fatoração.. poderia pensar em algebra linear... 1 é o elemento neutro da multiplicação ... segundo definição, ou algo do tipo. > desculpe a burrice, mas o que é fatoração unica :P > > (ué, 1 é divisivel por 1 e por ele mesmo :P hehehe) > > fabiano > - Original Message - > From: "Ricardo Bittencourt" <[EMAIL PROTECTED]> > To: <[EMAIL PROTECTED]> > Sent: Tuesday, March 23, 2004 12:32 AM > Subject: Re: [obm-l] Analise Combinatoria - Probleminha... > > > > Fabiano Sant'Ana wrote: > > > > > o que é um primo absoluto? > > > 1,2,3,5,7? > > > > Vale lembrar 1 não é primo; se fosse, não haveria > > fatoração única dos naturais. > > > > --- > Outgoing mail is certified Virus Free. > Checked by AVG anti-virus system (http://www.grisoft.com). > Version: 6.0.624 / Virus Database: 401 - Release Date: 16/03/04 > > = > 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 > = > Atenciosamente, Futuro Engenheiro Eletricista Osvaldo Mello Sponquiado FEIS - UNESP Usuário em GNU/Linux __ 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 =
Re: [obm-l] Analise Combinatoria - Probleminha...
"Se alguem por exemplo diz que 24=3*2^2, nenhuma outra pessoa pode obter algo diferente (a nao ser que tenha errado a conta :( )." realmente, fatoracao unica! - Original Message - From: Johann Peter Gustav Lejeune Dirichlet To: [EMAIL PROTECTED] Sent: Tuesday, March 23, 2004 12:16 PM Subject: Re: [obm-l] Analise Combinatoria - Probleminha... Sempre que nos naturais ce tem que fatorar em primos, nao podem haver duas fatoraçoes diferentes (a nao ser na ordem dos primos). Se alguem por exemplo diz que 24=3*2^2, nenhuma outra pessoa pode obter algo diferente (a nao ser que tenha errado a conta :( ). Se voce enfiasse o 1 como primo, voce poderia dizer que 24=2^2*3=1*2^2*3=1^2004*2^2*3=. PS: me diga dois numeros DIFERENTES que dividem 1Fabiano Sant'Ana <[EMAIL PROTECTED]> wrote: desculpe a burrice, mas o que é fatoração unica :P(ué, 1 é divisivel por 1 e por ele mesmo :P hehehe)fabiano- Original Message -From: "Ricardo Bittencourt" <[EMAIL PROTECTED]>To: <[EMAIL PROTECTED]>Sent: Tuesday, March 23, 2004 12:32 AMSubject: Re: [obm-l] Analise Combinatoria - Probleminha...> Fabiano Sant'Ana wrote:>> > o que é um primo absoluto?> > 1,2,3,5,7?>> Vale lembrar 1 não é primo; se fosse, não haveria> fatoração única dos naturais.---Outgoing mail is certified Virus Free.Checked by AVG anti-virus system (http://www.grisoft.com).Version: 6.0.624 / Virus Database: 401 - Release Date: 16/03/04=Instruções para entrar na lista, sair da lista e usar ! a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html= TRANSIRE SVVM PECTVS MVNDOQVE POTIRI CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE Fields Medal(John Charles Fields) Yahoo! Mail - O melhor e-mail do Brasil. Abra sua conta agora!
Re: [obm-l] Analise Combinatoria - Probleminha...
On Tue, Mar 23, 2004 at 01:53:36AM -0300, Fabiano Sant'Ana wrote: > desculpe a burrice, mas o que é fatoração unica :P > > (ué, 1 é divisivel por 1 e por ele mesmo :P hehehe) > > Fabiano Sant'Ana wrote: > > > > > o que é um primo absoluto? > > > 1,2,3,5,7? > > > > Vale lembrar 1 não é primo; se fosse, não haveria > > fatoração única dos naturais. De acordo com qualquer referência moderna, 1 não é primo. Mas se você olhar em livros bem antigos, você encontrará alguns em que 1 é definido como primo. Há na biblioteca do Impa uma tabelas de primos (chuto que sejam do início do século 20) e elas incluem o 1 como primo. []s, N. = 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 =
Re: [obm-l] Analise Combinatoria - Probleminha...
Sempre que nos naturais ce tem que fatorar em primos, nao podem haver duas fatoraçoes diferentes (a nao ser na ordem dos primos). Se alguem por exemplo diz que 24=3*2^2, nenhuma outra pessoa pode obter algo diferente (a nao ser que tenha errado a conta :( ). Se voce enfiasse o 1 como primo, voce poderia dizer que 24=2^2*3=1*2^2*3=1^2004*2^2*3=. PS: me diga dois numeros DIFERENTES que dividem 1Fabiano Sant'Ana <[EMAIL PROTECTED]> wrote: desculpe a burrice, mas o que é fatoração unica :P(ué, 1 é divisivel por 1 e por ele mesmo :P hehehe)fabiano- Original Message -From: "Ricardo Bittencourt" <[EMAIL PROTECTED]>To: <[EMAIL PROTECTED]>Sent: Tuesdday, March 23, 2004 12:32 AMSubject: Re: [obm-l] Analise Combinatoria - Probleminha...> Fabiano Sant'Ana wrote:>> > o que é um primo absoluto?> > 1,2,3,5,7?>> Vale lembrar 1 não é primo; se fosse, não haveria> fatoração única dos naturais.---Outgoing mail is certified Virus Free.Checked by AVG anti-virus system (http://www.grisoft.com).Version: 6.0.624 / Virus Database: 401 - Release Date: 16/03/04=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html= TRANSIRE SVVM PECTVS MVNDOQVE POTIRI CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE Fields Medal(John Charles Fields)Yahoo! Mail - O melhor e-mail do Brasil. Abra sua conta agora!
Re: [obm-l] Analise Combinatoria - Probleminha...
desculpe a burrice, mas o que é fatoração unica :P (ué, 1 é divisivel por 1 e por ele mesmo :P hehehe) fabiano - Original Message - From: "Ricardo Bittencourt" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Tuesday, March 23, 2004 12:32 AM Subject: Re: [obm-l] Analise Combinatoria - Probleminha... > Fabiano Sant'Ana wrote: > > > o que é um primo absoluto? > > 1,2,3,5,7? > > Vale lembrar 1 não é primo; se fosse, não haveria > fatoração única dos naturais. --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.624 / Virus Database: 401 - Release Date: 16/03/04 = 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 =
Re: [obm-l] Analise Combinatoria - Probleminha...
Title: Re: [obm-l] Analise Combinatoria - Probleminha... on 23.03.04 00:13, Fabiano Sant'Ana at [EMAIL PROTECTED] wrote: o que é um primo absoluto? 1,2,3,5,7? fabiano 1 nao eh primo.
Re: [obm-l] Analise Combinatoria - Probleminha...
Fabiano Sant'Ana wrote: o que é um primo absoluto? 1,2,3,5,7? Vale lembrar 1 não é primo; se fosse, não haveria fatoração única dos naturais. Ricardo Bittencourt http://www.mundobizarro.tk [EMAIL PROTECTED] "tenki ga ii kara sanpo shimashou" -- União contra o forward - crie suas proprias piadas -- = 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 =
Re: [obm-l] Analise Combinatoria - Probleminha...
o que é um primo absoluto? 1,2,3,5,7? fabiano - Original Message - From: Fabio Contreiras To: [EMAIL PROTECTED] Sent: Monday, March 22, 2004 11:23 PM Subject: [obm-l] Analise Combinatoria - Probleminha... Ola pessoal, me deparei com esse problema e nao consigo achar a resposta do gabarito que é 42. De quantas maneiras podemos escrever um numero com 3 algarismos distintos , sendo que o os 2 primeiros sao primos absolutos e o ultimo é divisivel por 3... abraços!!! ---Outgoing mail is certified Virus Free.Checked by AVG anti-virus system (http://www.grisoft.com).Version: 6.0.624 / Virus Database: 401 - Release Date: 16/03/04
Re: [obm-l] Analise Combinatoria - Probleminha...
Title: Re: [obm-l] Analise Combinatoria - Probleminha... on 22.03.04 23:23, Fabio Contreiras at [EMAIL PROTECTED] wrote: Ola pessoal, me deparei com esse problema e nao consigo achar a resposta do gabarito que é 42. De quantas maneiras podemos escrever um numero com 3 algarismos distintos , sendo que o os 2 primeiros sao primos absolutos e o ultimo é divisivel por 3... abraços!!! Divida em casos: Caso 1: o 3o. algarismo eh 3. Escolha do 1o. algarismo: 3 (as unicas possibilidades sao 2, 5 e 7, pois o 3 jah foi usado) Escolha do 2o. algarismo: 2 Sub-total do Caso 1: 3*2 = 6 Caso 2: o ultimo algarismo eh 0, 6 ou 9 (lembre-se 0 tambem eh divisivel por 3). Escolha do 3o. algarismo: 3 (0, 6 ou 9) Escolha do 1o. algarismo: 4 (2, 3, 5 ou 7) Escolha do 2o. algarismo: 3 Sub-total do caso 2: 2*4*3 = 36 Total: 6 + 36 = 42. []s, Claudio.
Re: [obm-l] analise combinatoria
Title: Re: [obm-l] analise combinatoria on 28.10.03 16:35, guilherme S. at [EMAIL PROTECTED] wrote: pessoal preciso de ajuda pra estas duas questoes: Oi, Guilherme: Aqui vao minhas tentativas: QUANTAS SAO as solucoes inteiras nao negativas da eq: x+y+z+w=20 , tal que x>y O numero de solucoes sem restricao eh Binom(23,3) = 1771. Agora dividimos em casos: x > y, x < y e x = y, observando que o numero de solucoes com x > y eh igual ao no. de solucoes com x < y. Chamemos esse numero de N. O caso x = y equivale ao no. de solucoes nao-negativas de 2x + z + w = 20. Isso eh igual ao coeficiente de x^20 no polinomio: (1+x+x^2+x^3+...+x^20)^2*(1+x^2+x^4+x^6+...+x^20), o qual, segundo o PARI-GP, eh igual a 121. (tambem dava pra calcular no braco sem muita dificuldade, fazendo x variar de 0 a 10, caso em que obteriamos: 21+19+17+...+3+1 = soma dos impares de 1 a 2*11-1 = 11^2 = 121). Logo, 2N + 121 = 1771 ==> N = 825. * quantas sao as funcoes nao decrescentes f:A->B , tal que A={1,2,3..m} e B={1,2,...n} Considere as quantidades: x1 = f(1), x2 = f(2) - f(1), x3 = f(3) - f(2), ..., xm = f(m) - f(m-1). Cada uma delas deve ser nao negativa e a soma de todas (igual a f(m) - f(1)) deve ser um inteiro entre 0 e n-1 (inclusive). Assim, a cada funcao podemos fazer corresponder uma solucao inteira nao-negativa da desigualdade: 0 <= x1 + x2 + ... + xm <= n-1. Por outro lado, a cada solucao inteira e nao negativa (x1,x2,...,xm) dessa desigualdade podemos associar uma funcao f tal que: f(1) = x1, f(2) = x1+x2, f(3) = x1+x2+x3, ..., f(m) = x1+...+xm. Logo, o numero de funcoes eh igual ao numero de solucoes da desigualdade. Esse numero eh igual a: Binom(m-1,m-1) + Binom(m,m-1) + ... + Binom(m+n-2,m-1) = Binom(m+n-1,m) (pelo teorema das colunas do triangulo de Pascal). Um abraco, Claudio.
Re: [obm-l] analise combinatoria
a restrição é só para x e y? bom, faça assim para cada possível valor de z + w, obtenha o número de pares x, y com x > y que satisfazem x + y = 20 - (z + w), assim, por exemplo para z + w = 0, temos x + y = 20, e isso tem como sol. 20 + 0, 19 + 1, ..., 11+9, ou seja 10 soluções (e z + w = 0 só tem uma) para z + w = 1, temos 2 soluções em z, w e x + y = 19 tem sol. 19 + 0, 18 + 1, ..., 10 + 9 (10 soluções em x, y * 2 sol. em z, w dá 20 soluções) continue a soma (mecanizando o processo, claro!). se A = {1} e B={1,2,..., n} existem n funções não decrescentes f:A->B suponha que g(m, n) conte quantas funções existem com f:[m] -> [n] (onde [x] = {1, 2, ..., x}) então g(1, n) = n e g(m, 1) = 1 vamos tentar obter então uma recorrência suponha f uma função não decrescente em f:[m+1] -> [n] f| é a função f definida apenas em [m], ela também é não decrescente, se soubermos qual o valor de f(m) fica fácil saber quantas funções possíveis podemos ter que sejam não decrescentes. proposição: g(m+1, n) = soma[i=1..n] { g(m, i) } a idéia é, precisamos contar todas as funções em que f(m)=k e multiplicar por n-k+1, para k = 1..n então vemos que g(m, 1) conta todas as funções com f(m) = 1 uma vez g(m, 2) conta novamente todas as funções com f(m) = 1 + uma vez ... g(m, n) conta " " " + uma vez ou seja somando todas estaremos contando as funções com f(m) = 1 exatamente n vezes o mesmo argumento se repete para um i qualquer g(m, i) conta todas as funções com f(m) = i uma vez g(m, i + 1), conta + uma vez ... g(m, n) conta + uma vez, onde as funções com f(m) = i são contadas exatamente n-i+1 vezes. [ ]'s - Original Message - From: guilherme S. To: [EMAIL PROTECTED] Sent: Tuesday, October 28, 2003 4:35 PM Subject: [obm-l] analise combinatoria pessoal preciso de ajuda pra estas duas questoes: QUANTAS SAO as solucoes inteiras nao negativas da eq: x+y+z+w=20 , tal que x>y quantas sao as funcoes nao decrescentes f:A->B , tal que A={1,2,3..m} e B={1,2,...n} Desafio AntiZona: participe do jogo de perguntas e respostas que vai dar1 Renault Clio, computadores, câmeras digitais, videogames e muito mais!
Re: [obm-l] analise combinatoria
Como é possível determinar se o resultado pedido envolve ou não rotação? Pois se eu rotacionar eu obteria 10*8*8!, ou não? Corrijam me se eu estiver errado e como determinar qual o resultado mais correto para a questão e porque. - Original Message - From: Cláudio (Prática) To: [EMAIL PROTECTED] Sent: Monday, October 27, 2003 11:58 AM Subject: Re: [obm-l] analise combinatoria Um outro jeito eh deduzir do número total de permutações circulares dos algarismos (9!) o número destas em que o 0 e o 5 ficam diametralmente opostos: Uma vez colocado o 0, há 1 maneira de se colocar o 5. Em seguida, permutam-se os 8 algarismos restantes. Total = 8!. Logo, o número desejado é 9! - 8! = 8!*(9-1) = 8!*8. - Original Message - From: Domingos Jr. To: [EMAIL PROTECTED] Sent: Monday, October 27, 2003 10:14 AM Subject: Re: [obm-l] analise combinatoria acho que está certo. fixe 0 numa posição, então o 5 pode possuir qualquer posição, exceto a diametralmente oposta, havendo 8 posições possíveis, depois os 8 demais números podem ser permutados livremente. não estamos considerando rotações das numerações (o que eu acho correto para esse problema, já que ele o polígono é regular e os vértices não possuem nomes). - Original Message - From: Silvio Borges To: [EMAIL PROTECTED] Sent: Monday, October 27, 2003 8:42 AM Subject: [obm-l] analise combinatoria Gostaria que me ajudassem nesta questao, eu fiz mas tenho duvidas quanto a resposta encontrada. Muito obrigado Silvio. A questao e a seguinte : De quantas maneiras podemos dispor os numeros de 0 a 9, nos vertices de um decagono regular, de modo que o 0 e o 5 nao fiquem diametralmente opostos ? eu encontrei 8 * 8! Esta mensagem foi verificada pelo E-mail Protegido Terra.Scan engine: VirusScan / Atualizado em 22/10/2003 / Versão: 1.4.0Proteja o seu e-mail Terra: http://www.emailprotegido.terra.com.br/
Re: [obm-l] analise combinatoria
Title: Re: [obm-l] analise combinatoria Pensei numa maneira mais bonitinha de resolver esse: Seja N(k) = numero de permutacoes circulares onde o k fica diametralmente oposto ao 0 (1<=k<=9). Eh claro que N(1) + N(2) + ... + N(9) = 9! Tambem deveria ser obvio que N(1) = N(2) = ... = N(9) = N (um argumento de simetria deveria bastar. Caso contrario, estabeleca uma bijecao entre o conjunto das permutacoes que tem 0 oposto a i e o das permutacoes que tem 0 oposto a j (1<=i<=j<=9)). Assim, teremos 9*N = 9! ==> N = 8!. Mas o que queremos de fato eh N(1) + ... + N(4) + N(6) + ... + N(9) = 8*N = 8*8!. Um abraco, Claudio. on 27.10.03 11:58, Cláudio (Prática) at [EMAIL PROTECTED] wrote: Um outro jeito eh deduzir do número total de permutações circulares dos algarismos (9!) o número destas em que o 0 e o 5 ficam diametralmente opostos: Uma vez colocado o 0, há 1 maneira de se colocar o 5. Em seguida, permutam-se os 8 algarismos restantes. Total = 8!. Logo, o número desejado é 9! - 8! = 8!*(9-1) = 8!*8. - Original Message - From: Domingos Jr. To: [EMAIL PROTECTED] Sent: Monday, October 27, 2003 10:14 AM Subject: Re: [obm-l] analise combinatoria acho que está certo. fixe 0 numa posição, então o 5 pode possuir qualquer posição, exceto a diametralmente oposta, havendo 8 posições possíveis, depois os 8 demais números podem ser permutados livremente. não estamos considerando rotações das numerações (o que eu acho correto para esse problema, já que ele o polígono é regular e os vértices não possuem nomes). - Original Message - From: Silvio Borges To: [EMAIL PROTECTED] Sent: Monday, October 27, 2003 8:42 AM Subject: [obm-l] analise combinatoria Gostaria que me ajudassem nesta questao, eu fiz mas tenho duvidas quanto a resposta encontrada. Muito obrigado Silvio. A questao e a seguinte : De quantas maneiras podemos dispor os numeros de 0 a 9, nos vertices de um decagono regular, de modo que o 0 e o 5 nao fiquem diametralmente opostos ? eu encontrei 8 * 8!
Re: [obm-l] analise combinatoria
Um outro jeito eh deduzir do número total de permutações circulares dos algarismos (9!) o número destas em que o 0 e o 5 ficam diametralmente opostos: Uma vez colocado o 0, há 1 maneira de se colocar o 5. Em seguida, permutam-se os 8 algarismos restantes. Total = 8!. Logo, o número desejado é 9! - 8! = 8!*(9-1) = 8!*8. - Original Message - From: Domingos Jr. To: [EMAIL PROTECTED] Sent: Monday, October 27, 2003 10:14 AM Subject: Re: [obm-l] analise combinatoria acho que está certo. fixe 0 numa posição, então o 5 pode possuir qualquer posição, exceto a diametralmente oposta, havendo 8 posições possíveis, depois os 8 demais números podem ser permutados livremente. não estamos considerando rotações das numerações (o que eu acho correto para esse problema, já que ele o polígono é regular e os vértices não possuem nomes). - Original Message - From: Silvio Borges To: [EMAIL PROTECTED] Sent: Monday, October 27, 2003 8:42 AM Subject: [obm-l] analise combinatoria Gostaria que me ajudassem nesta questao, eu fiz mas tenho duvidas quanto a resposta encontrada. Muito obrigado Silvio. A questao e a seguinte : De quantas maneiras podemos dispor os numeros de 0 a 9, nos vertices de um decagono regular, de modo que o 0 e o 5 nao fiquem diametralmente opostos ? eu encontrei 8 * 8!
Re: [obm-l] analise combinatoria
acho que está certo. fixe 0 numa posição, então o 5 pode possuir qualquer posição, exceto a diametralmente oposta, havendo 8 posições possíveis, depois os 8 demais números podem ser permutados livremente. não estamos considerando rotações das numerações (o que eu acho correto para esse problema, já que ele o polígono é regular e os vértices não possuem nomes). - Original Message - From: Silvio Borges To: [EMAIL PROTECTED] Sent: Monday, October 27, 2003 8:42 AM Subject: [obm-l] analise combinatoria Gostaria que me ajudassem nesta questao, eu fiz mas tenho duvidas quanto a resposta encontrada. Muito obrigado Silvio. A questao e a seguinte : De quantas maneiras podemos dispor os numeros de 0 a 9, nos vertices de um decagono regular, de modo que o 0 e o 5 nao fiquem diametralmente opostos ? eu encontrei 8 * 8!
RE: [obm-l] analise combinatoria
Resposta: 2 cores Pegue um ponto de uma região qualquer e veja quantos círculos contém este ponto. Se for um número ímpar, pinte de verde. Se for par, de amarelo. Prova: Basta analisar duas regiões de fronteira. São delimitadas por uma circunferência, ou seja, uma região possui N e a outra N+1 circunferência que as contém! -Original Message- From: Rafael [mailto:[EMAIL PROTECTED]] Sent: Thursday, December 19, 2002 2:53 PM To: OBM Subject: [obm-l] analise combinatoria Segue uma questão que caiu na segunda fase do vestibular da Universidade Federal de Pernambuco em 1999. Se alguém souber o porque da resposta... 07. A figura abaixo contém seis círculos. Um designer pretende colorir as regiões em que fica dividido o círculo maior de forma que regiões tendo um mesmo arco de circunferência como fronteira sejam coloridas com cores diferentes. Assinale o número mínimo de cores a serem utilizadas. (segue a figura circulos.gif anexada) Grato, Rafael. ___ Busca Yahoo! O melhor lugar para encontrar tudo o que você procura na Internet http://br.busca.yahoo.com/ = 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]> =
Re: [obm-l] analise combinatoria
A resposta é 2. Com 1 cor obviamente não é possível. Com 2 cores veja a figura em anexo. Observe que existe uma região que tem --- Rafael <[EMAIL PROTECTED]> escreveu: > Segue uma questão que caiu na segunda fase do > vestibular da Universidade Federal de Pernambuco em > 1999. Se alguém souber o porque da resposta... > > 07. A figura abaixo contém seis círculos. Um designer > pretende colorir as regiões em que fica dividido o > círculo maior de forma que regiões tendo um mesmo arco > de circunferência como fronteira sejam coloridas com > cores diferentes. Assinale o número mínimo de cores a > serem utilizadas. > > (segue a figura circulos.gif anexada) > > Grato, > > Rafael. > > __ _ > Busca Yahoo! > O melhor lugar para encontrar tudo o que você procura na Internet > http://br.busca.yahoo.com/ > ATTACHMENT part 2 image/gif name=circulos.gif --- UOL, o melhor da Internet http://www.uol.com.br/ circulop.gif Description: Binary data
Re: [obm-l] Analise Combinatoria, conceitos militares
No meio de tanta coisa séria que é tratada aqui, eu quis fazer "uma pausa para recreio, tal como nos tempos de escola", conforme procurei deixar bem claro na minha mensagem ao usar expressões pouco acadêmicas como "Se é para levar a frescura um degrau acima", "Para evitar esta v toda" e "Não sei como V faria para evitar uma p... briga na geral do Maracanã!". Infelizmente fui mal compreendido. Isto não se repetirá. JF - Original Message - From: "Adriano Almeida Faustino" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Saturday, June 15, 2002 2:39 PM Subject: Re: [obm-l] Analise Combinatoria, conceitos militares > > Nao me interessa,se nao gostou mude a questao mas que a ideia seja a mesma. > A questao nem e` minha,so me deram e eu queria saber se poderia usar os > lemas de Kaplansky,por isso enviei a questao!!! > > Adriano. > > >From: "Jose Francisco Guimaraes Costa" <[EMAIL PROTECTED]> > >Reply-To: [EMAIL PROTECTED] > >To: <[EMAIL PROTECTED]> > >Subject: [obm-l] Analise Combinatoria, conceitos militares > >Date: Thu, 6 Jun 2002 10:04:54 -0300 > > > >Para evitar problemas que V poderia ter se estivesse na conferência no > >auditório do IME, duas pequenas correções quanto à parte não matemática do > >problema: (1) almirantes, generais e brigadeiros são oficiais generais, e > >não oficiais superiores (na marinha os oficiais superiores são os capitães > >de corveta, fragata e mar-e-guerra, e no exército e aeronáutica os majores, > >tenentes coronéis e coronéis); (2) marinha, exército e aeronáutica são > >"forças" e não "armas" ("armas" - conceito que só se aplica ao exército - > >são infantaria, cavalaria e artilharia). > > > >Se é para levar a frescura um degrau acima, sendo o IME uma "OM" > >(Organização Militar), os oficiais generais estariam assentados de acordo > >com sua "antiguidade" (hierarquia): o mais "antigo" ao centro e os mais > >"modernos" alternadamente à direita e à esquerda dele. > > > >Para evitar esta v toda, sugiro trocar no enunciado do problema > >"conferência" por "jogo de futebol", "IME" por "Maracanã"; "auditório" por > >"geral", "7 oficiais" por "7 torcedores" e "generais, almirantes e > >brigadeiros" por "flamenguistas, fluminenses e vascaínos". > > > >Não sei como V faria para evitar uma p... briga na geral do Maracanã! > > > >JF > > > >PS: considerem isso uma pausa para recreio, tal como nos tempos de escola. > > > >- Original Message - > >From: "Adriano Almeida Faustino" <[EMAIL PROTECTED]> > >To: <[EMAIL PROTECTED]> > >Sent: Thursday, June 06, 2002 1:27 AM > >Subject: [obm-l] Analise Combinatoria > > > > > > > estou com duvida nessa questao e queria que alguem me ajudasse > > > > > > Para uma conferencia realizada no auditorio do IME,foram reservados 7 > > > lugares,que serao ocupados por 7 oficiais superiores.Sabendo-se que 3 > >sao > > > generais,2 almirantes e 2,brigadeiros e que estes lugares estao na > >primeira > > > fila,um ao lado do outro,determine de quantos modos podemos > >acomoda-los,sem > > > que haja sentados juntos oficiais de uma mesma arma. > > > []`s > > > Adriano. > > > > > > > > > > > > > > > > > > > > > > > > > > > _ > > > Envie e receba emails com o Hotmail no seu dispositivo móvel: > > > http://mobile.msn.com > > > > > > > >= > > > 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]> > > > > >= > > > > > > >= > >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]> > >= > > > _ > Chegou o novo MSN Explorer. Instale já. É gratuito: > http://explorer.msn.com.br > > = > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > O administrador desta lista é <[EMAIL PROTECTED]> > = > = 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]> =
Re: [obm-l] Analise Combinatoria, conceitos militares
Essas manifestaçoes de mau humor, como ja disse o Nicolau, nao devem ser mandadas para a lista e sim diretamente para o alvo visado. Tais manifestaçoes ja tiveram como resultado a auto-exclusao de um membro proeminente desta lista, o Prof. Dr. Jose Paulo Quinhoes Carneiro. Morgado Adriano Almeida Faustino wrote: > > Nao me interessa,se nao gostou mude a questao mas que a ideia seja a > mesma. > A questao nem e` minha,so me deram e eu queria saber se poderia usar > os lemas de Kaplansky,por isso enviei a questao!!! > > Adriano. > >> From: "Jose Francisco Guimaraes Costa" <[EMAIL PROTECTED]> >> Reply-To: [EMAIL PROTECTED] >> To: <[EMAIL PROTECTED]> >> Subject: [obm-l] Analise Combinatoria, conceitos militares >> Date: Thu, 6 Jun 2002 10:04:54 -0300 >> >> Para evitar problemas que V poderia ter se estivesse na conferência no >> auditório do IME, duas pequenas correções quanto à parte não >> matemática do >> problema: (1) almirantes, generais e brigadeiros são oficiais >> generais, e >> não oficiais superiores (na marinha os oficiais superiores são os >> capitães >> de corveta, fragata e mar-e-guerra, e no exército e aeronáutica os >> majores, >> tenentes coronéis e coronéis); (2) marinha, exército e aeronáutica são >> "forças" e não "armas" ("armas" - conceito que só se aplica ao >> exército - >> são infantaria, cavalaria e artilharia). >> >> Se é para levar a frescura um degrau acima, sendo o IME uma "OM" >> (Organização Militar), os oficiais generais estariam assentados de >> acordo >> com sua "antiguidade" (hierarquia): o mais "antigo" ao centro e os mais >> "modernos" alternadamente à direita e à esquerda dele. >> >> Para evitar esta v toda, sugiro trocar no enunciado do problema >> "conferência" por "jogo de futebol", "IME" por "Maracanã"; >> "auditório" por >> "geral", "7 oficiais" por "7 torcedores" e "generais, almirantes e >> brigadeiros" por "flamenguistas, fluminenses e vascaínos". >> >> Não sei como V faria para evitar uma p... briga na geral do Maracanã! >> >> JF >> >> PS: considerem isso uma pausa para recreio, tal como nos tempos de >> escola. >> >> - Original Message - >> From: "Adriano Almeida Faustino" <[EMAIL PROTECTED]> >> To: <[EMAIL PROTECTED]> >> Sent: Thursday, June 06, 2002 1:27 AM >> Subject: [obm-l] Analise Combinatoria >> >> >> > estou com duvida nessa questao e queria que alguem me ajudasse >> > >> > Para uma conferencia realizada no auditorio do IME,foram reservados 7 >> > lugares,que serao ocupados por 7 oficiais superiores.Sabendo-se que >> 3 sao >> > generais,2 almirantes e 2,brigadeiros e que estes lugares estao na >> primeira >> > fila,um ao lado do outro,determine de quantos modos podemos >> acomoda-los,sem >> > que haja sentados juntos oficiais de uma mesma arma. >> > []`s >> > Adriano. >> > >> > >> > >> > >> > >> > >> > >> > >> > _ >> > Envie e receba emails com o Hotmail no seu dispositivo móvel: >> > http://mobile.msn.com >> > >> > >> = >> >> > 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]> >> > >> = >> >> > >> >> = >> >> 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]> >> = >> > > > > _ > Chegou o novo MSN Explorer. Instale já. É gratuito: > http://explorer.msn.com.br > > = > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > O administrador desta lista é <[EMAIL PROTECTED]> > = > > = 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]> =
Re: [obm-l] Analise Combinatoria, conceitos militares
Nao me interessa,se nao gostou mude a questao mas que a ideia seja a mesma. A questao nem e` minha,so me deram e eu queria saber se poderia usar os lemas de Kaplansky,por isso enviei a questao!!! Adriano. >From: "Jose Francisco Guimaraes Costa" <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: <[EMAIL PROTECTED]> >Subject: [obm-l] Analise Combinatoria, conceitos militares >Date: Thu, 6 Jun 2002 10:04:54 -0300 > >Para evitar problemas que V poderia ter se estivesse na conferência no >auditório do IME, duas pequenas correções quanto à parte não matemática do >problema: (1) almirantes, generais e brigadeiros são oficiais generais, e >não oficiais superiores (na marinha os oficiais superiores são os capitães >de corveta, fragata e mar-e-guerra, e no exército e aeronáutica os majores, >tenentes coronéis e coronéis); (2) marinha, exército e aeronáutica são >"forças" e não "armas" ("armas" - conceito que só se aplica ao exército - >são infantaria, cavalaria e artilharia). > >Se é para levar a frescura um degrau acima, sendo o IME uma "OM" >(Organização Militar), os oficiais generais estariam assentados de acordo >com sua "antiguidade" (hierarquia): o mais "antigo" ao centro e os mais >"modernos" alternadamente à direita e à esquerda dele. > >Para evitar esta v toda, sugiro trocar no enunciado do problema >"conferência" por "jogo de futebol", "IME" por "Maracanã"; "auditório" por >"geral", "7 oficiais" por "7 torcedores" e "generais, almirantes e >brigadeiros" por "flamenguistas, fluminenses e vascaínos". > >Não sei como V faria para evitar uma p... briga na geral do Maracanã! > >JF > >PS: considerem isso uma pausa para recreio, tal como nos tempos de escola. > >- Original Message - >From: "Adriano Almeida Faustino" <[EMAIL PROTECTED]> >To: <[EMAIL PROTECTED]> >Sent: Thursday, June 06, 2002 1:27 AM >Subject: [obm-l] Analise Combinatoria > > > > estou com duvida nessa questao e queria que alguem me ajudasse > > > > Para uma conferencia realizada no auditorio do IME,foram reservados 7 > > lugares,que serao ocupados por 7 oficiais superiores.Sabendo-se que 3 >sao > > generais,2 almirantes e 2,brigadeiros e que estes lugares estao na >primeira > > fila,um ao lado do outro,determine de quantos modos podemos >acomoda-los,sem > > que haja sentados juntos oficiais de uma mesma arma. > > []`s > > Adriano. > > > > > > > > > > > > > > > > > > _ > > Envie e receba emails com o Hotmail no seu dispositivo móvel: > > http://mobile.msn.com > > > > >= > > 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]> > > >= > > > >= >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]> >= _ Chegou o novo MSN Explorer. Instale já. É gratuito: http://explorer.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =
Re: [obm-l] Analise Combinatoria
E` depois eu saquei a besteira que falei.Mas entao, bastaria ele falar que quer um grupo de tres alunos,que nao tenha alunos designados por numeros consecutivos,ja que onde tem 3 numeros consecutivos, tem 2 ?E se ele falasse uma comissao de 3 alunos,onde nao fazem parte 3 alunos designados por numeros consecutivos,daria na mesma? Por exemplo eu poderia usar Kaplansky aqui Para uma conferencia realizada no auditorio do IME,foram reservados 7 lugares,que serao ocupados por 7 oficiais superiores.Sabendo-se que 3 sao generais,2 almirantes e 2,brigadeiros e que estes lugares estao na primeira fileira,um ao lado do outro,determine de quantos modos podemos acomoda-los,sem que haja sentados juntos oficiais de uma mesma arma. Obrigado. []`s Adriano. >From: Augusto César Morgado <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: [EMAIL PROTECTED] >Subject: Re: [obm-l] Analise Combinatoria >Date: Thu, 30 May 2002 15:40:03 -0300 > >Claro, o que eu fiz foi deduzir localmente o lema de Kaplansky. Mas nao >entendi o final do seu comentario. O que seria dispensavel no enunciado >da questao seria o "tres" e nao o dois. >Morgado > >Adriano Almeida Faustino wrote: > >>O que fez praticamente fez foi o 1ºlema de Kaplansky ( C(n-p+1,p) >>),para p=3 ?E o que adiantou ele falar ``dois` ou tres alunos` ?,o que >>esse `dois` esta influindo? >>[]`s >>Adriano. >> >> >>>From: Augusto Cesar de Oliveira Morgado <[EMAIL PROTECTED]> >>>Reply-To: [EMAIL PROTECTED] >>>To: [EMAIL PROTECTED] >>>Subject: Re: [obm-l] Analise Combinatoria >>>Date: Mon, 27 May 2002 11:10:13 -0300 (EST) >>> >>> >>>Uma solucao mais elementar seria imaginar os alunos 1 2 ... n e >>>marcar com o sinal de + os escolhidos e com o sinal - os não >>>escolhidos. Formaremos uma fila com 3 sinais + e n-3 sinais -, nao >>>podendo haver dois sinais + consecutivos. Para isso, ponha os n-3 >>>sinais - em fila e vejamos de quantos modos podemos enfiar entre eles >>>(ou antes do primeiro ou depois do ultimo) os sinais +. >>>Sao n-2 espaços dos quais devemos escolher 3 e a resposta eh C(n-2,2). >>> >>>Em Mon, 27 May 2002 00:59:54 -0300, Paulo Rodrigues >>><[EMAIL PROTECTED]> disse: >>> >>> > : Considere uma turma com n alunos ,numerados de 1 a n. >>> > : Deseja-se organizar uma comissao de 3 alunos.De quantas maneiras >>>pode ser >>> > : formada esta comissao,de modo que nao facam parte da mesma dois >>>ou tres >>> > : alunosdesignados por numeros consecutivos ? >>> > >>> > Seja C={x, y, z} uma comissão satisfazendo às condições do >>>problema, com >>> > x>>elementos pois >>> > z > y +1 > x+2. C1 é necessariamente um subconjunto de >>>[n-2]={1,2,...,n-2} >>> > e prova-se facilmente que essa função que leva C em C1 é uma >>>bijeção do >>> > conjunto considerado no conjunto dos 3-subconjuntos de [n-2]. >>>Portanto, o >>> > número de subconjuntos C é igual ao número de subconjuntos C1, igual a >>> > binomial(n-2,3) = (n-2)(n-3)(n-4)/6. >>> > >>> > >>> > --- >>> > esta mensagem não contém vírus! >>> > Checked by AVG anti-virus system (http://www.grisoft.com). >>> > Version: 6.0.363 / Virus Database: 201 - Release Date: 21/05/2002 >>> > >>> > >>>= >>> >>> > 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]> >>> > >>>= >>> >>> > >>> > >>> >>>= >>> >>>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]> >>>= >>> >> >> >> >>_ >>Chegou o novo MSN Explorer. Instale já. É gratuito: >>http://explorer.msn.com.br >> >>= >>Instruções para entrar na lista, sair da lista e usar a lista em >>http://www.mat.
Re: [obm-l] Analise Combinatoria
Claro, o que eu fiz foi deduzir localmente o lema de Kaplansky. Mas nao entendi o final do seu comentario. O que seria dispensavel no enunciado da questao seria o "tres" e nao o dois. Morgado Adriano Almeida Faustino wrote: > O que fez praticamente fez foi o 1ºlema de Kaplansky ( C(n-p+1,p) > ),para p=3 ?E o que adiantou ele falar ``dois` ou tres alunos` ?,o que > esse `dois` esta influindo? > []`s > Adriano. > > >> From: Augusto Cesar de Oliveira Morgado <[EMAIL PROTECTED]> >> Reply-To: [EMAIL PROTECTED] >> To: [EMAIL PROTECTED] >> Subject: Re: [obm-l] Analise Combinatoria >> Date: Mon, 27 May 2002 11:10:13 -0300 (EST) >> >> >> Uma solucao mais elementar seria imaginar os alunos 1 2 ... n e >> marcar com o sinal de + os escolhidos e com o sinal - os não >> escolhidos. Formaremos uma fila com 3 sinais + e n-3 sinais -, nao >> podendo haver dois sinais + consecutivos. Para isso, ponha os n-3 >> sinais - em fila e vejamos de quantos modos podemos enfiar entre eles >> (ou antes do primeiro ou depois do ultimo) os sinais +. >> Sao n-2 espaços dos quais devemos escolher 3 e a resposta eh C(n-2,2). >> >> Em Mon, 27 May 2002 00:59:54 -0300, Paulo Rodrigues >> <[EMAIL PROTECTED]> disse: >> >> > : Considere uma turma com n alunos ,numerados de 1 a n. >> > : Deseja-se organizar uma comissao de 3 alunos.De quantas maneiras >> pode ser >> > : formada esta comissao,de modo que nao facam parte da mesma dois >> ou tres >> > : alunosdesignados por numeros consecutivos ? >> > >> > Seja C={x, y, z} uma comissão satisfazendo às condições do >> problema, com >> > x> elementos pois >> > z > y +1 > x+2. C1 é necessariamente um subconjunto de >> [n-2]={1,2,...,n-2} >> > e prova-se facilmente que essa função que leva C em C1 é uma >> bijeção do >> > conjunto considerado no conjunto dos 3-subconjuntos de [n-2]. >> Portanto, o >> > número de subconjuntos C é igual ao número de subconjuntos C1, igual a >> > binomial(n-2,3) = (n-2)(n-3)(n-4)/6. >> > >> > >> > --- >> > esta mensagem não contém vírus! >> > Checked by AVG anti-virus system (http://www.grisoft.com). >> > Version: 6.0.363 / Virus Database: 201 - Release Date: 21/05/2002 >> > >> > >> = >> >> > 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]> >> > >> = >> >> > >> > >> >> = >> >> 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]> >> = >> > > > > _ > Chegou o novo MSN Explorer. Instale já. É gratuito: > http://explorer.msn.com.br > > = > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > O administrador desta lista é <[EMAIL PROTECTED]> > = > > = 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]> =
Re: [obm-l] Analise Combinatoria
O que fez praticamente fez foi o 1ºlema de Kaplansky ( C(n-p+1,p) ),para p=3 ?E o que adiantou ele falar ``dois` ou tres alunos` ?,o que esse `dois` esta influindo? []`s Adriano. >From: Augusto Cesar de Oliveira Morgado <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: [EMAIL PROTECTED] >Subject: Re: [obm-l] Analise Combinatoria >Date: Mon, 27 May 2002 11:10:13 -0300 (EST) > > >Uma solucao mais elementar seria imaginar os alunos 1 2 ... n e marcar com >o sinal de + os escolhidos e com o sinal - os não escolhidos. Formaremos >uma fila com 3 sinais + e n-3 sinais -, nao podendo haver dois sinais + >consecutivos. Para isso, ponha os n-3 sinais - em fila e vejamos de quantos >modos podemos enfiar entre eles (ou antes do primeiro ou depois do ultimo) >os sinais +. >Sao n-2 espaços dos quais devemos escolher 3 e a resposta eh C(n-2,2). > >Em Mon, 27 May 2002 00:59:54 -0300, Paulo Rodrigues <[EMAIL PROTECTED]> >disse: > > > : Considere uma turma com n alunos ,numerados de 1 a n. > > : Deseja-se organizar uma comissao de 3 alunos.De quantas maneiras pode >ser > > : formada esta comissao,de modo que nao facam parte da mesma dois ou >tres > > : alunosdesignados por numeros consecutivos ? > > > > Seja C={x, y, z} uma comissão satisfazendo às condições do problema, com > > xpois > > z > y +1 > x+2. C1 é necessariamente um subconjunto de >[n-2]={1,2,...,n-2} > > e prova-se facilmente que essa função que leva C em C1 é uma bijeção do > > conjunto considerado no conjunto dos 3-subconjuntos de [n-2]. Portanto, >o > > número de subconjuntos C é igual ao número de subconjuntos C1, igual a > > binomial(n-2,3) = (n-2)(n-3)(n-4)/6. > > > > > > --- > > esta mensagem não contém vírus! > > Checked by AVG anti-virus system (http://www.grisoft.com). > > Version: 6.0.363 / Virus Database: 201 - Release Date: 21/05/2002 > > > > >= > > 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]> > > >= > > > > > >= >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]> >= _ Chegou o novo MSN Explorer. Instale já. É gratuito: http://explorer.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =
Re: [obm-l] Analise Combinatoria (Ops ... Cochilo)
Ola Pessoal, Corrigindo um cochilo. Na segunda solucao e necessario considerar uma equacao a quatro variaveis e nao a duas : X+Y+Z+W=N-3 Em geral, pensa-se em N-3 como o numero de unidades que devem ser separadas por tres barras. Exemplo : X+Y+Z+W=12 UUU|UUU||UU->solucao : (3,3,4,2) U|U|U|U->solucao : (1,5,1,5) E assim sucessivamente ... O que eu estou propondo e que se olhe as barras como alunos escolhidos : UUU|UUU||UU->alunos escolhidos : {4,8,13} U|U|U|U->alunos escolhidos : {2,8,10} Olhando as coisas assim ( eu sei que e um olhar estranho e nao convencional, mas entenda que funciona ) a toda solucao da equacao "sem zero" corresponde uma escolha valida dos alunos. Basta agora considerar separadamente as solucoes da forma : IUU..., UUU..U| e IUU...UU| Um abraco Paulo Santa Rita 2,1544,270502 >From: "Paulo Santa Rita" <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: [EMAIL PROTECTED] >Subject: Re: [obm-l] Analise Combinatoria >Date: Mon, 27 May 2002 18:26:37 + > >Ola Pessoal, > >Em muitos problemas de Analise Combinatoria, como no caso abaixo, o >enunciado faz algumas restricoes. Um caminho natural e que, quase sempre, >conduz a uma solucao satisfatoria e considerar as restricoes >e conta-las separadamente ... > >O total de comissoes com 3 alunos e : BINOM(N,3). > >Desse total temos que retirar as restricoes. Vamos conta-las : > >1) tres numeros consecutivos : >{1,2,3},{2,3,4}, ..., {N-2,N-1,N} >Evidentemente, N-2 casos >SUBTOTAL1 : (N-2) casos > >2) dois numeros consecutivos : >{1,2) + Um escolhido entre {4,5,...,N} = N-3 casos >{N-1,N} + Um escolhido entre {1,2,...,N-3) = N-3 casos >SUBTOTAL2 : 2(N-3) casos > >Pares : {2,3},{3,4},...,{N-2,N-1} -> (N-3) pares >Para cada um desses pares podemos escolher um terceiro numero de N-4 >maneiras. Logo : (N-3)(N-4) pares >SUBTOTAL3 : (N-3)(N-4) > >CALCULO FINAL : > >T=BINOM(N,3) - [ SUBTOTAL1 + SUBTOTAL2 + SUBTOTAL3 ] >T=BINOM(N,3) - [(N-2)^2] >T=[N(N-1)(N-2)/6] - [(N-2)^2]=((N-2)(N-3)(N-4))/6 > > >UMA OUTRA FORMA DE FAZER : > >Seja a equacao : X+Y+Z=N. Sem duvida que voce sabe calcular o numero de >solucoes inteiras nao negativas desta equacao, pois este problema basico e >abordado em todo livro de Analise Combinatoria. > >Para obter as "solucoes positivas", faca : > >X=X'+1 ; Y=Y'+1 e Z=Z'+1 > >E resolva : X'+Y'+Z'=N-3. Se voce considerar que uma solucao de uma tal >equacao e apenas uma forma de separa N-3 esferas por duas barras, a cada >colucao inteira positiva corresponde uma forma de escolher duas pessoas nao >consecutivas. > >Exemplo ( vou considerar |=Barra, A=unidade e N-3=5 ) > >A solucao (1,2,2) correspode a A | AA | AA isto significaria escolher a >segundo e o 5 aluno; AA|AA|A=(2,2,1) equivale a escolher o 3 e o 6 aluno; >A|AAA|A=(1,3,1) equivale a escolher o 2 e o 6 aluno e assim sucessivamente. >Ha, portanto, uma funcao entre as solucoes inteiras positivas da equacao e >as escolhas que voce pode fazer. E so pensar com calma que a solucao sai >por >aqui facil. Os detalhes voce completa > > >UMA OUTRA SOLUCAO ? : > >Procure se informar sobre os lemas de Kaplanski. No livro de Analise >Combinatoria do Prof Morgado ha tudo isso e muito mais. Este livro, em >minha >opiniao, e o que ha de melhor no Brasil nesta area e vai te dar uma base >para voce ser bem sucedido em qualquer vestibular que exija tal tema. > >Um abraco >Paulo Santa Rita >2,1521,270502 > >>Considere uma turma com n alunos ,numerados de 1 a n. >>Deseja-se organizar uma comissao de 3 alunos.De quantas maneiras pode ser >>formada esta comissao,de modo que nao facam parte da mesma dois ou tres >>alunosdesignados por numeros consecutivos ? > > >_ >Envie e receba emails com o Hotmail no seu dispositivo móvel: >http://mobile.msn.com > >= >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]> >= _ Converse com amigos on-line, conheça o MSN Messenger: http://messenger.msn.com = 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]> =
Re: [obm-l] Analise Combinatoria
Ola Pessoal, Em muitos problemas de Analise Combinatoria, como no caso abaixo, o enunciado faz algumas restricoes. Um caminho natural e que, quase sempre, conduz a uma solucao satisfatoria e considerar as restricoes e conta-las separadamente ... O total de comissoes com 3 alunos e : BINOM(N,3). Desse total temos que retirar as restricoes. Vamos conta-las : 1) tres numeros consecutivos : {1,2,3},{2,3,4}, ..., {N-2,N-1,N} Evidentemente, N-2 casos SUBTOTAL1 : (N-2) casos 2) dois numeros consecutivos : {1,2) + Um escolhido entre {4,5,...,N} = N-3 casos {N-1,N} + Um escolhido entre {1,2,...,N-3) = N-3 casos SUBTOTAL2 : 2(N-3) casos Pares : {2,3},{3,4},...,{N-2,N-1} -> (N-3) pares Para cada um desses pares podemos escolher um terceiro numero de N-4 maneiras. Logo : (N-3)(N-4) pares SUBTOTAL3 : (N-3)(N-4) CALCULO FINAL : T=BINOM(N,3) - [ SUBTOTAL1 + SUBTOTAL2 + SUBTOTAL3 ] T=BINOM(N,3) - [(N-2)^2] T=[N(N-1)(N-2)/6] - [(N-2)^2]=((N-2)(N-3)(N-4))/6 UMA OUTRA FORMA DE FAZER : Seja a equacao : X+Y+Z=N. Sem duvida que voce sabe calcular o numero de solucoes inteiras nao negativas desta equacao, pois este problema basico e abordado em todo livro de Analise Combinatoria. Para obter as "solucoes positivas", faca : X=X'+1 ; Y=Y'+1 e Z=Z'+1 E resolva : X'+Y'+Z'=N-3. Se voce considerar que uma solucao de uma tal equacao e apenas uma forma de separa N-3 esferas por duas barras, a cada colucao inteira positiva corresponde uma forma de escolher duas pessoas nao consecutivas. Exemplo ( vou considerar |=Barra, A=unidade e N-3=5 ) A solucao (1,2,2) correspode a A | AA | AA isto significaria escolher a segundo e o 5 aluno; AA|AA|A=(2,2,1) equivale a escolher o 3 e o 6 aluno; A|AAA|A=(1,3,1) equivale a escolher o 2 e o 6 aluno e assim sucessivamente. Ha, portanto, uma funcao entre as solucoes inteiras positivas da equacao e as escolhas que voce pode fazer. E so pensar com calma que a solucao sai por aqui facil. Os detalhes voce completa UMA OUTRA SOLUCAO ? : Procure se informar sobre os lemas de Kaplanski. No livro de Analise Combinatoria do Prof Morgado ha tudo isso e muito mais. Este livro, em minha opiniao, e o que ha de melhor no Brasil nesta area e vai te dar uma base para voce ser bem sucedido em qualquer vestibular que exija tal tema. Um abraco Paulo Santa Rita 2,1521,270502 >Considere uma turma com n alunos ,numerados de 1 a n. >Deseja-se organizar uma comissao de 3 alunos.De quantas maneiras pode ser >formada esta comissao,de modo que nao facam parte da mesma dois ou tres >alunosdesignados por numeros consecutivos ? _ Envie e receba emails com o Hotmail no seu dispositivo móvel: http://mobile.msn.com = 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]> =
Re: [obm-l] Analise Combinatoria
Uma solucao mais elementar seria imaginar os alunos 1 2 ... n e marcar com o sinal de + os escolhidos e com o sinal - os não escolhidos. Formaremos uma fila com 3 sinais + e n-3 sinais -, nao podendo haver dois sinais + consecutivos. Para isso, ponha os n-3 sinais - em fila e vejamos de quantos modos podemos enfiar entre eles (ou antes do primeiro ou depois do ultimo) os sinais +. Sao n-2 espaços dos quais devemos escolher 3 e a resposta eh C(n-2,2). Em Mon, 27 May 2002 00:59:54 -0300, Paulo Rodrigues <[EMAIL PROTECTED]> disse: > : Considere uma turma com n alunos ,numerados de 1 a n. > : Deseja-se organizar uma comissao de 3 alunos.De quantas maneiras pode ser > : formada esta comissao,de modo que nao facam parte da mesma dois ou tres > : alunosdesignados por numeros consecutivos ? > > Seja C={x, y, z} uma comissão satisfazendo às condições do problema, com > x z > y +1 > x+2. C1 é necessariamente um subconjunto de [n-2]={1,2,...,n-2} > e prova-se facilmente que essa função que leva C em C1 é uma bijeção do > conjunto considerado no conjunto dos 3-subconjuntos de [n-2]. Portanto, o > número de subconjuntos C é igual ao número de subconjuntos C1, igual a > binomial(n-2,3) = (n-2)(n-3)(n-4)/6. > > > --- > esta mensagem não contém vírus! > Checked by AVG anti-virus system (http://www.grisoft.com). > Version: 6.0.363 / Virus Database: 201 - Release Date: 21/05/2002 > > = > 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]> > = > > = 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]> =
Re: [obm-l] Analise Combinatoria
Uma solucao mais elementar seria imaginar os alunos 1 2 ... n e marcar com o sinal de + os escolhidos e com o sinal - os não escolhidos. Formaremos uma fila com 3 sinais + e n-3 sinais -, nao podendo haver dois sinais + consecutivos. Para isso, ponha os n-3 sinais - em fila e vejamos de quantos modos podemos enfiar entre eles (ou antes do primeiro ou depois do ultimo) os sinais +. Sao n-2 espaços dos quais devemos escolher 3 e a resposta eh C(n-2,2). Em Mon, 27 May 2002 00:59:54 -0300, Paulo Rodrigues <[EMAIL PROTECTED]> disse: > : Considere uma turma com n alunos ,numerados de 1 a n. > : Deseja-se organizar uma comissao de 3 alunos.De quantas maneiras pode ser > : formada esta comissao,de modo que nao facam parte da mesma dois ou tres > : alunosdesignados por numeros consecutivos ? > > Seja C={x, y, z} uma comissão satisfazendo às condições do problema, com > x z > y +1 > x+2. C1 é necessariamente um subconjunto de [n-2]={1,2,...,n-2} > e prova-se facilmente que essa função que leva C em C1 é uma bijeção do > conjunto considerado no conjunto dos 3-subconjuntos de [n-2]. Portanto, o > número de subconjuntos C é igual ao número de subconjuntos C1, igual a > binomial(n-2,3) = (n-2)(n-3)(n-4)/6. > > > --- > esta mensagem não contém vírus! > Checked by AVG anti-virus system (http://www.grisoft.com). > Version: 6.0.363 / Virus Database: 201 - Release Date: 21/05/2002 > > = > 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]> > = > > = 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]> =
Re: [obm-l] Analise Combinatoria
: Considere uma turma com n alunos ,numerados de 1 a n. : Deseja-se organizar uma comissao de 3 alunos.De quantas maneiras pode ser : formada esta comissao,de modo que nao facam parte da mesma dois ou tres : alunosdesignados por numeros consecutivos ? Seja C={x, y, z} uma comissão satisfazendo às condições do problema, com x y +1 > x+2. C1 é necessariamente um subconjunto de [n-2]={1,2,...,n-2} e prova-se facilmente que essa função que leva C em C1 é uma bijeção do conjunto considerado no conjunto dos 3-subconjuntos de [n-2]. Portanto, o número de subconjuntos C é igual ao número de subconjuntos C1, igual a binomial(n-2,3) = (n-2)(n-3)(n-4)/6. --- esta mensagem não contém vírus! Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.363 / Virus Database: 201 - Release Date: 21/05/2002 = 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]> =
Re: [obm-l] Analise Combinatoria
mande as respostas deles pra mim resolver please... __ Quer ter seu próprio endereço na Internet? Garanta já o seu e ainda ganhe cinco e-mails personalizados. DomíniosBOL - http://dominios.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]> =
Re:[obm-l] Analise Combinatoria
A resposta não seria: (n-1)/6*(n^2-8n+6)? Considere uma turma com n alunos ,numerados de 1 a n. > Deseja-se organizar uma comissao de 3 alunos.De quantas maneiras pode ser > formada esta comissao,de modo que nao facam parte da mesma dois ou tres > alunosdesignados por numeros consecutivos ? > > _ > Una-se ao maior serviço de email do mundo: o MSN Hotmail. > http://www.hotmail.com > > = > 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]> > = > __ Quer ter seu próprio endereço na Internet? Garanta já o seu e ainda ganhe cinco e-mails personalizados. DomíniosBOL - http://dominios.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]> =
Re: [obm-l] Analise Combinatoria
Putz, Adriano hehe, tu deve ter abrido esse mail lokinho lokinho crente crente que alguem teria resolvido seu problema, né?, pois é..eu não vim para te ajudar, e sim para te complicar! hehe , ja que tu gosta desse tipo de problemas toma mais 4 ai pro c!: Com os algarismos 1, 2, 3, 4, 5 e 6 formam-se números naturais de 6 algarismos distintos. Sabendo-se que neles não aparecem juntos, dois algarismos pares nem dois algarismos ímpares, calcular o número total de naturais assim formados? Quantos números pares, de cinco algarismos, podem ser formados sem repetir algarismos? Seis pessoas, -A, B, C, D e F - ficam em pé uma ao lado da outra para uma fotografia. Se A e B se recusam a ficar lado a lado e C e D insistem em aparecer uma ao lado da outra, determinar o número de possibilidades distintas para as seis pessoas se disporem? Para um campeonato de volêi foram convocados 10 jogadores: 4 mineiros e 6 cariocas, sendo que 3 dos mineiros são juvenis. Lembrando que um time em quadra tem 6 jogadores, determinar quantos são os times possíveis contendo, pelo menos, 1 carioca e 1 mineiro, sabendo que no time não pode haver mais do que 1 juvenil? Junior-Rio=) = 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]> =