Re: [obm-l] Problema interessante

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

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" <jopereira@vesper.com.br>
To: <obm-l@mat.puc-rio.br>
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<...<a_n e
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<...<a_n e
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 é <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>
=========================================================================