Re: [obm-l] Teorema do Rearranjo

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Acho que não é difícil demonstrar esse resultado...

considere uma permutação qualquer (i1, ..., i[n])
se i1 != n então i[j] = n para algum j > 1, e trocamos os índices i1 e i[j].
após essa troca nossa soma fica menor ou igual a anterior...
os termos que mudaram foram
a(1)*b(i1) <-> a(1)*b(n)
a(j)*b(n) <-> a(j)*b(i1)

a(1)*b(i1) + a(j)*b(n) - a(1)*b(n) - a(j)*b(i1) =
b(i1)*[a(1) - a(j)] + b(n)*[a(j) - a(1)] = [a(j) - a(1)] * [b(n) - b(1)] >=
0

repita o argumento, agora verificando se i2 = n-1 e assim
consecutivamente...

pra verificar o limitante superior o esquema é análogo.

> Sejam a(1), a(2), ..., a(n)  e b(1), b(2), ..., b(n) duas sequências de
> números reais (não necessariamente positivos).
> Suponhamos que: a(1) <= a(2) <= ... <= a(n)  e  b(1) <= b(2) <= ... <=
b(n)
> Seja (i_1, i_2, ..., i_n) uma permutação qualquer de (1, 2, ..., n).
> Então:
> a(1)*b(n) + a(2)*b(n-1) + ... + a(n)*b(1) <= a(1)*b(i_1) + a(2)*b(i_2) +
...
> + a(n)*b(i_n)
> e
> a(1)*b(i_1) + a(2)*b(i_2) + ... + a(n)*b(i_n) <= a(1)*b(1) + a(2)*b(2) +
...
> + a(n)*b(n)

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