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