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

[ghaeser@xxxxxxxxxxxxxx]

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