Re: [obm-l] ajuda !!

["Bruno F. C. Leite" <bruleite@xxxxxxxxxxxx>]

At 13:21 25/08/02 +0000, you wrote:
>olá!
>
>>   ei, como faço pra estimar a qnt. de dígitos de 4444^4444 ?
>>(e pq q eh menor q 4*4444 ?)
>
>--> bem, realmente eh facil ver q 4444^4444 tem menos q
>4*4444 +1 digitos, pois 10^4 >4444, mas ainda fica uma aproximação ruim 
>(apesar de q com essa estimativa dê pra fzer o problema), dai tentei fzer 
>4444<10^4/2 => 4444^4444<10^4*4444/2^4444, daí usando log2=0,301 (acho q 
>eh isso)  pode-se ter uma aproximação melhor eu acho, mas como melhorar 
>mais um pouco esta aproximação? e como saber se a aproximação q temos eh 
>suficiente pra resolver a questão??
>
>   aproveitando a deixa, como provo q se x1>=x2>=...>=xn e
>y1>=y2>=...>=yn , e zi uma permutação de yi (i=1,...,n), então
>sum(xiyi)>=sum(xizi) (i=1,...,n) ???

Oi,

Esssa é a desigualdade do rearranjo. Tem numa eureka, eu acho que 5 ou 6. 
(veja o artigo de desigualdades) Deve ter também o artigo avulso no site da 
eureka.

tem um raciocínio que ilustra essa desigualdade. Suponha que você tem 3 
caixas: uma com notas de $100, outra com notas de $10 e outra com notas de 
$1. Suponha que você pode pegar 30 de uma caixa, 20 de outra e 7 de outra, 
mas você pode escolher em qual vc pega 30, em qual vc pega 20, etc. O que 
vc faz?

Bem, é claro que você vai ordenar os dois (100>10>1) e (30>20>7) e pegar 
30*100+10*20+7*1...

Pegue a soma máxima S entre todas as possiveis somas sum(xi zi). Queremos 
provar que i<j implica z_i>=z_j. Suponha que não, temos i<j e z_i<z_j. Seja 
S' a soma que você obtém trocando z_i e z_j de lugar. Mostre que S'>S, o 
que será absurdo.

Bruno Leite
http://www.ime.usp.br/~brleite



>  thanks!
>  fê!
>
>
>_________________________________________________________________
>Converse com seus amigos online, faça o download grátis do MSN Messenger: 
>http://messenger.msn.com.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>
>=========================================================================

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