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 =========================================================================