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, [EMAIL PROTECTED] 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, [EMAIL PROTECTED] <[EMAIL PROTECTED]> 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
