Re: [obm-l] IMO 2004 - Problema 3 - Incompleto

[Carlos Yuzo Shine]

Nesta IMO houve quatro Ouros 42: um do Canadá (note
que o Canadá empatou com o Brasil em pontos!!), um da
Hungria, e dois da Rússia. Nenhum é chinês ou
norte-americano.

Mas a delegação da China foi a única que obteve seis
medalhas de ouro este ano.

[]'s
Shine

--- [EMAIL PROTECTED] wrote:
> Falando em IMO sera que algum participante da China,
> U.S.A ou outro pais fez 
> 42 pontos ? 
> 
> 
> 
> 
> Em uma mensagem de 19/7/2004 21:39:22 Hora padrão
> leste da Am. Sul, 
> [EMAIL PROTECTED] escreveu:
> 
> 
> > 
> > Desculpem, mas este esboço que enviei está
> incompleto. Não li todas as 
> > mensagens da lista, talvez alguém já tenha
> percebido, mas exatamente   onde 
> > eu escrevo "verifiquem isto, na pressa eu posso
> ter me enganado" eu 
> > realmente me enganei (a pressa não combina com
> problemas da IMO).
> > 
> > Luciano.
> > 
> > 
> > 
> 
> 
> 


__
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://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] IMO 2005, 2006, 2007, 2008 e 2009

[Carlos Yuzo Shine]

Oi gente,

Só informando onde e quando serão as próximas IMOs:

1 a 12 de julho de 2005: Cancún, México (as provas
serão nos dias 6 e 7)
2006: Eslovênia
2007: Vietnam
2008: Espanha
2009: Alemanha

[]'s
Shine




__
Do you Yahoo!?
Vote for the stars of Yahoo!'s next ad campaign!
http://advision.webevents.yahoo.com/yahoo/votelifeengine/
=
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] Equipe para IMC-2004

[Olimpiada Brasileira de Matematica]

Oi Gente, 

Já temos equipe confirmada para participar da International Mathematical

Competition for University Students a ser realizada na cidade de
Skopje
na Macedônia entre os dias 23 a 29 de julho.

Líder: 
Prof. Fernando Pimentel (UFC) 

Equipe:
Thiago Barros Rodrigues Costa - UNICAMP
Yuri Gomes Lima - UFC
Rafael Fonteles - UFPI
Diêgo Veloso Uchôa - IME
Eduardo Famini Silva - IME
Eduardo Casagrande Stabel - UFRGS
Carlos Stein Naves de Brito - ITA
Humberto Silva Naves - ITA
Tertuliano Franco Santos Franco - UFBA
Murilo Vasconcelos Freire - IME 
Alex Corrêa Abreu - UFRJ  


Parabéns a todos!!! 

Abraços, Nelita.   

[obm-l] Dado interessante sobre a IMO 2004

[Carlos Yuzo Shine]

Oi gente,

Um dado interessante: só três países não obtiveram
nenhum zero nos problemas de seus alunos (isto é, cada
aluno recebeu em cada problema uma nota maior que
zero): China, Japão e EUA.

E só quatro países só receberam um zero: Bulgária,
Hungria, Irã e... o Brasil!

[]'s
Shine




__
Do you Yahoo!?
Vote for the stars of Yahoo!'s next ad campaign!
http://advision.webevents.yahoo.com/yahoo/votelifeengine/
=
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] Dado interessante sobre a IMO 2004

[Alan Pellejero]

Olá pessoal, gostaria de parabenizar a equipe pela conquista e tirar umas dúvidas que eu tenho...
1-) Em alguma IMO o Brasil já fez 42 pontos?
2-) Existe IMO no nível universitário?
3-) Ouvi dizer que temos um rapaz de 19 anos que terminou o doutorado no IMPA. Gostaria de saber se ele já participou de alguma IMO? Se sim, como foi o desempenho, se não, por quê?
Grato!
Um abraço
AlanCarlos Yuzo Shine <[EMAIL PROTECTED]> wrote:
Oi gente,Um dado interessante: só três países não obtiveramnenhum zero nos problemas de seus alunos (isto é, cadaaluno recebeu em cada problema uma nota maior quezero): China, Japão e EUA.E só quatro países só receberam um zero: Bulgária,Hungria, Irã e... o Brasil![]'sShine__Do you Yahoo!?Vote for the stars of Yahoo!'s next ad campaign!http://advision.webevents.yahoo.com/yahoo/votelifeengine/=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=
		Yahoo! Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!

Re: [obm-l] Dado interessante sobre a IMO 2004

[Olimpiada Brasileira de Matematica]

At 01:09 PM 7/20/04 -0300, you wrote:
Olá pessoal, gostaria de parabenizar a equipe pela conquista e tirar umas 
dúvidas que eu tenho...

1-) Em alguma IMO o Brasil já fez 42 pontos?
Sim, foi o Prof. Nicolau Saldanha. :) :)
2-) Existe IMO no nível universitário?
Sim, a IMC. (nossa equipe vai na quinta-feira)
3-) Ouvi dizer que temos um rapaz de 19 anos que terminou o doutorado no 
IMPA.
Verdade.
Gostaria de saber se ele já participou de alguma IMO?
Não.
Se sim, como foi o desempenho, se não, por quê?
Ele não é olímpico.
Grato!
Um abraço
Alan
Abração, Nelita.
=
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] Análise

[Lista OBM]

Gente,
 
não precisam mais responder o problema, pois consegui fazê-lo.Lista OBM <[EMAIL PROTECTED]> wrote:

 
Gostaria que alguém me ajudasse com o problema abiaxo.
 
Seja A em L(R^m, R^n) e A* em L(R^n,R^m) (A* é a adjunta de A). Prove que a norma de A definida por ||A|| = [tr(A*A)]^1/2, onde  = tr(A*B) define um produto interno para L(R^m, R^n), é diferenciável, exceto no ponto 0.
 
Grato, Éder.
__Do You Yahoo!?Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com 
		Yahoo! Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!

Re: [obm-l] Dado interessante sobre a IMO 2004

[edmilson motta]

Isso reflete o excelente trabalho feito pelos alunos e
pelos líderes: Shine e Gugu. Parabéns!! 

Temos agora muito trabalho pela frente para manter e
melhorar os nossos resultados.

Abraços, Ed.



--- Carlos Yuzo Shine <[EMAIL PROTECTED]> wrote:
> Oi gente,
> 
> Um dado interessante: só três países não obtiveram
> nenhum zero nos problemas de seus alunos (isto é,
> cada
> aluno recebeu em cada problema uma nota maior que
> zero): China, Japão e EUA.
> 
> E só quatro países só receberam um zero: Bulgária,
> Hungria, Irã e... o Brasil!
> 
> []'s
> Shine
> 
> 
>   
>   
> __
> Do you Yahoo!?
> Vote for the stars of Yahoo!'s next ad campaign!
>
http://advision.webevents.yahoo.com/yahoo/votelifeengine/
>
=
> 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
>
=
> 




__
Do you Yahoo!?
Yahoo! Mail Address AutoComplete - You start. We finish.
http://promotions.yahoo.com/new_mail 
=
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] Função Exponencial

[Lista OBM]

Gostaria de saber se existe duas funções reais f e g tais que (fog)(x) = e^x.
 
Grato, Éder. 
		Yahoo! Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!

[obm-l] Função Exponencial

[Lista OBM]

Gostaria de saber se existe duas funções reais f e g tais que (fog)(x) = e^x.
 
Grato, Éder.
		Yahoo! Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!

Re: [obm-l] Função Exponencial

[Domingos Jr.]

seja g : IR -> IR uma bijeção
defina f(x) = exp{g^(-1) (x)}
é simples ver que (f o g)(x) = f(g(x)) = exp{g^(-1) (g(x))} = exp{x}.
Gostaria de saber se existe duas funções reais f e g tais que (fog)(x) 
= e^x.
 
Grato, Éder. 


Yahoo! Mail 
 
agora ainda melhor: 100MB, anti-spam e antivírus grátis! 

=
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] Função Exponencial

[Carlos]

Oi,  você poderia pegar, por exemplo, 
por exemplo, f(x)=x e g(x)=e^x.
Carlos

Lista OBM wrote:

  Gostaria de saber se existe duas funções reais f e g tais que
(fog)(x) = e^x.
   
  Grato, Éder. 
   
  Yahoo!
Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!

[obm-l] Re: [obm-l] Análise

[Artur Costa Steiner]

Parabens! Eu cheguei a ve-lo, mas ultimamente ando infelizmente sem poder
participar muito da lista.Artur

- Mensagem Original De:
[EMAIL PROTECTED]Para: "[EMAIL PROTECTED]"
<[EMAIL PROTECTED]>Assunto: Re: [obm-l] AnáliseData:
20/07/04 14:40
Gente,
 
não precisam mais responder o problema, pois consegui
fazê-lo.Lista OBM <[EMAIL PROTECTED]>
wrote:

 
Gostaria que alguém me ajudasse com o problema abiaxo.
 
Seja A em L(R^m, R^n) e A* em L(R^n,R^m) (A* é a adjunta de A). Prove
que a norma de A definida por ||A|| = [tr(A*A)]^1/2, onde  =
tr(A*B) define um produto interno para L(R^m, R^n), é
diferenciável, exceto no ponto 0.
 
Grato, Éder.
__Do You
Yahoo!?Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com 


Yahoo!
Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!



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] Mais uma da EN -Derivada

[Artur Costa Steiner]

Dica: considere a definicao de derivada e a Regra de L'Ho
Arturpital


- Mensagem Original 
De: [EMAIL PROTECTED]
Para: "[EMAIL PROTECTED]" <[EMAIL PROTECTED]>
Assunto: [obm-l] Mais uma da EN -Derivada
Data: 19/07/04 19:21

Seja G(x) uma função real derivável até a 3ª ordem para
todo x real, tal que G(0) = G '(0) = 0 e G ''(0) = 16.
Se F(X) é função real definida por:

| G(x)/2x ,se X diferente de 0
|
F(X) - |
|
| 0 ,se X = 0

Então F '(0) é Igual a:

A) 16

B) 12

C) 8

D) 4

E) 0


[]`s

João Vitor, Foraleza- CE


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


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
=

[obm-l] RES: [obm-l] Função Exponencial

[David M. Cardoso]

f(x) = e^x
g(x) = x

Pode ser assim?
 

> -Mensagem original-
> De: [EMAIL PROTECTED] 
> [mailto:[EMAIL PROTECTED] Em nome de Lista OBM
> Enviada em: terça-feira, 20 de julho de 2004 14:37
> Para: [EMAIL PROTECTED]
> Assunto: [obm-l] Função Exponencial
> 
> Gostaria de saber se existe duas funções reais f e g tais que 
> (fog)(x) = e^x.
>  
> Grato, Éder. 
> 
> 
> 
> Yahoo! Mail 
>   agora ainda melhor: 100MB, anti-spam e antivírus > grátis!
> 


=
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

[David M. Cardoso]

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
=

[obm-l] Problema de Divisibilidade / Primos

[David M. Cardoso]

Mais duas questoes que não consigo me mecher:

Quantos inteiros existem que não são divisíveis por qualquer que seja o
primo maior que 20 e não são divisiveis por qualquer que seja o primo?

[]'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
=

Re: [obm-l] Dado interessante sobre a IMO 2004

[JoaoCarlos_Junior]

E o Ralph e o professor Gugu? Quais as notas de cada, quando aumentaram a
coleção de prêmios olímpicos do país com três medalhas douradas?
E  ainda,  no  ano  deles, quantos atingiram os 42 pontos? E De que
  países eram?
Essas duas últimas perguntas valem também para o professor Nicolau.

  Um abraço, João.



   

  Olimpiada

  Brasileira dePara: [EMAIL PROTECTED] 
 
  Matematica   cc: 

  <[EMAIL PROTECTED]>Assunto:  Re: [obm-l] Dado 
interessante sobre a IMO 2004
  Enviado Por: 

  [EMAIL PROTECTED]

  uc-rio.br

   

   

  20/07/2004 13:34 

  Favor responder a

  obm-l

   

   





At 01:09 PM 7/20/04 -0300, you wrote:
>Olá pessoal, gostaria de parabenizar a equipe pela conquista e tirar umas
>dúvidas que eu tenho...

>1-) Em alguma IMO o Brasil já fez 42 pontos?
Sim, foi o Prof. Nicolau Saldanha. :) :)

>2-) Existe IMO no nível universitário?
Sim, a IMC. (nossa equipe vai na quinta-feira)

>3-) Ouvi dizer que temos um rapaz de 19 anos que terminou o doutorado no
>IMPA.
Verdade.

>Gostaria de saber se ele já participou de alguma IMO?
Não.

>Se sim, como foi o desempenho, se não, por quê?
Ele não é olímpico.

>Grato!
>Um abraço
>Alan

Abração, Nelita.


=
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 de Divisibilidade / Primos

[Bruno França dos Reis]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On Tuesday 20 July 2004 18:26, David M. Cardoso wrote:
> Mais duas questoes que não consigo me mecher:
>
> Quantos inteiros existem que não são divisíveis por qualquer que seja o
> primo maior que 20 e não são divisiveis por qualquer que seja o primo?

a) infinitos: 2^n não é divisível por qualquer que seja o primo maior que 20, 
pois é divisível apenas pelo primo 2, qualquer que seja n natural.

b) apenas o 1, pois qualquer outro número é divisível por ao menos um primo: 
se ele for composto, sabemos que ele é múltiplo de primos, e se ele é primo, 
ele é divisível por si próprio, um número primo. Já o 1 é divisível apenas 
por 1, que não é primo (e não me venham com essa de que 1 é primo também!)

acho que é isso!

abraço

- -- 
Bruno França dos Reis
brunoreis at terra com br
icq: 12626000
gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key

-BEGIN PGP SIGNATURE-
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFA/ZREsHdDIT+qyroRAhQFAKDOZm/uCMp38TYe+uXT2rL+lkNPWQCfWTdb
iMrCfq37UfF/7EZvrP6Qm3g=
=qpSy
-END PGP SIGNATURE-

=
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] RECADO AOS GÊNIOS DE PLANTÃO

[FabianoSutter]

É com muita satisfação que recebo mensagens sobre o meu estudo. Ajuda, dicas e como o 
assunto é chocante, aceito críticas também, muitas até, demasiadamente exageradas que 
insinuam a derrota e a impossibilidade de vencer tal desafio. Muitos pensam na quebra 
em tempo polinomial, como sendo algo impossível e inalcançável.
Alguns até dizem que qualquer idiota faria tal algoritmo. Não estou aqui querendo 
expor um algoritmo para encontrar o n-ésimo primo. Sei que muitos existem. Como disse 
o nosso amigo Domingos qualquer idiota faria um desse. 
Há muito tempo, venho estudando a estrutura do RSA. Sabemos que ela se resume em N = 
p*q. Basta??
Para mim, sim. Qual algoritmo seria capaz de fatorar, em tempo polinomial, tal valor 
de N? Sei o q estou fazendo e entrei no grupo para uma troca de idéias. Não posso 
aceitar conselhos do tipo, estude mais, esqueça isso, não existe resposta mais 
didática para tal conceito,etc..Estou confiante no que estou fazendo.Tenho duas 
saídas: ou eu quebro a cara, ou consigo montar o algoritmo. Posso estar blefando. E se 
não estiver??
A Matemática é assim. Sorte lançada!!!
Abraço a todos!!!
Agradeço todos aqueles q até agora me ajudaram
Em breve, estarei colocando algo na lista para apreciação dos interessados e tb para 
os gênios de plantão.
=
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 de Divisibilidade / Primos

[Alessandro]

h, agora vc me deixou com uma duvida, pois ateh hj
sabia q o numero 1  era primos, mas nao era considerado como
primo por ser composto,( o mesmo acontecia com o 2, ou estou ficando
loko ;)





On Tuesday 20 July 2004 18:53, Bruno França dos Reis wrote:
] On Tuesday 20 July 2004 18:26, David M. Cardoso wrote:
] > Mais duas questoes que não consigo me mecher:
] >
] > Quantos inteiros existem que não são divisíveis por qualquer que seja o
] > primo maior que 20 e não são divisiveis por qualquer que seja o primo?
]
] a) infinitos: 2^n não é divisível por qualquer que seja o primo maior que
 20, ] pois é divisível apenas pelo primo 2, qualquer que seja n natural. ]
] b) apenas o 1, pois qualquer outro número é divisível por ao menos um
 primo: ] se ele for composto, sabemos que ele é múltiplo de primos, e se ele
 é primo, ] ele é divisível por si próprio, um número primo. Já o 1 é
 divisível apenas ] por 1, que não é primo (e não me venham com essa de que 1
 é primo também!) ]
] acho que é isso!
]
] abraço
]

-- 


"O universo eh um texto escrito em caracteres matematicos." (Galileu Galilei)

* Copyleft by(c): MuTlEy_SaNdRo
* Idioma: C, ASM(AT&T)
* mutley  sandro  spymac  com 
* Slack User# 342751  [http://counter.li.org]
* ICQ# 15792
* SlackWare /Linux 9.1 kernel 2.6.6



=
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

[Helder Suzuki]

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
=

Re: [obm-l] Função Exponencial

[Fábio Dias Moreira]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Lista OBM <[EMAIL PROTECTED]> said:
> Gostaria de saber se existe duas funções reais f e g tais que (fog)(x) =
> e^x.
> [...]

Como outros já responderam, sim, existe: basta tomar f(x) = x e g(x) = e^x.

O mais interessante nesse problema é que existe uma função f: R -> R tal que 
(fof)(x) = e^x -- esse é um dos problemas propostos na Matemática 
Universitária, no. 35, páginas 41-46.

(espaço para quem quer pensar no problema...)


















































Cosndiere A_1 = (-1, 0], A_2 = (-inf, -1] e, se A_i = (a_i, b_i], então 
A_{i+2} = (e^a_i, e^b_i] (estou definindo e^-inf = 0). É fácil ver que os 
A_i's são uma partição de R.

Agora, defina f_i: A_i -> A_{i+1} por f_1(x) = -1/(x+1) e f_{i+1}(x) = 
e^(f_i^{-1}(x)), onde f_i^{-1} é a inversa da f_i. Para provar que esta 
definição faz sentido, temos que provar que f_i é invertível para todo i. 
Isso é verdade para i = 1; suponha a afirmação verdadeira para f_{i-1}. Então 
f_i é trivialmente injetora, e é sobrejetora, pois a imagem de f_{i-1}^{-1} é 
A_{i-1}, logo a imagem de f_i é a "exponencial" de A_{i-1}, que é A_{i+1}.

Finalmente, defina f(x) = f_i(x), onde i é escolhido de tal forma que x 
pertença a A_i. Então

f(f(x)) = f(f_i(x)). Mas f_i(x) pertence a A_{i+1}, logo

f(f(x)) = f_{i+1}(f_i(x)) = e^(f_i^{-1}(f_i(x))) = e^x para todo x real.

[]s,

- -- 
Fábio Dias Moreira
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFA/aOmalOQFrvzGQoRApaJAJwOwqqzb2/iF37X4BnJ+fPFyHZylQCePqdA
Z9SahgcKCY+ovHQkGILqRWg=
=EbqB
-END PGP SIGNATURE-


=
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 de Divisibilidade / Primos

[Bruno França dos Reis]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On Tuesday 20 July 2004 19:20, Alessandro wrote:
> h, agora vc me deixou com uma duvida, pois ateh hj
> sabia q o numero 1  era primos, mas nao era considerado como
> primo por ser composto,( o mesmo acontecia com o 2, ou estou ficando
> loko ;)

1 é composto? Então devem haver p e q primos tais que p*q=1. |p*q| = |p|*|q|. 
Se p>1 ou q>1 então |p*q| > 1, então |p*q| != 1, então p*q != +-1, logo 1 não 
é composto.

2 é composto? Hmmm, é divisível apenas por 2 e por 1, logo, pela definição, é 
primo.

1 é primo? Hmm, pelo T.F.A., temos que a cada número natural corresponde um 
único produto da forma p_1^a_1 * p_2^a_2 * p_3^a_3 * ..., onde p_n é o 
n-ésimo número primo, e a_n é o expoente do n-ésimo primo para que o produto 
seja igual ao numero natural em questão. Para um dado número, o TFA garante 
que existem valores para todos os p's e a's, e que esses valores são únicos. 
Considere que 1 é primo. Seria então o primeiro número primo: p_1 = 1. Então, 
peguemos o número 10, como exemplo:
10=1^1 * 2^1 * 5^1
Porém, temos que a_1, que nesse exemplo é igual a 1, pode variar, veja:
10=1^652313 * 2^1 * 5^1
Então há infinitas formas de escrever um determinado número como produto de 
_primos_. (??)
Isso contraria o TFA, o que termina um dos argumentos para 1 não ser 
considerado primo.

Outro argumento: a definição de primo é: "um número p>=2 é primo se, e somente 
se, ele é divisível por 1 e por p". Mais clareza que isso é impossível! (essa 
definição consta no "Introdução à Teoria dos Números, de João de Oliveira 
Santos (? acho que é esse o nome dele, estou sem o livro no momento))


...

abraço


- -- 
Bruno França dos Reis
brunoreis at terra com br
icq: 12626000
gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key

-BEGIN PGP SIGNATURE-
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFA/aWasHdDIT+qyroRAu/bAJ9A8jYENo4sP3Ie7zJIoiCw8ZOaDwCcDk2d
GONkCMElWZIptmylxBw+MKM=
=lMu/
-END PGP SIGNATURE-

=
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 de Divisibilidade / Primos

[David M. Cardoso]

Droga droga droga !!!
Na pressa, errei o enunciado da questão!
Mil desculpas!

Segue o enunciado correto:

"Quantos inteiros existem que não são divisíveis por qualquer que seja o
primo maior que 20 e não são divisíveis pelo quadrado de qualquer que seja o
primo?"

Puxa vida... tenho prova amanha cedo, vou tentar tirar minhas duvidas de
ultima hora, tenho a sorte de voces existirem e ainda erro o enunciado da
questao... :~(

[]'s
David

> -Mensagem original-
> De: [EMAIL PROTECTED] 
> [mailto:[EMAIL PROTECTED] Em nome de Bruno França dos Reis
> Enviada em: terça-feira, 20 de julho de 2004 18:53
> Para: [EMAIL PROTECTED]
> Assunto: Re: [obm-l] Problema de Divisibilidade / Primos
> 
> -BEGIN PGP SIGNED MESSAGE-
> Hash: SHA1
> 
> On Tuesday 20 July 2004 18:26, David M. Cardoso wrote:
> > Mais duas questoes que não consigo me mecher:
> >
> > Quantos inteiros existem que não são divisíveis por 
> qualquer que seja 
> > o primo maior que 20 e não são divisiveis por qualquer que 
> seja o primo?
> 
> a) infinitos: 2^n não é divisível por qualquer que seja o 
> primo maior que 20, pois é divisível apenas pelo primo 2, 
> qualquer que seja n natural.
> 
> b) apenas o 1, pois qualquer outro número é divisível por ao 
> menos um primo: 
> se ele for composto, sabemos que ele é múltiplo de primos, e 
> se ele é primo, ele é divisível por si próprio, um número 
> primo. Já o 1 é divisível apenas por 1, que não é primo (e 
> não me venham com essa de que 1 é primo também!)
> 
> acho que é isso!
> 
> abraço
> 
> - --
> Bruno França dos Reis
> brunoreis at terra com br
> icq: 12626000
> gpg-key: 
> http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
> 
> -BEGIN PGP SIGNATURE-
> Version: GnuPG v1.2.4 (GNU/Linux)
> 
> iD8DBQFA/ZREsHdDIT+qyroRAhQFAKDOZm/uCMp38TYe+uXT2rL+lkNPWQCfWTdb
> iMrCfq37UfF/7EZvrP6Qm3g=
> =qpSy
> -END PGP SIGNATURE-
> 
> ==
> ===
> 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] RECADO AOS GÊNIOS DE PLANTÃO

[Domingos Jr.]

meu, posta logo o que vc já fez...
matemática é assim... vc quer que alguém te reconheça: faça por merecer!!!
eu não te conheço, não sei o que vc sabe sobre teoria da computação nem 
sobre teoria dos números.
independente disso, eu sei que o problema de fatorar inteiros é muito 
difícil e milhares de mentes brilhantes já tentaram o problema, você 
espera que eu acredite que um desconhecido tenha conseguido... não acha 
que é pretensão demais da sua parte?

e a sua suposta troca de idéias tem se resumido a "qual o 
4567851654854654 primo?" --- questões de relevância muito duvidosa.

como já disse inúmeras vezes... ou vc coloca o que está estudando pra 
quem tiver saco dar uma olhada e --- quem sabe --- te dar conselhos ou 
realmente suas mensagens vão ser pura piada.

É com muita satisfação que recebo mensagens sobre o meu estudo. Ajuda, dicas e como o assunto é chocante, aceito críticas também, muitas até, demasiadamente exageradas que insinuam a derrota e a impossibilidade de vencer tal desafio. Muitos pensam na quebra em tempo polinomial, como sendo algo impossível e inalcançável.
Alguns até dizem que qualquer idiota faria tal algoritmo. Não estou aqui querendo expor um algoritmo para encontrar o n-ésimo primo. Sei que muitos existem. Como disse o nosso amigo Domingos qualquer idiota faria um desse. 
Há muito tempo, venho estudando a estrutura do RSA. Sabemos que ela se resume em N = p*q. Basta??
Para mim, sim. Qual algoritmo seria capaz de fatorar, em tempo polinomial, tal valor de N? Sei o q estou fazendo e entrei no grupo para uma troca de idéias. Não posso aceitar conselhos do tipo, estude mais, esqueça isso, não existe resposta mais didática para tal conceito,etc..Estou confiante no que estou fazendo.Tenho duas saídas: ou eu quebro a cara, ou consigo montar o algoritmo. Posso estar blefando. E se não estiver??
A Matemática é assim. Sorte lançada!!!
Abraço a todos!!!
Agradeço todos aqueles q até agora me ajudaram
Em breve, estarei colocando algo na lista para apreciação dos interessados e tb para os gênios de plantão.
=
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] Dado interessante sobre a IMO 2004

[Paulo Rodrigues]

O Ralph fez 42 no IMO de 87 em Cuba. Na Polônia ele obteve 37 pontos (o
corte foi 34).

Quanto ao Gugu não tenho certeza, mas acho que ele fez 36 pontos na China.

A IMO de 81, que o Nicolaou participou, foi a que teve mais provas
perfeitas... foram mais de 20.

Abraços, Paulo
- Original Message -
From: <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Tuesday, July 20, 2004 4:36 PM
Subject: Re: [obm-l] Dado interessante sobre a IMO 2004






E o Ralph e o professor Gugu? Quais as notas de cada, quando aumentaram a
coleção de prêmios olímpicos do país com três medalhas douradas?
E  ainda,  no  ano  deles, quantos atingiram os 42 pontos? E De que
  países eram?
Essas duas últimas perguntas valem também para o professor Nicolau.

  Um abraço, João.




  Olimpiada
  Brasileira dePara:
[EMAIL PROTECTED]
  Matematica   cc:
  <[EMAIL PROTECTED]>Assunto:  Re: [obm-l] Dado
interessante sobre a IMO 2004
  Enviado Por:
  [EMAIL PROTECTED]
  uc-rio.br


  20/07/2004 13:34
  Favor responder a
  obm-l






At 01:09 PM 7/20/04 -0300, you wrote:
>Olá pessoal, gostaria de parabenizar a equipe pela conquista e tirar umas
>dúvidas que eu tenho...

>1-) Em alguma IMO o Brasil já fez 42 pontos?
Sim, foi o Prof. Nicolau Saldanha. :) :)

>2-) Existe IMO no nível universitário?
Sim, a IMC. (nossa equipe vai na quinta-feira)

>3-) Ouvi dizer que temos um rapaz de 19 anos que terminou o doutorado no
>IMPA.
Verdade.

>Gostaria de saber se ele já participou de alguma IMO?
Não.

>Se sim, como foi o desempenho, se não, por quê?
Ele não é olímpico.

>Grato!
>Um abraço
>Alan

Abração, Nelita.


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


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.723 / Virus Database: 479 - Release Date: 19/7/2004

=
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 de Divisibilidade / Primos

[Bernardo Freitas Paulo da Costa]

Oi, David,

Enumere os primos menores do que 20:
2, 3, 5, 7, 11, 13, 17, 19: são 8.

Um número que satisfaça as condições do enunciado pode ter,
no máximo, um de cada um destes fatores, pela segunda parte, e nenhum 
outro fator, pela primeira parte.
Assim, temos um problema de combinatória, agora:
quantos números podemos formar utilizando apenas o produto de 8 primos, 
onde não podemos incluir um primo duas vezes. Ou, mais combinatória ainda,
quantos subconjuntos de um conjunto de 8 elementos existem?
Para ver que as soluções são iguais, associe a cada subconjunto
o número correspondente ao produto de seus elementos, e ao subconjunto 
vazio o número 1 (eis aqui mais uma boa justificativa para termos um 
produtório vazio valendo 1!!)

Bom, para este problema a resposta é conhecida: vale 2^8 = 256.
Pronto, são 256 números.

Abraços,
Bernardo Costa


On Tue, 20 Jul 2004, David M. Cardoso wrote:

> 
> Droga droga droga !!!
> Na pressa, errei o enunciado da questão!
> Mil desculpas!
> 
> Segue o enunciado correto:
> 
> "Quantos inteiros existem que não são divisíveis por qualquer que seja o
> primo maior que 20 e não são divisíveis pelo quadrado de qualquer que seja o
> primo?"
> 
> Puxa vida... tenho prova amanha cedo, vou tentar tirar minhas duvidas de
> ultima hora, tenho a sorte de voces existirem e ainda erro o enunciado da
> questao... :~(
> 
> []'s
> David
> 
> > -Mensagem original-
> > De: [EMAIL PROTECTED] 
> > [mailto:[EMAIL PROTECTED] Em nome de Bruno França dos Reis
> > Enviada em: terça-feira, 20 de julho de 2004 18:53
> > Para: [EMAIL PROTECTED]
> > Assunto: Re: [obm-l] Problema de Divisibilidade / Primos
> > 
> > -BEGIN PGP SIGNED MESSAGE-
> > Hash: SHA1
> > 
> > On Tuesday 20 July 2004 18:26, David M. Cardoso wrote:
> > > Mais duas questoes que não consigo me mecher:
> > >
> > > Quantos inteiros existem que não são divisíveis por 
> > qualquer que seja 
> > > o primo maior que 20 e não são divisiveis por qualquer que 
> > seja o primo?
> > 
> > a) infinitos: 2^n não é divisível por qualquer que seja o 
> > primo maior que 20, pois é divisível apenas pelo primo 2, 
> > qualquer que seja n natural.
> > 
> > b) apenas o 1, pois qualquer outro número é divisível por ao 
> > menos um primo: 
> > se ele for composto, sabemos que ele é múltiplo de primos, e 
> > se ele é primo, ele é divisível por si próprio, um número 
> > primo. Já o 1 é divisível apenas por 1, que não é primo (e 
> > não me venham com essa de que 1 é primo também!)
> > 
> > acho que é isso!
> > 
> > abraço
> > 
> > - --
> > Bruno França dos Reis
> > brunoreis at terra com br
> > icq: 12626000
> > gpg-key: 
> > http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
> > 
> > -BEGIN PGP SIGNATURE-
> > Version: GnuPG v1.2.4 (GNU/Linux)
> > 
> > iD8DBQFA/ZREsHdDIT+qyroRAhQFAKDOZm/uCMp38TYe+uXT2rL+lkNPWQCfWTdb
> > iMrCfq37UfF/7EZvrP6Qm3g=
> > =qpSy
> > -END PGP SIGNATURE-
> > 
> > ==
> > ===
> > 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
> =
> 

=
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 de Divisibilidade / Primos

[David M. Cardoso]

Aeee ... acabei de pensar na solucao, não sei se ta certo:

se n é o produto de k primos (i<=k<=8), entao
n = p_1 * p_2 * p_3 * ... * p_k

tal que p_i < 20 (1 <= i <= k)
entao p_i pertence ao conjunto dos primos menores que 20 {
2,3,5,7,11,13,17,19 }
queremos contar os subconjuntos desse conjunto... menos o vazio..

temos entao 2^8 - 1 numeros deste tipo.

Ta certo?

[]'s
David

> -Mensagem original-
> De: [EMAIL PROTECTED] 
> [mailto:[EMAIL PROTECTED] Em nome de David M. Cardoso
> Enviada em: terça-feira, 20 de julho de 2004 20:11
> Para: [EMAIL PROTECTED]
> Assunto: RES: [obm-l] Problema de Divisibilidade / Primos
> 
> 
> Droga droga droga !!!
> Na pressa, errei o enunciado da questão!
> Mil desculpas!
> 
> Segue o enunciado correto:
> 
> "Quantos inteiros existem que não são divisíveis por qualquer 
> que seja o primo maior que 20 e não são divisíveis pelo 
> quadrado de qualquer que seja o primo?"
> 
> Puxa vida... tenho prova amanha cedo, vou tentar tirar minhas 
> duvidas de ultima hora, tenho a sorte de voces existirem e 
> ainda erro o enunciado da questao... :~(
> 
> []'s
> David
> 
> > -Mensagem original-
> > De: [EMAIL PROTECTED]
> > [mailto:[EMAIL PROTECTED] Em nome de Bruno França 
> dos Reis 
> > Enviada em: terça-feira, 20 de julho de 2004 18:53
> > Para: [EMAIL PROTECTED]
> > Assunto: Re: [obm-l] Problema de Divisibilidade / Primos
> > 
> > -BEGIN PGP SIGNED MESSAGE-
> > Hash: SHA1
> > 
> > On Tuesday 20 July 2004 18:26, David M. Cardoso wrote:
> > > Mais duas questoes que não consigo me mecher:
> > >
> > > Quantos inteiros existem que não são divisíveis por
> > qualquer que seja
> > > o primo maior que 20 e não são divisiveis por qualquer que
> > seja o primo?
> > 
> > a) infinitos: 2^n não é divisível por qualquer que seja o 
> primo maior 
> > que 20, pois é divisível apenas pelo primo 2, qualquer que seja n 
> > natural.
> > 
> > b) apenas o 1, pois qualquer outro número é divisível por 
> ao menos um 
> > primo:
> > se ele for composto, sabemos que ele é múltiplo de primos, 
> e se ele é 
> > primo, ele é divisível por si próprio, um número primo. Já o 1 é 
> > divisível apenas por 1, que não é primo (e não me venham 
> com essa de 
> > que 1 é primo também!)
> > 
> > acho que é isso!
> > 
> > abraço
> > 
> > - --
> > Bruno França dos Reis
> > brunoreis at terra com br
> > icq: 12626000
> > gpg-key: 
> > http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
> > 
> > -BEGIN PGP SIGNATURE-
> > Version: GnuPG v1.2.4 (GNU/Linux)
> > 
> > iD8DBQFA/ZREsHdDIT+qyroRAhQFAKDOZm/uCMp38TYe+uXT2rL+lkNPWQCfWTdb
> > iMrCfq37UfF/7EZvrP6Qm3g=
> > =qpSy
> > -END PGP SIGNATURE-
> > 
> > ==
> > ===
> > 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
> ==
> ===
> 


=
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

[David M. Cardoso]

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
=

RES: RES: [obm-l] Problema de Divisibilidade / Primos

[David M. Cardoso]

Realmente.. realmente.. o vazio conta como o numero 1..
ok .. obrigado!

[]'s
David

> -Mensagem original-
> De: [EMAIL PROTECTED] 
> [mailto:[EMAIL PROTECTED] Em nome de Bernardo 
> Freitas Paulo da Costa
> Enviada em: terça-feira, 20 de julho de 2004 21:29
> Para: [EMAIL PROTECTED]
> Assunto: Re: RES: [obm-l] Problema de Divisibilidade / Primos
> 
> Oi, David,
> 
> Enumere os primos menores do que 20:
> 2, 3, 5, 7, 11, 13, 17, 19: são 8.
> 
> Um número que satisfaça as condições do enunciado pode ter, 
> no máximo, um de cada um destes fatores, pela segunda parte, 
> e nenhum outro fator, pela primeira parte.
> Assim, temos um problema de combinatória, agora:
> quantos números podemos formar utilizando apenas o produto de 
> 8 primos, onde não podemos incluir um primo duas vezes. Ou, 
> mais combinatória ainda, quantos subconjuntos de um conjunto 
> de 8 elementos existem?
> Para ver que as soluções são iguais, associe a cada 
> subconjunto o número correspondente ao produto de seus 
> elementos, e ao subconjunto vazio o número 1 (eis aqui mais 
> uma boa justificativa para termos um produtório vazio valendo 1!!)
> 
> Bom, para este problema a resposta é conhecida: vale 2^8 = 256.
> Pronto, são 256 números.
> 
> Abraços,
> Bernardo Costa
> 
> 
> On Tue, 20 Jul 2004, David M. Cardoso wrote:
> 
> > 
> > Droga droga droga !!!
> > Na pressa, errei o enunciado da questão!
> > Mil desculpas!
> > 
> > Segue o enunciado correto:
> > 
> > "Quantos inteiros existem que não são divisíveis por 
> qualquer que seja 
> > o primo maior que 20 e não são divisíveis pelo quadrado de qualquer 
> > que seja o primo?"
> > 
> > Puxa vida... tenho prova amanha cedo, vou tentar tirar 
> minhas duvidas 
> > de ultima hora, tenho a sorte de voces existirem e ainda erro o 
> > enunciado da questao... :~(
> > 
> > []'s
> > David
> > 
> > > -Mensagem original-
> > > De: [EMAIL PROTECTED]
> > > [mailto:[EMAIL PROTECTED] Em nome de Bruno 
> França dos Reis 
> > > Enviada em: terça-feira, 20 de julho de 2004 18:53
> > > Para: [EMAIL PROTECTED]
> > > Assunto: Re: [obm-l] Problema de Divisibilidade / Primos
> > > 
> > > -BEGIN PGP SIGNED MESSAGE-
> > > Hash: SHA1
> > > 
> > > On Tuesday 20 July 2004 18:26, David M. Cardoso wrote:
> > > > Mais duas questoes que não consigo me mecher:
> > > >
> > > > Quantos inteiros existem que não são divisíveis por
> > > qualquer que seja
> > > > o primo maior que 20 e não são divisiveis por qualquer que
> > > seja o primo?
> > > 
> > > a) infinitos: 2^n não é divisível por qualquer que seja o primo 
> > > maior que 20, pois é divisível apenas pelo primo 2, qualquer que 
> > > seja n natural.
> > > 
> > > b) apenas o 1, pois qualquer outro número é divisível por 
> ao menos 
> > > um primo:
> > > se ele for composto, sabemos que ele é múltiplo de 
> primos, e se ele 
> > > é primo, ele é divisível por si próprio, um número primo. 
> Já o 1 é 
> > > divisível apenas por 1, que não é primo (e não me venham 
> com essa de 
> > > que 1 é primo também!)
> > > 
> > > acho que é isso!
> > > 
> > > abraço
> > > 
> > > - --
> > > Bruno França dos Reis
> > > brunoreis at terra com br
> > > icq: 12626000
> > > gpg-key: 
> > > http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
> > > 
> > > -BEGIN PGP SIGNATURE-
> > > Version: GnuPG v1.2.4 (GNU/Linux)
> > > 
> > > iD8DBQFA/ZREsHdDIT+qyroRAhQFAKDOZm/uCMp38TYe+uXT2rL+lkNPWQCfWTdb
> > > iMrCfq37UfF/7EZvrP6Qm3g=
> > > =qpSy
> > > -END PGP SIGNATURE-
> > > 
> > > ==
> > > ===
> > > 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
> > 
> ==
> > ===
> > 
> 
> ==
> ===
> 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
=

[obm-l] Morgado e a todos amigos

[nilton rr]

Queridos companheiros preciso dessas respostas até amanhã cedo, vou dar uma aula e fiz os exercicíos e não estou confiando muito nos meus resultados. Obrigado antecipadamente.
1) Quantos são os anagramas da palavra ARARUAMA que têm a letra R no terceiro lugar ou a letra A no quarto lugar
2)De quantos modos distintos posso dispor 6 casais em torno de uma mesa circular de modo que um homem sente-se ao lado de sua esposa e haja dois casais onde as esposas precisam sentar-se uma ao lado da outra?
3)Dezessete livros distintos serão distribuidos entre 5 estudantes. de quantas maneiras diferentes estes livros podem ser distribuidos de modo que 2 destes estudantes recebam 4 livros cada um e os outros 3 estudantes recebam 3 livros cada um?
		Yahoo! Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!

[obm-l] Problema - Primos

[David M. Cardoso]

Mais um problema não resolvido:

"Mostre que um número com 30 dígitos não pode ter mais que 100 fatores
primos."

[]'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
=

[obm-l] Problema - Recorrência / Fibonacci

[David M. Cardoso]

Olá novamente,

Seja F_n a recorrência definida por F_(n+1) = F_n + F_(n-1).
Com F_1 = 1, F_2 = 1, ... (sequencia de fibonacci)

"Qual é o maior: 2^100 ou F_100 ?"

deu pra perceber, testando, que 2^100 é maior.
Ateh porque 2^(n+1) / 2^n = 2
Enquanto que F_(n+1) / F_(n) ~ 1,618 quando n é grande.

Mas não sei formalizar/mostrar que 2^100 é de fato o maior.

[]'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
=

RES: [obm-l] Morgado e a todos amigos

[Guilherme]

Title: Mensagem



Olá, 
Nilton!
 
Vou 
tentar ajudar...
 
1) 
Fazendo todos os anagramas que têm R na terceira posição (fixando-se o R e 
permutando as demais com repetição), fica permutação de 7 elementos com 4 letras 
"A" repetidas = 7!/4! = 210.
Agora 
calcula-se pelo mesmo modo o número de anagramas que têm o "A" na terceira 
posição. Dá 7!/(2!.3!) = 420
Vamos 
calcular agora os que têm o R na terceira e o A na quarta. Dá 6!/3! = 120. Estes 
são os repetidos (foram contados duas vezes). 
O 
resultado final é, então 210 + 420 - 120 = 510.
 
2) Eu 
considerei que "cada homem deve sentar-se ao lado de sua mulher". É essa a 
interpretação? 
Vamos 
lá então. Supondo que M1 e M2 devem sentar-se juntas, os casais H1, M1 e H2 e M2 
podem ser considerados como um só, pois só há as seguintes posições relativas 
para eles: H1M1M2H2 ou H2M2M1H1.
Então, 
devemos fazer a permutação entre os casais "não é suruba ;-) ". P5 = 5! = 120 
(lembrando que considerei os casais 1 e 2 como um só).
Depois, devemos trocar as posições dos homens e mulheres em cada casal, 
incluindo a troca que os casais 1 e 2 podem fazer entre si: P2 . P2 . P2 . P2 . 
P2 = (2!)^5 = 32.
Ainda 
devemos dividir o resultado por 12, para desconsiderar as posições iguais por 
rotação (mesa circular).
O 
resultado final, é, então: 120 . 32 / 12 = 320.
 
3) 
Lembrando que podemos escolher os livros para dar a cada estudante 
seqüencialmente, temos C(17,4) x C(13,4) x C(9,3) x C(6,3) x C(3,3) = 2380 x 715 
x 84 x 20 = 2.858.856.000 maneira distintas!!!
 
Pessoal, por favor verifiquem os resultados!
 
Um 
grande abraço, 
 
Guilherme Marques.
 
 

  
  -Mensagem original-De: 
  [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Em nome de 
  nilton rrEnviada em: terça-feira, 20 de julho de 2004 
  21:30Para: [EMAIL PROTECTED]Assunto: [obm-l] Morgado 
  e a todos amigos
  
  
Queridos companheiros preciso dessas respostas até amanhã cedo, vou dar 
uma aula e fiz os exercicíos e não estou confiando muito nos meus 
resultados. Obrigado antecipadamente.
1) Quantos são os anagramas da palavra ARARUAMA que têm a letra R no 
terceiro lugar ou a letra A no quarto lugar
2)De quantos modos distintos posso dispor 6 casais em torno de uma mesa 
circular de modo que um homem sente-se ao lado de sua esposa e haja dois 
casais onde as esposas precisam sentar-se uma ao lado da outra?
3)Dezessete livros distintos serão distribuidos entre 5 estudantes. de 
quantas maneiras diferentes estes livros podem ser distribuidos de modo 
que 2 destes estudantes recebam 4 livros cada um e os outros 3 
estudantes recebam 3 livros cada um?
  
  
  Yahoo! 
  Mail agora ainda melhor: 100MB, anti-spam e antivírus 
grátis!

RES: [obm-l] Problema - Primos

[David M. Cardoso]

> 
> "Mostre que um número com 30 dígitos não pode ter mais que 
> 100 fatores primos."
> 

Bem.. talvez eu tenha feito, acho que eh soh mostrar que
Piso[Log_10[2^100]+1] = 31
e que portanto 2^100, que é o menor produto de 100 fatores primos, tem 31
dígitos.

[]'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
=

Re: [obm-l] Problema - Primos

[Domingos Jr.]

David M. Cardoso wrote:
Mais um problema não resolvido:
"Mostre que um número com 30 dígitos não pode ter mais que 100 fatores
primos."
o menor número com 100 fatores primos é p_1 * p_2 * ... * p_100
onde p_1, p_2, .. p_100 são os 100 primeiros primos
note que 2, 3, 5, 7 são os únicos primos menores que 10, sendo assim, 96 
dos 100 primeiros primos são maiores que 10, ou seja
p_1 * p_2 * ... * p_100 > 2*3*5*7*10^96

mas 2*3*5*7*10^96 >> 10^30 - 1 = 9...9 (30 dígitos)
se vc permitir primos repetidos o menor valor possível com 100 fatores é 
2^100 > 10^30, pois 100 log2 > 30 log10 e portanto, mesmo permitindo 
primos repetidos,  o enunciado vale.
=
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] Obrigado Guilherme

[nilton rr]

Guilherme muito obrigado pela ajuda e pela sua atenção. Forte abraço.Guilherme <[EMAIL PROTECTED]> wrote:


Olá, Nilton!
 
Vou tentar ajudar...
 
1) Fazendo todos os anagramas que têm R na terceira posição (fixando-se o R e permutando as demais com repetição), fica permutação de 7 elementos com 4 letras "A" repetidas = 7!/4! = 210.
Agora calcula-se pelo mesmo modo o número de anagramas que têm o "A" na terceira posição. Dá 7!/(2!.3!) = 420
Vamos calcular agora os que têm o R na terceira e o A na quarta. Dá 6!/3! = 120. Estes são os repetidos (foram contados duas vezes). 
O resultado final é, então 210 + 420 - 120 = 510.
 
2) Eu considerei que "cada homem deve sentar-se ao lado de sua mulher". É essa a interpretação? 
Vamos lá então. Supondo que M1 e M2 devem sentar-se juntas, os casais H1, M1 e H2 e M2 podem ser considerados como um só, pois só há as seguintes posições relativas para eles: H1M1M2H2 ou H2M2M1H1.
Então, devemos fazer a permutação entre os casais "não é suruba ;-) ". P5 = 5! = 120 (lembrando que considerei os casais 1 e 2 como um só).
Depois, devemos trocar as posições dos homens e mulheres em cada casal, incluindo a troca que os casais 1 e 2 podem fazer entre si: P2 . P2 . P2 . P2 . P2 = (2!)^5 = 32.
Ainda devemos dividir o resultado por 12, para desconsiderar as posições iguais por rotação (mesa circular).
O resultado final, é, então: 120 . 32 / 12 = 320.
 
3) Lembrando que podemos escolher os livros para dar a cada estudante seqüencialmente, temos C(17,4) x C(13,4) x C(9,3) x C(6,3) x C(3,3) = 2380 x 715 x 84 x 20 = 2.858.856.000 maneira distintas!!!
 
Pessoal, por favor verifiquem os resultados!
 
Um grande abraço, 
 
Guilherme Marques.
 
 


-Mensagem original-De: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Em nome de nillton rrEnviada em: terça-feira, 20 de julho de 2004 21:30Para: [EMAIL PROTECTED]Assunto: [obm-l] Morgado e a todos amigos


Queridos companheiros preciso dessas respostas até amanhã cedo, vou dar uma aula e fiz os exercicíos e não estou confiando muito nos meus resultados. Obrigado antecipadamente.
1) Quantos são os anagramas da palavra ARARUAMA que têm a letra R no terceiro lugar ou a letra A no quarto lugar
2)De quantos modos distintos posso dispor 6 casais em torno de uma mesa circular de modo que um homem sente-se ao lado de sua esposa e haja dois casais onde as esposas precisam sentar-se uma ao lado da outra?
3)Dezessete livros distintos serão distribuidos entre 5 estudantes. de quantas maneiras diferentes estes livros podem ser distribuidos de modo que 2 destes estudantes recebam 4 livros cada um e os outros 3 estudantes recebam 3 livros cada um?


Yahoo! Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!
		Yahoo! Mail agora ainda melhor: 100MB, anti-spam e antivírus grátis!

Re: [obm-l] Problema - Recorrência / Fibonacci

[Domingos Jr.]

David M. Cardoso wrote:
Olá novamente,
Seja F_n a recorrência definida por F_(n+1) = F_n + F_(n-1).
Com F_1 = 1, F_2 = 1, ... (sequencia de fibonacci)
"Qual é o maior: 2^100 ou F_100 ?"
deu pra perceber, testando, que 2^100 é maior.
Ateh porque 2^(n+1) / 2^n = 2
Enquanto que F_(n+1) / F_(n) ~ 1,618 quando n é grande.
Mas não sei formalizar/mostrar que 2^100 é de fato o maior.
Você pode provar o resultado por indução para todo n, veja:
para n = 1, 2, F_n = 1 < 2^n
F_{n+1} = F_n + F{n-1} < 2^n + 2^{n-1} = 3*2^{n-1} < 4*2^{n-1} = 2^{n+1}
e o resultado segue por indução.
=
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 - Matemática Discreta

[David M. Cardoso]

Eu não sei em que tópico este problema se enquadra, por isso coloquei no
assunto a disciplina que tem relação com ele. Não consegui fazer:

"Existem (m-1)n + 1 pessoas na sala. Mostre que ou existem m pessoas que não
se conhecem mutuamente, ou existe uma pessoa que conhece pelo menos n
outras."

[]'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
=

[obm-l] RES: [obm-l] Problema - Recorrência / Fibonacci

[David M. Cardoso]

Entendi.. entendi.. obrigado.

[]'s

> -Mensagem original-
> De: [EMAIL PROTECTED] 
> [mailto:[EMAIL PROTECTED] Em nome de Domingos Jr.
> Enviada em: terça-feira, 20 de julho de 2004 23:44
> Para: [EMAIL PROTECTED]
> Assunto: Re: [obm-l] Problema - Recorrência / Fibonacci
> 
> David M. Cardoso wrote:
> 
> >Olá novamente,
> >
> >Seja F_n a recorrência definida por F_(n+1) = F_n + F_(n-1).
> >Com F_1 = 1, F_2 = 1, ... (sequencia de fibonacci)
> >
> >"Qual é o maior: 2^100 ou F_100 ?"
> >
> >deu pra perceber, testando, que 2^100 é maior.
> >Ateh porque 2^(n+1) / 2^n = 2
> >Enquanto que F_(n+1) / F_(n) ~ 1,618 quando n é grande.
> >
> >Mas não sei formalizar/mostrar que 2^100 é de fato o maior.
> >
> Você pode provar o resultado por indução para todo n, veja:
> para n = 1, 2, F_n = 1 < 2^n
> 
> F_{n+1} = F_n + F{n-1} < 2^n + 2^{n-1} = 3*2^{n-1} < 
> 4*2^{n-1} = 2^{n+1}
> 
> e o resultado segue por indução.
> ==
> ===
> 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

[Augusto Cesar de Oliveira Morgado]

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
=

Re: [obm-l] Problema Subconjuntos

[Claudio Buffara]

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

[Helder Suzuki]

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
=