Desigualdade envolvendo somas parciais (era: [obm-l] Duvida)

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Oi Marcio e membros da lista,

Na verdade, no livro "Mathematical Miniatures", do
Svetoslav Savchev e Titu Andreescu, há uma
generalização do problema:

Os reais positivos a_1, a_2, ..., a_n e b_1 <= b_2 <=
... <= b_n satisfazem as n desigualdades

a_1 <= b_1; a_1 + a_2 <= b_1 + b_2; ...;
a_1 + a_2 + ... + a_n <= b_1 + b_2 + ... + b_n

Então
raiz(a_1) + raiz(a_2) + ... + raiz(a_n) <=
raiz(b_1) + raiz(b_2) + ... + raiz(b_n).

No problema proposto, b_k = k^2.

Vamos à demonstração (que li no livro). Ela usa uma
identidade muito legal que é a soma de Abel: sendo
a_1,a_2,...,a_n e b_1,b_2,...,b_n duas seqüências e
S_k=a_1+a_2+...+a_n, k=1,2,...,n, temos

a_1b_1 + a_2b_2 + ... + a_nb_n = 
S_nb_n + S_1(b_1-b_2) + S_2(b_2-b_3)
+ ... + S_{n-1}(b_{n-1}-b_n)

Essencialmente, é uma integração por partes discreta.

Essa fórmula é muito conveniente quando temos somas
parciais (veja que S_1 = a_1, S_2 = a_1 + a_2, S_3 =
a_1 + a_2 + a_3 são somas parciais!). Mas aplicar
diretamente não leva a uma solução imediata. Primeiro
note que
  raiz(a_k) = raiz(raiz(b_k)*(a_k/raiz(b_k)))
           <= [1/2][raiz(b_k) + a_k/raiz(b_k)]
por médias.

Assim, basta provar que
   a_1/raiz(b_1) + a_2/raiz(b_2) + ... + a_n/raiz(b_n)
<= raiz(b_1) + raiz(b_2) + ... + raiz(b_n).

Aí entra Abel. Sejam S_k = a_1 + a_2 + ... + a_k e T_k
= b_1 + b_2 + ... + b_k. Note que S_k <= T_k para todo
k=1,2,...,n. Aplicando soma de Abel, obtemos
   a_1/raiz(b_1) + a_2/raiz(b_2) + ... + a_n/raiz(b_n)
=  S_n/raiz(b_n) + S_1(1/raiz(b_1)-1/raiz(b_2)) + ...
+
   S_{n-1}(1/raiz(b_{n-1})-1/raiz(b_n))
<= T_n/raiz(b_n) + T_1(1/raiz(b_1)-1/raiz(b_2)) + ...
+
   T_{n-1}(1/raiz(b_{n-1})-1/raiz(b_n))

Revertendo Abel para T_k no lugar de S_k, obtemos
   a_1/raiz(b_1) + a_2/raiz(b_2) + ... + a_n/raiz(b_n)
<= b_1/raiz(b_1) + b_2/raiz(b_2) + ... + b_n/raiz(b_n)
 = raiz(b_1) + raiz(b_2) + ... + raiz(b_n).

Legal, né?

[]'s
Shine

--- Marcio Cohen <marciocohen@superig.com.br> wrote:
> Oi Luiz!
> Você trocou o sinal das desigualdades, essa solução
> está errada..
> Segue uma solucao absurdamente feia (mas
> aparentemente correta) para o 
> problema (desafio qualquer um a achar uma solução
> mais feia :))
> 
> Problema: a<=1^2,  a+b<=1^2+2^2, 
> a+b+c<=1^2+2^2+3^2, 
> a+b+c+d<=1^2+2^2+3^2+4^2 =>
>      sqrt(a)+sqrt(b)+sqrt(c)+sqrt(d)<=1+2+3+4
> 
> Solução:
>    Para a,b,c fixos, ponha x = d e analise f(x) = 
> sqrt(a)+sqrt(b)+sqrt(c)+sqrt(x), 0<=x<=30-a-b-c.
> Essa eh uma funcao 
> crescente, e portanto seu máximo ocorre quando x =
> 30-a-b-c, i.e, 
> a+b+c+d=30.
>    Agora troque c por x. Para a,b fixados, voce tem
> 0<=x<=14-a-b, d=30-x-a-b 
> e olhando para
>      g(x) = sqrt(a)+sqrt(b)+sqrt(x)+sqrt(30-x-a-b),
>      2g'(x) = 1/sqrt(x) -1/sqrt(30-x-a-b)
>     Observe que g eh crescente de x=0 ateh
> x=15-(a+b)/2. Como a+b>0, 
> 14-(a+b) < 15-(a+b)/2 e portanto o máximo dentro da
> restrição ocorre quando 
> x=14-(a+b), i.e, a+b+c=14 e portanto d = 16.
>     Agora voce tem um novo problema.. Basta mostrar
> que
>     a<=1^2,  a+b<=1^2+2^2, a+b+c<=1^2+2^2+3^2 => 
> sqrt(a)+sqrt(b)+sqrt(c)<=1+2+3
>     Pronto, é só repetir o raciocínio para concluir
> que c=9, b=4 e a=1 dão o 
> valor máximo da soma pedida.
> 
> Obs: Essa demonstração não pode ser adaptada
> fielmente para uma versão desse 
> problema com 5 letras. Ficam então duas perguntas:
> Qual o maior valor de n 
> tal que a_1+...+a_k <=1^2+...+k^2 para k=1,2,..,n
> sempre implica 
> sqrt(a1)+...+sqrt(an)<=1+2+...+n?
> 
> 
> 
> ----- Original Message ----- 
> From: "Luiz Felippe medeiros de almeida"
> <luiz.felippe@gmail.com>
> To: <obm-l@mat.puc-rio.br>
> Sent: Thursday, April 21, 2005 10:46 PM
> Subject: Re: [obm-l] Duvida
> 
> 
> > Olá Fernado , acho q consegui fazer o problema que
> vc pediu. Lá vai:
> > a<=1
> > a+b<=5  ==> b<=5-a ==> b<=4 ==> sqrt(b)<=2
> > a+b+c<=14 ==> c<= a+b ==> c<= 14-4-1 ==>sqrt(c)<=3
> > a+b+c+d<=30 ==> d<=30-a-b-c==> d<=30-1-4-9 =>
> sqrt(d)<=4
> > Logo somando todas as equações temos :
> >   sqrt(a) + sqrt(b) + sqrt(c) + sqrt(d) <=10
> >  Abraço
> > Luiz Felippe Medeiros
> >
> > On 4/21/05, Fernando <goianinho_@terra.com.br>
> wrote:
> >>
> >> a <= 1
> >> a+b <= 5
> >> a+b+c <= 14
> >> a+b+c+d <= 30
> >> Prove: sqrt(a)+sqrt(b)+sqrt(c)+sqrt(d) <= 10
> >>
> >> Desde ja agradeço
> >> []'s
> >
> >
>
=========================================================================
> > 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
> >
>
=========================================================================
> >
> > 
> 
> 
>
=========================================================================
> 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
>
=========================================================================
> 

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
=========================================================================
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
=========================================================================