Re: [obm-l] Rearranjo generalizado - revisado

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   Oi pessoal,
   A gente discutiu esse problema hoje no treinamento do IMPA. A solucao do
Claudio parece muito com a do Alex. A minha e' um pouco diferente, e segue
dos seguintes lemas (as provas sao faceis e deixo como exercicio):
Def: (a_1,a_2,...,a_n)<<(b_1,b_2,...,b_n) se para todo k<=n,
a_k+a_(k+1)+...+a_n<=b_k+b_(k+1)+...+b_n.
Lema 1: dadas duas permutacoes (i1,i2,...,in) e (j1,j2,...,jn) de
(1,2,...,n) e duas sequencias nao-decrescentes (a_1,a_2,..,a_n) e
(b_1,b_2,...,b_n) temos
(a_i1.b_j1,a_i2.b_j2,...,a_in.b_jn)<<(a_1.b_1,a_2.b_2,....,a_n.b_n).
Lema 2: se (a_1,a_2,...,a_n)<<(b_1,b_2,...,b_n) e (c_1,c_2,...,c_n) e' uma
sequencia nao-decrescente entao
(c_1.a_1,c_2.a_2,...,c_n.a_n)<<(c_1.b_1,c_2.b_2,...,c_n.b_n).
     Esses lemas implicam um resultado um pouco mais forte: a sequencia dos 
produtos com todas as sequencias na ordem certa e' maxima na ordem <<.
     Abracos,
             Gugu

P.S.: As sequencias acima sao todas positivas. Vale a pena notar que o
resultado com duas sequencias vale mesmo sem supor que os termos sao
nao-negativos, mas em geral precisamos disso (como mostra o exemplo das
sequencias (-1,-1,1),(-1,-1,1),(-1,-1,1)).

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

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