Re: [obm-l] Prova combinatoria
O que o Bernardo disse! Usando a ideia dele, cheguei em: "Você tem um alfabeto de apenas 3 letras -- digamos, A, B e C -- e quer montar uma palavra com n símbolos (a ordem importa, repetições obviamente são aceitas). Por exemplo, uma palavra válida com n=6 é ABBACA (eu sem querer escrevi outra parecida, mas depois li o que eu tinha escrito e era ligeiramente ofensivo... :) :) :)). Quantas destas palavras têm exatamente k consoantes?" Abraço, Ralph 2012/6/6 Bernardo Freitas Paulo da Costa > 2012/6/6 marcone augusto araújo borges : > > notação:(n,p)-->número binomial de numerador n e denominador p > > > > 1 + 2(n,1) + 4(n,2) + ...[2^(n-1)](n,n-1)+ [2 ^n](n,n) = 3^n > > Se desenvolvermos (x + 2y)^n e substituirmos x por 1 e y por > 1,encontraremos > > a expressão do lado esquerdo,que será igual a (1+ 2)^n > Veja que isso é também a expansão de (x + y)^n com x=1 e y=2. > > > O exercício pede para encontrar uma prova combinatória. > Uhm, pra tentar uma prova combinatória, eu faria *antes de mais nada* > uma prova combinatória da mesma fórmula só que com x=1 e y=1. Talvez > você até já conheça uma. Daí tente generalizar! > > > Já pensei,pensei e não saiu. > > Abraços, > -- > Bernardo Freitas Paulo da Costa > > = > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > = >
RE: [obm-l] Prova combinatoria
Estou vendo como seria essa generalização,e acho que 3^n é o numero de duplas ordenadas tipo (A,B),com A e B subconjuntos disjuntos de um conjunto M de n elementos. Não sei se me expressei corretamente,mas eu estava tentando uma contagem por ai. > Date: Wed, 6 Jun 2012 20:57:17 +0200 > Subject: Re: [obm-l] Prova combinatoria > From: bernardo...@gmail.com > To: obm-l@mat.puc-rio.br > > 2012/6/6 marcone augusto araújo borges : > > notação:(n,p)-->número binomial de numerador n e denominador p > > > > 1 + 2(n,1) + 4(n,2) + ...[2^(n-1)](n,n-1)+ [2 ^n](n,n) = 3^n > > Se desenvolvermos (x + 2y)^n e substituirmos x por 1 e y por 1,encontraremos > > a expressão do lado esquerdo,que será igual a (1+ 2)^n > Veja que isso é também a expansão de (x + y)^n com x=1 e y=2. > > > O exercício pede para encontrar uma prova combinatória. > Uhm, pra tentar uma prova combinatória, eu faria *antes de mais nada* > uma prova combinatória da mesma fórmula só que com x=1 e y=1. Talvez > você até já conheça uma. Daí tente generalizar! > > > Já pensei,pensei e não saiu. > > Abraços, > -- > Bernardo Freitas Paulo da Costa > > = > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > =
Re: [obm-l] Prova combinatoria
2012/6/6 marcone augusto araújo borges : > notação:(n,p)-->número binomial de numerador n e denominador p > > 1 + 2(n,1) + 4(n,2) + ...[2^(n-1)](n,n-1)+ [2 ^n](n,n) = 3^n > Se desenvolvermos (x + 2y)^n e substituirmos x por 1 e y por 1,encontraremos > a expressão do lado esquerdo,que será igual a (1+ 2)^n Veja que isso é também a expansão de (x + y)^n com x=1 e y=2. > O exercício pede para encontrar uma prova combinatória. Uhm, pra tentar uma prova combinatória, eu faria *antes de mais nada* uma prova combinatória da mesma fórmula só que com x=1 e y=1. Talvez você até já conheça uma. Daí tente generalizar! > Já pensei,pensei e não saiu. Abraços, -- Bernardo Freitas Paulo da Costa = 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] Prova combinatoria
notação:(n,p)-->número binomial de numerador n e denominador p 1 + 2(n,1) + 4(n,2) + ...[2^(n-1)](n,n-1)+ [2 ^n](n,n) = 3^n Se desenvolvermos (x + 2y)^n e substituirmos x por 1 e y por 1,encontraremos a expressão do lado esquerdo,que será igual a (1+ 2)^n O exercício pede para encontrar uma prova combinatória. Já pensei,pensei e não saiu.
[obm-l] FW: [obm-l] Re: [obm-l] Questão de combinatoria
From: marconeborge...@hotmail.com To: obm-l@mat.puc-rio.br Subject: RE: [obm-l] Re: [obm-l] Questão de combinatoria Date: Wed, 6 Jun 2012 13:37:56 + Beleza!Eh isso mesmo. Eu tinha pensado em escolher duas linhas e duas colunas,para formar um retângulo. Date: Wed, 6 Jun 2012 00:58:24 -0300 Subject: [obm-l] Re: [obm-l] Questão de combinatoria From: ralp...@gmail.com To: obm-l@mat.puc-rio.br Escolher um retangulo significa escolher o canto esquerdo superior e o canto direito inferior. Como o canto esquerdo superior tem que ficar a "Noroeste" desta celula, sao pq opcoes para ele. Como o canto direito inferior tem que ficar a "Sudeste" dela, sao (m-p+1)(n-q+1) opcoes para ele (note que isto inclui a propria celula como possibilidade). Total: p(m+1-p)q(n+1-q) opcoes. Eh isso? Abraco, Ralph 2012/6/5 marcone augusto araújo borges Em uma tabela com m linhas e n colunas,a célula da intersecção da p-ésima linha com a q-ésima coluna está marcada. Quantos retângulos formados pelas células da tabela contêm a celula marcada?
[obm-l] RE: [obm-l] Re: [obm-l] Questão de combinatoria
Beleza!Eh isso mesmo. Eu tinha pensado em escolher duas linhas e duas colunas,para formar um retângulo. Date: Wed, 6 Jun 2012 00:58:24 -0300 Subject: [obm-l] Re: [obm-l] Questão de combinatoria From: ralp...@gmail.com To: obm-l@mat.puc-rio.br Escolher um retangulo significa escolher o canto esquerdo superior e o canto direito inferior. Como o canto esquerdo superior tem que ficar a "Noroeste" desta celula, sao pq opcoes para ele. Como o canto direito inferior tem que ficar a "Sudeste" dela, sao (m-p+1)(n-q+1) opcoes para ele (note que isto inclui a propria celula como possibilidade). Total: p(m+1-p)q(n+1-q) opcoes. Eh isso? Abraco, Ralph 2012/6/5 marcone augusto araújo borges Em uma tabela com m linhas e n colunas,a célula da intersecção da p-ésima linha com a q-ésima coluna está marcada. Quantos retângulos formados pelas células da tabela contêm a celula marcada?
Re: [obm-l] Problema de grafos
valeu demais!! 2012/6/5 Ralph Teixeira > Versao relampago: > casa-dos-pombos, 68,68,68,69,69,69,70,70,70,...,100,100,100,101,101,101, > contradicao. > > Versao explicada: > Ha 101-67=34 numeros entre 68 e 101 (que sao os possiveis numeros de > amigos) de cada fulano. > Seja xi o numero de estudantes com i amigos (onde i=68,69,...,101). Note > que sao 34 numeros xi, cuja soma eh 102. Queremos provar que algum deles eh > maior ou igual a 4, certo? > Entao suponha por contradicao que todos eles sao menores ou iguais a 3. > Entao a soma eh no maximo 34x3=102, o que soh serah atingido se TODOS forem > iguais a 3. Entao chegamos aa conclusao de que o unico jeito do nosso > teorema furar seria se houvesse 3 alunos com 68 amigos, outros 3 com 69 > amigos, e assim por diante, e 3 com 101 amigos, exatamente. > > Agora seja yk o numero de amigos do fulano k (k=1,2,3,...,102) -- ou seja, > a lista dos numeros yk seria aquela lista lah em cima. A soma dos yk tem > que ser par (afinal, quando voce soma os yk's, voce estah contando o > "numero de amizades", soh que em dobro, porque cada amizade eh contada duas > vezes -- estamos fazendo a hipotese aqui de que, se A eh amigo de B, entao > B eh amigo de A). Como 68+68+68+69+69+69+...+101+101+101 = 17x169 eh impar, > esta nao eh uma configuracao possivel. Acabou. > > Abraco, >Ralph > > 2012/6/5 Mauricio de Araujo > >> Amigos, gostaria de uma luz para fazer o problema abaixo: >> >> Cada um dos 102 estudantes ´e amigo de pelo menos 68 outros alunos. Prove >> que existem quatro >> estudantes com o mesmo n´umero de amigos. >> >> -- >> -- >> Abraços >> oɾnɐɹɐ ǝp oıɔıɹnɐɯ >> *momentos excepcionais pedem ações excepcionais* >> >> > -- -- Abraços oɾnɐɹɐ ǝp oıɔıɹnɐɯ *momentos excepcionais pedem ações excepcionais*