[obm-l] Rearranjo generalizado - revisado

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Oi, Marcio:

Dei uma boa mexida na demonstracao e eliminei aquela passagem nao
justificada. Por favor de uma lida e me diga se ficou algum furo.

O problema:

Sejam varias seqs de termos positivos (a), (b), (c), ...e considere as somas
do tipo S = a_1*b_1*c_1*... +a_2*b_2*c_2* ... + ... a_n*b_n*c_n*... onde
(a_i) eh uma permutacao da 1a sequencia, (b_i) uma permutacao da 2a, e assim
por diante.
    Mostre que S é máxima quando as sequencias tem a mesma ordenacao.
    O caso com 2 sequencias eh o que se conhece como "desigualdade do
rearranjo"

-----------

Inducao sobre o numero M de sequencias (M >= 2):
 
O caso base (M = 2) eh a desigualdade do rearranjo.

Supondo que o resultado seja verdadeiro para quaisquer M-1 sequencias (M >=
3) de termos positivos, consideremos as M sequencias (A_i), (B_i), (C_i),
..., (Z_i) (achei melhor usar esta notacao do que dois indices) de termos
positivos e as somas correspondentes do tipo:
S = A_1*B_1*...*Z_1 + ... + A_n*B_n*...*Z_n

Inicialmente, aplicamos a hipotese de inducao as M-1 sequencias (A_i*B_i),
(C_i), ..., (Z_i) e concluimos que S eh maxima quando todas estas as
sequencias tem a mesma ordenacao, digamos:
0 < A_1*B_1 <= ... <= A_n*B_n,
0 < C_1 <= ... <= C_n,
...
0 < Z_1 <= ... <= Z_n.

O objetivo agora eh provar que:
0 < A_1 <= ... <= A_n  e  0 < B_1 <= ... <= B_n

Suponhamos, portanto, que este nao seja o caso.
Sem perda de generalidade podemos supor que existem i, j tais que:
1 <= i < j <= n  e  A_i > A_j.

Nesse caso, como A_i*B_i <= A_j*B_j, teremos que B_i < B_j, o que,
juntamente com as outras desigualdades decorrentes da h.i., implica que:
B_i*...*Z_i < B_j*...*Z_j.

Agora, vamos calcular o valor da soma S1, a qual eh obtida de S pela
permutacao de A_i e A_j (todos os demais termos ficam iguais). Assim:

S1 = S - A_i*B_i*...*Z_i - A_j*B_j*...*Z_j + A_j*B_i*...*Z_i +
A_i*B_j*...*Z_j ==>

S1 = S + (A_i - A_j)*(B_j*...*Z_j - B_i*...*Z_i)

Como A_i > A_j e B_j*...*Z_j > B_i*...*Z_i, temos que S1 > S.

Ou seja, colocando em ordem crescente dois termos originalmente "fora de
ordem" da sequncia (A_i), conseguimos aumentar o valor da soma. O mesmo
raciocinio vale para eventuais termos "fora de ordem" da sequencia (B_i).

Portanto, a soma eh maxima quando (A_i) e (B_i) estao em ordem crescente.

Em virtude da h.i., podemos concluir que S eh maxima quando:
0 < A_1 <= ... <= A_n,
0 < B_1 <= ... <= B_n,
0 < C_1 <= ... <= C_n,
...
0 < Z_1 <= ... <= Z_n,
ou seja, quando as M sequencias tiverem a a mesma ordenacao.

FIM


Um abraco,
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>
=========================================================================