Re: RES: [obm-l] Problema Subconjuntos
Olá Artur!!! O 1° lema de Kaplansky diz que o número de p-subconjuntos (isto é, um subconjunto com p elementos) de {1,2,...,n} nos quais não há números consecutivos é: f (n,p) = Combinação(n-p+1,p). Para maiores detalhes consulte Análise Combinatória e Probabilidade de Morgado, Pitombeira, P.C.Pinto Carvalho e Pedro Fernandez, da coleção do Professor de Matemática. Espero ter ajudado,um grande abraço, Poncio - Original Message - From: Artur Costa Steiner <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Wednesday, July 21, 2004 8:14 PM Subject: Re: RES: [obm-l] Problema Subconjuntos > >C(n-2;3). Basta usar o primeiro lema de Kaplansky. > > Eu nunca ouvi falar deste lema (ignorancia minha). Alguem poderia > enuncia-lo? > Obrigado. > Artur > > > OPEN Internet > @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ > > > = > 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: RES: [obm-l] Problema Subconjuntos
achei isso no arquivo da lista: Kaplansky. Primeiro lema: O número de subconjuntos de tamanho p do conjunto {1, 2,..., n} no qual nao figuram numeros consecutivos eh C(n-p+1, p) Segundo lema: Igual ao anterior, mas considerando 1 e n como consecutivos. O numero de subconjuntos eh [n/(n-p)]*C(n-p, p). --- Artur Costa Steiner <[EMAIL PROTECTED]> escreveu: > >C(n-2;3). Basta usar o primeiro lema de Kaplansky. > > Eu nunca ouvi falar deste lema (ignorancia minha). > Alguem poderia > enuncia-lo? > Obrigado. > Artur ___ Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis! http://br.info.mail.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 =
Re: RES: [obm-l] Problema Subconjuntos
>C(n-2;3). Basta usar o primeiro lema de Kaplansky. Eu nunca ouvi falar deste lema (ignorancia minha). Alguem poderia enuncia-lo? Obrigado. Artur OPEN Internet @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = 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] Problema Subconjuntos. Correção
Favor esquecer a bobagem abaixo. Morgado -- Original Message --- From: "Augusto Cesar de Oliveira Morgado" <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] Sent: Wed, 21 Jul 2004 02:51:09 -0200 Subject: Re: RES: [obm-l] Problema Subconjuntos > C(n-2;3). Basta usar o primeiro lema de Kaplansky. > > > -- Original Message --- > From: "David M. Cardoso" <[EMAIL PROTECTED]> > To: <[EMAIL PROTECTED]> > Sent: Tue, 20 Jul 2004 20:57:24 -0300 > Subject: RES: [obm-l] Problema Subconjuntos > > > Cara, muito obrigado.. > > Sendo que ta dando trabalho pra eu entender algumas coisas, > > como "teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2".. > > hora eu penso que entendi, hora eu não entendo mais e fico tentando lembrar > > pq eu fico entendido antes, talvez seja o nervosismo, talvez seja apenas > > porque o raciocinio eh complicado demais pra mim.. > > > > Outra duvida que tenho é se é possível transformar a recorrência num > > "polinomiozinho" em função de n ou se uma resposta desse tipo já esta > > completa o suficiente.. > > > > []'s > > David > > > > > -Mensagem original- > > > De: [EMAIL PROTECTED] > > > [mailto:[EMAIL PROTECTED] Em nome de Helder Suzuki > > > Enviada em: terça-feira, 20 de julho de 2004 19:30 > > > Para: [EMAIL PROTECTED] > > > Assunto: Re: [obm-l] Problema Subconjuntos > > > > > > vamos ver, seguindo a dica de usar recorrencia > > > > > > se T[n] for igual ao numero de subconjuntos do conjunto {1, > > > 2, ..., n} que nao contem 3 inteiros consecutivos. > > > temos que: > > > T[0] = 1 > > > {} > > > > > > T[1] = 2 > > > {} e {1} > > > > > > T[2] = 4 > > > {}, {1}, > > > {2} e {1, 2} > > > > > > T[3] = 7 > > > {}, {1}, {2}, {1, 2}, > > > {3}, {1, 3}, {2, 3} > > > > > > T[4] = 13 > > > {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {4}, {1, 4}, {2, > > > 4}, {3, 4}, {1, 2, 4}, {1, 3, 4} > > > > > > bom, suponha que sabemos o valor de T[n-1], T[n-2], ..., > > > T[1]; como podemos achar T[n] em funcao de T[n-1]? humm... > > > considere todos subconjuntos de {1, 2, 3, 4, ..., n-1} que > > > satisfazem a condicao do enunciado. > > > se adicionarmos um elemento n, em quais desses subconjuntos o > > > n pode entrar e quais ele nao pode(para manter a condicao do > > > enunciado)? > > > se n nao pode entrar em X subconjuntos, temos que T[n] = > > > T[n-1] + T[n-1] - X T[n] = 2*T[n-1] - X mas X eh o numero de > > > subconjuntos que tem os elementos > > > n-1 e n-2. > > > > > > imagine que temos os subconjnutos de {1, 2, ..., n-3} e > > > queremos adicionar os elementos n-1 e n-2 a esses > > > subconjuntos ao mesmo tempo, nesse caso só nao poderemos > > > adicionar n-1 e n-2 aos subconjuntos que tem o elemento n-3, > > > entao teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2: > > > X = T[n-3] - T[n-4] > > > > > > entao nossa recorrencia fica: > > > T[n] = 2*T[n-1] - T[n-3] + T[n-4] > > > > > > []'s, > > > Helder > > > > > > --- "David M. Cardoso" <[EMAIL PROTECTED]> > > > escreveu: > > > > > > > > > Olá, > > > > > > > > Alguem pode me ajudar? Não consegui resolver o seguinte problema: > > > > > > > > "Quantos subconjuntos o conjunto {1,2,3,...,n} tais que não contêm > > > > três inteiros consecutivos?" > > > > > > > > A dica dada na questão é: "Encontre uma recorrência." > > > Porém, qualquer > > > > solução (sem/com recorrência) vai ajudar. > > > > > > > > []'s > > > > David > > > > > > > > > > > > > > > > > > ___ > > > Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis! > > > http://br.info.mail.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 > > > == > > > === > > > > > > > = > > 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 > > = > --- End of Original Message --- > > = > 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 > = --- End of Original Message --- = 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: RES: [obm-l] Problema Subconjuntos
Eh, eu fiz uma confusao ali imagine que temos os subconjnutos de {1, 2, ..., n-3} e queremos adicionar os elementos n-1 e n-2 a esses subconjuntos ao mesmo tempo, nesse caso só nao poderemos adicionar n-1 e n-2 aos subconjuntos que tem o elemento n-3, entao teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2: X = T[n-3] - T[n-4] T[n-3] - T[n-4] eh o numero de subconjuntos que tem o elemento n-3. podemos adicionar n-1 e n-2 a todos os outros subconjuntos, entao podemos adicionar n-1 e n-2 a T[n-3] - (T[n-3] - T[n-4]) = T[n-4] entao X = T[n-4] e T[n] = 2*T[n-1] - T[n-4] --- "David M. Cardoso" <[EMAIL PROTECTED]> escreveu: > > Cara, muito obrigado.. > Sendo que ta dando trabalho pra eu entender algumas > coisas, > como "teremos T[n-3] - T[n-4] subconjuntos com os > elementos n-1 e n-2".. > hora eu penso que entendi, hora eu não entendo mais > e fico tentando lembrar > pq eu fico entendido antes, talvez seja o > nervosismo, talvez seja apenas > porque o raciocinio eh complicado demais pra mim.. > > Outra duvida que tenho é se é possível transformar a > recorrência num > "polinomiozinho" em função de n ou se uma resposta > desse tipo já esta > completa o suficiente.. > > []'s > David > > > -Mensagem original- > > De: [EMAIL PROTECTED] > > [mailto:[EMAIL PROTECTED] Em nome de > Helder Suzuki > > Enviada em: terça-feira, 20 de julho de 2004 19:30 > > Para: [EMAIL PROTECTED] > > Assunto: Re: [obm-l] Problema Subconjuntos > > > > vamos ver, seguindo a dica de usar recorrencia > > > > se T[n] for igual ao numero de subconjuntos do > conjunto {1, > > 2, ..., n} que nao contem 3 inteiros consecutivos. > > temos que: > > T[0] = 1 > > {} > > > > T[1] = 2 > > {} e {1} > > > > T[2] = 4 > > {}, {1}, > > {2} e {1, 2} > > > > T[3] = 7 > > {}, {1}, {2}, {1, 2}, > > {3}, {1, 3}, {2, 3} > > > > T[4] = 13 > > {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {4}, > {1, 4}, {2, > > 4}, {3, 4}, {1, 2, 4}, {1, 3, 4} > > > > bom, suponha que sabemos o valor de T[n-1], > T[n-2], ..., > > T[1]; como podemos achar T[n] em funcao de T[n-1]? > humm... > > considere todos subconjuntos de {1, 2, 3, 4, ..., > n-1} que > > satisfazem a condicao do enunciado. > > se adicionarmos um elemento n, em quais desses > subconjuntos o > > n pode entrar e quais ele nao pode(para manter a > condicao do > > enunciado)? > > se n nao pode entrar em X subconjuntos, temos que > T[n] = > > T[n-1] + T[n-1] - X T[n] = 2*T[n-1] - X mas X eh o > numero de > > subconjuntos que tem os elementos > > n-1 e n-2. > > > > imagine que temos os subconjnutos de {1, 2, ..., > n-3} e > > queremos adicionar os elementos n-1 e n-2 a esses > > subconjuntos ao mesmo tempo, nesse caso só nao > poderemos > > adicionar n-1 e n-2 aos subconjuntos que tem o > elemento n-3, > > entao teremos T[n-3] - T[n-4] subconjuntos com os > elementos n-1 e n-2: > > X = T[n-3] - T[n-4] > > > > entao nossa recorrencia fica: > > T[n] = 2*T[n-1] - T[n-3] + T[n-4] > > > > []'s, > > Helder > > > > --- "David M. Cardoso" <[EMAIL PROTECTED]> > > escreveu: > > > > > > > Olá, > > > > > > Alguem pode me ajudar? Não consegui resolver o > seguinte problema: > > > > > > "Quantos subconjuntos o conjunto {1,2,3,...,n} > tais que não contêm > > > três inteiros consecutivos?" > > > > > > A dica dada na questão é: "Encontre uma > recorrência." > > Porém, qualquer > > > solução (sem/com recorrência) vai ajudar. > > > > > > []'s > > > David > > > > > > > > > > > > > ___ > > Yahoo! Mail agora com 100MB, anti-spam e antivírus > grátis! > > http://br.info.mail.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 > > > == > > === > > > > > = > 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 > = > bm-l.html > = > ___ Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis! http://br.info.mail.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 =
Re: [obm-l] Problema Subconjuntos
Oi, Helder: Eu achei uma recorrencia diferente: Seja A um dos T(n) subconjuntos nas condicoes do enunciado. Existem 3 casos a considerar: Caso 1: n nao pertence a A ==> existem T(n-1) tais subconjuntos Caso 2: n pertence mas n-1 nao pertence a A ==> existem T(n-2) tais subconjuntos Caso 3: n e n-1 pertencem a A ==> n-2 nao pode pertencer a A ==> existem T(n-3) tais subconjuntos Logo, T(n) = T(n-1) + T(n-2) + T(n-3). Usando o fato de que T(0) = 1, T(1) = 2 e T(2) = 4, obtemos: T(3) = 7 T(4) = 13 T(5) = 24 T(6) = 44 T(7) = 81 T(8) = 149 T(9) = 274 ... []s, Claudio. on 20.07.04 19:29, Helder Suzuki at [EMAIL PROTECTED] wrote: > vamos ver, seguindo a dica de usar recorrencia > > se T[n] for igual ao numero de subconjuntos do > conjunto {1, 2, ..., n} que nao contem 3 inteiros > consecutivos. > temos que: > T[0] = 1 > {} > > T[1] = 2 > {} e {1} > > T[2] = 4 > {}, {1}, > {2} e {1, 2} > > T[3] = 7 > {}, {1}, {2}, {1, 2}, > {3}, {1, 3}, {2, 3} > > T[4] = 13 > {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, > {4}, {1, 4}, {2, 4}, {3, 4}, {1, 2, 4}, {1, 3, 4} > > bom, suponha que sabemos o valor de T[n-1], T[n-2], > ..., T[1]; como podemos achar T[n] em funcao de > T[n-1]? humm... > considere todos subconjuntos de {1, 2, 3, 4, ..., n-1} > que satisfazem a condicao do enunciado. > se adicionarmos um elemento n, em quais desses > subconjuntos o n pode entrar e quais ele nao pode(para > manter a condicao do enunciado)? > se n nao pode entrar em X subconjuntos, temos que > T[n] = T[n-1] + T[n-1] - X > T[n] = 2*T[n-1] - X > mas X eh o numero de subconjuntos que tem os elementos > n-1 e n-2. > > imagine que temos os subconjnutos de {1, 2, ..., n-3} > e queremos adicionar os elementos n-1 e n-2 a esses > subconjuntos ao mesmo tempo, nesse caso só nao > poderemos adicionar n-1 e n-2 aos subconjuntos que tem > o elemento n-3, entao teremos T[n-3] - T[n-4] > subconjuntos com os elementos n-1 e n-2: > X = T[n-3] - T[n-4] > > entao nossa recorrencia fica: > T[n] = 2*T[n-1] - T[n-3] + T[n-4] > > []'s, > Helder > > --- "David M. Cardoso" <[EMAIL PROTECTED]> > escreveu: > >> >> Olá, >> >> Alguem pode me ajudar? Não consegui resolver o >> seguinte problema: >> >> "Quantos subconjuntos o conjunto {1,2,3,...,n} tais >> que não contêm três >> inteiros consecutivos?" >> >> A dica dada na questão é: "Encontre uma >> recorrência." Porém, qualquer >> solução (sem/com recorrência) vai ajudar. >> >> []'s >> David > > > > > > ___ > Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis! > http://br.info.mail.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 > = > = 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: RES: [obm-l] Problema Subconjuntos
C(n-2;3). Basta usar o primeiro lema de Kaplansky. == Mensagem enviada pelo CIP WebMAIL - Nova Geração - v. 2.1 CentroIn Internet Provider http://www.centroin.com.br Tel: (21) 2542-4849, (21) 2295-3331Fax: (21) 2295-2978 Empresa 100% Brasileira - Desde 1992 prestando servicos online -- Original Message --- From: "David M. Cardoso" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Tue, 20 Jul 2004 20:57:24 -0300 Subject: RES: [obm-l] Problema Subconjuntos > Cara, muito obrigado.. > Sendo que ta dando trabalho pra eu entender algumas coisas, > como "teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2".. > hora eu penso que entendi, hora eu não entendo mais e fico tentando lembrar > pq eu fico entendido antes, talvez seja o nervosismo, talvez seja apenas > porque o raciocinio eh complicado demais pra mim.. > > Outra duvida que tenho é se é possível transformar a recorrência num > "polinomiozinho" em função de n ou se uma resposta desse tipo já esta > completa o suficiente.. > > []'s > David > > > -Mensagem original- > > De: [EMAIL PROTECTED] > > [mailto:[EMAIL PROTECTED] Em nome de Helder Suzuki > > Enviada em: terça-feira, 20 de julho de 2004 19:30 > > Para: [EMAIL PROTECTED] > > Assunto: Re: [obm-l] Problema Subconjuntos > > > > vamos ver, seguindo a dica de usar recorrencia > > > > se T[n] for igual ao numero de subconjuntos do conjunto {1, > > 2, ..., n} que nao contem 3 inteiros consecutivos. > > temos que: > > T[0] = 1 > > {} > > > > T[1] = 2 > > {} e {1} > > > > T[2] = 4 > > {}, {1}, > > {2} e {1, 2} > > > > T[3] = 7 > > {}, {1}, {2}, {1, 2}, > > {3}, {1, 3}, {2, 3} > > > > T[4] = 13 > > {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {4}, {1, 4}, {2, > > 4}, {3, 4}, {1, 2, 4}, {1, 3, 4} > > > > bom, suponha que sabemos o valor de T[n-1], T[n-2], ..., > > T[1]; como podemos achar T[n] em funcao de T[n-1]? humm... > > considere todos subconjuntos de {1, 2, 3, 4, ..., n-1} que > > satisfazem a condicao do enunciado. > > se adicionarmos um elemento n, em quais desses subconjuntos o > > n pode entrar e quais ele nao pode(para manter a condicao do > > enunciado)? > > se n nao pode entrar em X subconjuntos, temos que T[n] = > > T[n-1] + T[n-1] - X T[n] = 2*T[n-1] - X mas X eh o numero de > > subconjuntos que tem os elementos > > n-1 e n-2. > > > > imagine que temos os subconjnutos de {1, 2, ..., n-3} e > > queremos adicionar os elementos n-1 e n-2 a esses > > subconjuntos ao mesmo tempo, nesse caso só nao poderemos > > adicionar n-1 e n-2 aos subconjuntos que tem o elemento n-3, > > entao teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2: > > X = T[n-3] - T[n-4] > > > > entao nossa recorrencia fica: > > T[n] = 2*T[n-1] - T[n-3] + T[n-4] > > > > []'s, > > Helder > > > > --- "David M. Cardoso" <[EMAIL PROTECTED]> > > escreveu: > > > > > > > Olá, > > > > > > Alguem pode me ajudar? Não consegui resolver o seguinte problema: > > > > > > "Quantos subconjuntos o conjunto {1,2,3,...,n} tais que não contêm > > > três inteiros consecutivos?" > > > > > > A dica dada na questão é: "Encontre uma recorrência." > > Porém, qualquer > > > solução (sem/com recorrência) vai ajudar. > > > > > > []'s > > > David > > > > > > > > > > > > ___ > > Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis! > > http://br.info.mail.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 > > == > > === > > > > = > 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 > = --- End of Original Message --- = 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 =
RES: [obm-l] Problema Subconjuntos
Cara, muito obrigado.. Sendo que ta dando trabalho pra eu entender algumas coisas, como "teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2".. hora eu penso que entendi, hora eu não entendo mais e fico tentando lembrar pq eu fico entendido antes, talvez seja o nervosismo, talvez seja apenas porque o raciocinio eh complicado demais pra mim.. Outra duvida que tenho é se é possível transformar a recorrência num "polinomiozinho" em função de n ou se uma resposta desse tipo já esta completa o suficiente.. []'s David > -Mensagem original- > De: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] Em nome de Helder Suzuki > Enviada em: terça-feira, 20 de julho de 2004 19:30 > Para: [EMAIL PROTECTED] > Assunto: Re: [obm-l] Problema Subconjuntos > > vamos ver, seguindo a dica de usar recorrencia > > se T[n] for igual ao numero de subconjuntos do conjunto {1, > 2, ..., n} que nao contem 3 inteiros consecutivos. > temos que: > T[0] = 1 > {} > > T[1] = 2 > {} e {1} > > T[2] = 4 > {}, {1}, > {2} e {1, 2} > > T[3] = 7 > {}, {1}, {2}, {1, 2}, > {3}, {1, 3}, {2, 3} > > T[4] = 13 > {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {4}, {1, 4}, {2, > 4}, {3, 4}, {1, 2, 4}, {1, 3, 4} > > bom, suponha que sabemos o valor de T[n-1], T[n-2], ..., > T[1]; como podemos achar T[n] em funcao de T[n-1]? humm... > considere todos subconjuntos de {1, 2, 3, 4, ..., n-1} que > satisfazem a condicao do enunciado. > se adicionarmos um elemento n, em quais desses subconjuntos o > n pode entrar e quais ele nao pode(para manter a condicao do > enunciado)? > se n nao pode entrar em X subconjuntos, temos que T[n] = > T[n-1] + T[n-1] - X T[n] = 2*T[n-1] - X mas X eh o numero de > subconjuntos que tem os elementos > n-1 e n-2. > > imagine que temos os subconjnutos de {1, 2, ..., n-3} e > queremos adicionar os elementos n-1 e n-2 a esses > subconjuntos ao mesmo tempo, nesse caso só nao poderemos > adicionar n-1 e n-2 aos subconjuntos que tem o elemento n-3, > entao teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2: > X = T[n-3] - T[n-4] > > entao nossa recorrencia fica: > T[n] = 2*T[n-1] - T[n-3] + T[n-4] > > []'s, > Helder > > --- "David M. Cardoso" <[EMAIL PROTECTED]> > escreveu: > > > > > Olá, > > > > Alguem pode me ajudar? Não consegui resolver o seguinte problema: > > > > "Quantos subconjuntos o conjunto {1,2,3,...,n} tais que não contêm > > três inteiros consecutivos?" > > > > A dica dada na questão é: "Encontre uma recorrência." > Porém, qualquer > > solução (sem/com recorrência) vai ajudar. > > > > []'s > > David > > > > > > ___ > Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis! > http://br.info.mail.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 > == > === > = 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] Problema Subconjuntos
vamos ver, seguindo a dica de usar recorrencia se T[n] for igual ao numero de subconjuntos do conjunto {1, 2, ..., n} que nao contem 3 inteiros consecutivos. temos que: T[0] = 1 {} T[1] = 2 {} e {1} T[2] = 4 {}, {1}, {2} e {1, 2} T[3] = 7 {}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3} T[4] = 13 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {4}, {1, 4}, {2, 4}, {3, 4}, {1, 2, 4}, {1, 3, 4} bom, suponha que sabemos o valor de T[n-1], T[n-2], ..., T[1]; como podemos achar T[n] em funcao de T[n-1]? humm... considere todos subconjuntos de {1, 2, 3, 4, ..., n-1} que satisfazem a condicao do enunciado. se adicionarmos um elemento n, em quais desses subconjuntos o n pode entrar e quais ele nao pode(para manter a condicao do enunciado)? se n nao pode entrar em X subconjuntos, temos que T[n] = T[n-1] + T[n-1] - X T[n] = 2*T[n-1] - X mas X eh o numero de subconjuntos que tem os elementos n-1 e n-2. imagine que temos os subconjnutos de {1, 2, ..., n-3} e queremos adicionar os elementos n-1 e n-2 a esses subconjuntos ao mesmo tempo, nesse caso só nao poderemos adicionar n-1 e n-2 aos subconjuntos que tem o elemento n-3, entao teremos T[n-3] - T[n-4] subconjuntos com os elementos n-1 e n-2: X = T[n-3] - T[n-4] entao nossa recorrencia fica: T[n] = 2*T[n-1] - T[n-3] + T[n-4] []'s, Helder --- "David M. Cardoso" <[EMAIL PROTECTED]> escreveu: > > > Olá, > > Alguem pode me ajudar? Não consegui resolver o > seguinte problema: > > "Quantos subconjuntos o conjunto {1,2,3,...,n} tais > que não contêm três > inteiros consecutivos?" > > A dica dada na questão é: "Encontre uma > recorrência." Porém, qualquer > solução (sem/com recorrência) vai ajudar. > > []'s > David ___ Yahoo! Mail agora com 100MB, anti-spam e antivírus grátis! http://br.info.mail.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 =
[obm-l] Problema Subconjuntos
Olá, Alguem pode me ajudar? Não consegui resolver o seguinte problema: "Quantos subconjuntos o conjunto {1,2,3,...,n} tais que não contêm três inteiros consecutivos?" A dica dada na questão é: "Encontre uma recorrência." Porém, qualquer solução (sem/com recorrência) vai ajudar. []'s David = 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 =