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