Re: [obm-l] Problema interessante

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

Essa tecnica e muito boa de se aplicar em problemas!!!Tem o da Eureka 8 que o Humberto resolveu,a Cone Sul e talvez um da IMO.

 Cl�udio_(Pr�tica) <claudio@praticacorretora.com.br> wrote:

Oi, JG:

Legal! Usa a mesma id�ia b�sica que a minha, mas voc� chega l� por uma rota
diferente.
Acho que essa id�ia de particionar o conjunto {1,2,...,2n} de duas forma
distintas pode ser usada em v�rias ocasi�es.
� uma t�cnica boa de se ter no repert�rio.

Um abra�o,
Claudio.

----- Original Message -----
From: "Jo�o Gilberto Ponciano Pereira"
To:
Sent: Thursday, February 27, 2003 10:50 AM
Subject: RE: [obm-l] Problema interessante


> "Tome uma parti��o QUALQUER de {1,2,...,2n} em dois conjuntos A e B com n
> elementos cada. Ponha os elementos de A em ordem crescente a_1<...os
> de B em ordem decrescente b_1>...>b_n. Prove que:
>
> |a_1-b_1| + ... + |a_n-b_n| = n^2"
>
> Acabei esquecendo de mandar a resposta, mas aqui vai ela, espero que em
> tempo....
>
> Vamos chamar os conjuntos:
> x = {1 a n} e y={n+1 a 2n}
>
> Vamos supor que o conjunto A � formado de tal forma que possua m elementos
> de Y e n-m elementos de X. Logo, o conjunto B � obrigatoriamente formado
por
> m elementos de x e n-m elementos de Y.
>
> Ent�o podemos considerar que:
> RESULTADO = |a_1-b_1| + ... + |a_n-b_n| = (a1 - b1) + (a2 - b2) + ... +
(am
> - bm) - ((am+1 - bm+1) + ... +(an - bn))=
> soma a (1 a m) - soma b(1 a m) - soma a(m+1 a n) + soma b(m+1 a n)
>
> Se voltarmos a suposi��o inicial, soma a (1 a m) + soma b(m+1 a n) � a
soma
> dos elementos do conjunto Y, e soma b(1 a m) + soma a(m+1 a n) � a soma
dos
> elementos de X.
>
> Logo, temos que:
> RESULTADO = soma(n+1 a 2n) - soma(1 a n) = n*n + soma(1 a n) - soma(1 a n)
> =n^2
>
> -----Original Message-----
> From: Cl�udio (Pr�tica) [mailto:claudio@praticacorretora.com.br]
> Sent: Monday, February 24, 2003 2:48 PM
> To: obm-l@mat.puc-rio.br
> Subject: [obm-l] Problema interessante
>
>
>
> Ta� um resultado inesperado (pelo menos pra mim):
>
> Tome uma parti��o QUALQUER de {1,2,...,2n} em dois conjuntos A e B com n
> elementos cada. Ponha os elementos de A em ordem crescente a_1<...os
> de B em ordem decrescente b_1>...>b_n. Prove que:
>
> |a_1-b_1| + ... + |a_n-b_n| = n^2.
>
> Um abra�o,
> Claudio.
>
> =========================================================================
> 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 �
> =========================================================================

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

---

Busca Yahoo! 
O servi�o de busca mais completo da Internet. O que voc� pensar o Yahoo! encontra.