[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Problema Subconjuntos. Correção



Favor esquecer a bobagem abaixo. 
Morgado



---------- Original Message -----------
From: "Augusto Cesar de Oliveira Morgado" <morgado@centroin.com.br>
To: obm-l@mat.puc-rio.br
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" <david-obm@suati.com.br>
> To: <obm-l@mat.puc-rio.br>
> 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: owner-obm-l@mat.puc-rio.br 
> > > [mailto:owner-obm-l@mat.puc-rio.br] Em nome de Helder Suzuki
> > > Enviada em: terça-feira, 20 de julho de 2004 19:30
> > > Para: obm-l@mat.puc-rio.br
> > > 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" <david-obm@suati.com.br>
> > > 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
=========================================================================