Re: [obm-l] Re: [obm-l] Subconjuntos de {1,2,...,2n}

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Certamente indução funciona e mata o problema, que é o que interessa.

No entanto, o que eu tinha em mente era algo utilizando o princípio das
gavetas (ou das casas de pombos). Por exemplo, no problema de provar que
qualquer subconjunto de {1, 2, ..., 2n} com n+1 elementos contém dois
números primos entre si, as soluções apresentadas foram baseadas na idéia de
decompor { 1, ..., 2n } em n "gavetas":
{1, 2}, {3, 4}, ..., {2n-3,2n-2}, {2n-1,2n}
nas quais deveriam ser colocadas n+1 "meias", de forma que alguma gaveta
necessariamente teria de conter 2 "meias", ou seja, 2 inteiros positivos
consecutivos e, portanto, primos entre si.

Vale a pena tentar descobrir quais seriam as n "gavetas" para este problema.

Um abraço,
Claudio.

----- Original Message -----
From: <ghaeser@zipmail.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Thursday, January 23, 2003 1:49 AM
Subject: [obm-l] Re: [obm-l] Subconjuntos de {1,2,...,2n}


>Um problema parecido, mas um pouco mais difícil, é o seguinte:
>Provar que qualquer subconjunto T com n+1 elementos de S = {1, >2, ...,
2n } contém dois números distintos x,y tais que um é >múltiplo do outro.

vamos tentar por indução:

base: n=1
S={1,2}
T={1,2}
x=1, y=2.

hip (caso n):
dado S={1,2,..,2n}, entao em qualquer subconjunto T de S tal que |T|=n+1,
existem x,y tal que y=k.x para algum k natural.

passo (caso n+1):
S={1,2,..,2n,2n+1,2n+2}

preciso provar que em qualquer subconjunto T de S, tal que |T|=n+2, existem
x,y tq y=k.x para algum k natural.

se 2n+1 e 2n+2 nao pertencem a T, basta remover um elemento qualquer de
T e aplicar a hipótese de indução para obter x e y.

se 2n+1 ou 2n+2 (ou exclusivo) nao pertencem a T, entao remova este elemento
e a hipótese de indução faz o serviço.

se 2n+1 e 2n+2 pertencem a T :

se n+1 pertence a T entao x=n+1, y=2n+2

se n+1 nao pertence a T entao seja:
T'=T\{2n+1,2n+2}U{n+1}.

T' satisfaz a hipótese, entao basta aplicá-la para obter x,y.

se x e y sao diferentes de n+1 então é pq existe x e y em T.
se y=n+1 entao como 2n+2 é multiplo de n+1, tome y=2n+2. e teremos x e y
pertencentes a T, tal que y=k.x
(note que n+1 nunca pode ser o x pois não existe multiplo de n+1 em
{1,2,..,2n}).

o que demonstra o que queríamos.

Gabriel Haeser
www.gabas.cjb.net


"Mathematicus nascitur, non fit"
Matemáticos não são feitos, eles nascem
---------------------------------------
Gabriel Haeser
www.gabas.cjb.net


------------------------------------------
Use o melhor sistema de busca da Internet
Radar UOL - http://www.radaruol.com.br



=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================