[obm-l] Parcelas de 1998
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) > nSejam 1998 = n_1 + n_2 + n_3 + â n_k eP = n_1*n_2*n_3*n_kCom as observaÃÃes (i) e (ii) devemos ter n_i pertencente a {1, 2, 3, 4} e como 4 = 2*2podemos 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)
Re: [obm-l] Parcelas de 1998
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 = 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 =
Re: [obm-l] Parcelas de 1998
Title: Re: [obm-l] Parcelas de 1998 O enunciado nao diz que as parcelas devem ser inteiras. Com 666 parcelas igaus a 3, o logaritmo do produto serah igual a 731,67578. Por outro lado, se tivermos 734 parcelas iguais a "e" (base dos logaritmos naturais) e uma igual a 1998 - 734*e, o logaritmo do produto serah 735,02286. []s, Claudio. on 15.10.04 18:50, [EMAIL PROTECTED] at [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)
Re: [obm-l] Parcelas de 1998
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, [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
Re: [obm-l] Parcelas de 1998
Claudio, Poderia ser mais claro ? Pois sÃo problemas de nÃvel olÃmpico, resolvi comeÃar a estudar estes tipos de problema -- atravÃs da Eureka -- hà pouco tempo. Em uma mensagem de 15/10/2004 20:03:31 Hora padrÃo leste da Am. Sul, [EMAIL PROTECTED] escreveu: O enunciado nao diz que as parcelas devem ser inteiras. Com 666 parcelas igaus a 3, o logaritmo do produto serah igual a 731,67578. Por outro lado, se tivermos 734 parcelas iguais a "e" (base dos logaritmos naturais) e uma igual a 1998 - 734*e, o logaritmo do produto serah 735,02286. []s, Claudio. on 15.10.04 18:50, [EMAIL PROTECTED] at [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) > nSejam 1998 = n_1 + n_2 + n_3 + Å n_k eP = n_1*n_2*n_3*n_kCom as observaÃÃes (i) e (ii) devemos ter n_i pertencente a {1, 2, 3, 4} e como 4 = 2*2podemos 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)
Re: [obm-l] Parcelas de 1998
Title: Re: [obm-l] Parcelas de 1998 Eu soh disse que, se nao nos restringirmos a parcelas inteiras, 666 parcelas iguais a 3 nao eh a solucao otima. Existe uma solucao cujo produto eh maior, apesar das parcelas serem irracionais. E como estamos tratando de numeros muito grandes, tais como 3^666, eh mais facil comparar os seus logaritmos naturais. []s, Claudio. on 15.10.04 21:15, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote: Claudio, Poderia ser mais claro ? Pois são problemas de nível olímpico, resolvi começar a estudar estes tipos de problema -- através da Eureka -- há pouco tempo. Em uma mensagem de 15/10/2004 20:03:31 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu: O enunciado nao diz que as parcelas devem ser inteiras. Com 666 parcelas igaus a 3, o logaritmo do produto serah igual a 731,67578. Por outro lado, se tivermos 734 parcelas iguais a "e" (base dos logaritmos naturais) e uma igual a 1998 - 734*e, o logaritmo do produto serah 735,02286. []s, Claudio. on 15.10.04 18:50, [EMAIL PROTECTED] at [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 + S 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, 31+22 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)
Re: [obm-l] Parcelas de 1998
Entendi, obrigado ! Em uma mensagem de 15/10/2004 20:47:08 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu: Eu soh disse que, se nao nos restringirmos a parcelas inteiras, 666 parcelas iguais a 3 nao eh a solucao otima. Existe uma solucao cujo produto eh maior, apesar das parcelas serem irracionais. E como estamos tratando de numeros muito grandes, tais como 3^666, eh mais facil comparar os seus logaritmos naturais. []s, Claudio. on 15.10.04 21:15, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote: Claudio, Poderia ser mais claro ? Pois são problemas de nível olímpico, resolvi começar a estudar estes tipos de problema -- através da Eureka -- há pouco tempo.
Re: [obm-l] Parcelas de 1998
Já entendi ! Obrigado ! Em uma mensagem de 15/10/2004 20:09:49 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu: 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.