[obm-l] Re: [obm-l] Re: [obm-l] Dúvida???

[ghaeser@xxxxxxxxxxxxxx]

Seja S={1,2,..,2n}

em qualquer subconjunto T de S, tq |T|=n+1, existem x e y tq 
mdc(x,y)=1

dem: indução em n.

base:
n=1
S={1,2}
T={1,2}

x=1, y=2

hip: existe x e y , se S={1,2,..,2n} e |T|=n+1, T subconj. de S.

passo:

seja S={1,2,..,2n,2n+1,2n+2}

se 2n+1 e 2n+2 nao pertencem a T, |T|=n+2 então basta remover um elemento
qualquer de T e aplicar a hipótese de indução.

se 2n+1 xou 2n+2 pertencem a T, |T|=n+2 então basta remover este elemento
e aplicar a hipótese de indução

se 2n+1 e 2n+2 pertencem a T então x=2n+1, y=2n+2.

>>       Por que podemos garantir que em qualquer subconjunto com n + 1
>>     elementos do conjunto {1, 2, 3, ..., 2n} existem pelo menos
>>     dois elementos que são primos entre si?
>>
>
>

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