Re: [obm-l] Parcelas de 1998

[Faelccmm@xxxxxxx]

Olá !

As passagens de sua explicação que não entendi foram:

p1) Bom, agora temos um passo de "indução" que funciona muito bem: Suponha
que você tenha numa soma um a_k que seja maior do que 4. Ele pode ser
decomposto em b_1 + b_2, com produto maior do que a_k, e assim esta
não é a soma cujo produto dos termos é máximo. Então, a soma tem
apenas termos entre {1, 2, 3, 4} 


p2) Uma outra maneira de fazer a "tacada final" (que é o mais fácil...)
seria resolver o problema de maximizar 2^x * 3^y restrito a 2x + 3y =
1998. Bom, isto é equivalente (tire o log) a maximizar x*log(2) +
y*log(3), com restrição linear em x e y também. Ora, você sabe que
este problema tem solução no bordo (mas você pode fazer as contas,
nada te impede... substitua x na segunda equação, e mãos à obra), e
basta tentar o bordo, que são as soluções com x mínimo e as com y
mínimo.





Em uma mensagem de 15/10/2004 18:40:54 Hora padrão leste da Am. Sul, bernardofpc@gmail.com escreveu:


> Bom, a talvez isso fique simples se você considerar um problema com um
> número menor: escreva 10 como soma de números naturais a_i tais que
> seu produto seja o maior possível. A primeira coisa que você pode ver
> é ir aumentanto o número de a_i e vendo no que dá. É imediato que a
> melhor solução com dois caras é 5 + 5, já que (n-x)(n+x) = n^2 - x^2 <
> n^2 (seja n = 10/2).
>
> Esta é a linha-mestra de raciocínio (é a proposição (i)! ), mas ainda
> não está perfeito, pois 11 é ímpar. Para a nossa sorte, temos que a
> melhor decomposição (isto é  (ii)! ) é (n/2+1/2)(n/2-1/2) se temos n
> ímpar.
>
> Bom, agora temos um passo de "indução" que funciona muito bem: Suponha
> que você tenha numa soma um a_k que seja maior do que 4. Ele pode ser
> decomposto em b_1 + b_2, com produto maior do que a_k, e assim esta
> não é a soma cujo produto dos termos é máximo. Então, a soma tem
> apenas termos entre {1, 2, 3, 4} (você não ia ser louco de botar zero,
> claro, então não vem ao caso se zero é natural...). A observação (iii)
> retira o 4 da lista, e em seguida ele retira o 1.
> Falta apenas decidir dentre todos os jeitos de escrever 1998 como soma
> de "2" e "3", qual dá o maior produto. Assim, temos que ele elimina a
> possibilidade de "2+2+2", pois o produto destes é 8, enquanto "3+3"
> faz um produto 9. E aí ele divide 1998 por 3 para saber o máximo de
> "3" que pode usar, e descobre que pode ser tudo "3".
>
> Uma outra maneira de fazer a "tacada final" (que é o mais fácil...)
> seria resolver o problema de maximizar 2^x * 3^y restrito a 2x + 3y =
> 1998. Bom, isto é equivalente (tire o log) a maximizar x*log(2) +
> y*log(3), com restrição linear em x e y também. Ora, você sabe que
> este problema tem solução no bordo (mas você pode fazer as contas,
> nada te impede... substitua x na segunda equação, e mãos à obra), e
> basta tentar o bordo, que são as soluções com x mínimo e as com y
> mínimo.
>
> Abraços,
> Bernardo Costa
>
>
> On Fri, 15 Oct 2004 16:50:43 EDT, faelccmm@aol.com <faelccmm@aol.com> wrote:
> > Olá pessoal ! 
> >  
> > Abaixo esta um problema e sua solução. Tive dúvidas em algumas passagens. 
> >  
> > Passagem 01) 
> >  
> > (i) se n (n > 4) é par, temos (n/2)*(n/2) > n 
> > (ii) se n (n > 3) é ímpar, temos ((n-1)/2)*((n+1)/2) > n 
> >  
> > Eu entendi as desigualdades acima, mas não entendo qual a relação dela com o
> > problema. Por que o autor da solução as criou ? 
> >  
> > Passagem 02) 
> >  
> > Com as observações (i) e (ii) devemos ter n_i pertencente a {1, 2, 3, 4} ...
> >  
> > Eu até entendo que (i) U (ii) = (n >= 5), mas não entendi a afirmação acima
> > ?! 
> >  
> > ***************************************************************************************************************************
> > Escreva 1998 como soma de (um número arbitrário de) parcelas 
> > de modo que o produto das parcelas seja o maior possível. 
> >  
> >  
> > SOLUÇAO: 
> >  
> > Observe inicialmente que, dado n pertencente a N, 
> >  
> > (i) se n (n > 4) é par, temos (n/2)*(n/2) > n 
> > (ii) se n (n > 3) é ímpar, temos ((n-1)/2)*((n+1)/2) > n
> > 
> > Sejam 1998 = n_1 + n_2 + n_3 + … n_k e
> > P = n_1*n_2*n_3*n_k
> > 
> > Com as observações (i) e (ii) devemos ter n_i pertencente a {1, 2, 3, 4} e
> > como 4 = 2*2
> > podemos substituir 4 por "2 + 2" e teremos n_i pertencente a {1, 2, 3} logo
> > P = [1^(alfa)]*[2^(beta)]*[3^(gama)]. É evidente que alfa = 0, pois se alfa
> > = 1, "1+2" pode ser substituído por um 3 e "1 + 3" pode ser substituído por
> > "2 + 2". Também beta =< 2, pois "2 + 2 + 2" pode ser substituído por "3 +3"
> > ( 3*3 > 2*2*2) e conseqüentemente 
> > P = [2^(beta)]*[3^(gama)] com (beta = 1 ou 2). Como 1998 = 3*666 + 0, 
> > P = 3^666 e S = 3 + 3 + 3 + 3 +...+ 3 (666 vezes) 
> >  
> >  
>
>
> -- 
> Bernardo Freitas Paulo da Costa