RE: [obm-l] Problema interessante

[João Gilberto Ponciano Pereira <jopereira@xxxxxxxxxxxxx>]

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