[obm-l] Re: [obm-l] Fatoração de 5^1985 - 1.
Caros Fabrício e Nehab, Achar um fator foi fácil, o problema foi quebrar o quociente nos outros dois. Fiz assim: 5^1985 - 1 = (5^397)^5 - 1 Seja x = 5^397. Então queremos fatorar x^5 - 1 que, de imediato, resulta em (x - 1) (x^4 + x^3 + x^2 + x + 1), ou seja, um dos fatores é 5^397 - 1. Falta fatorar x^4 + x^3 + x^2 + x + 1 de uma forma conveniente. Após um tempinho (pouca coisa, até no Fla x Flu no Maracanã estava rabiscando...), tive a idéia de tentar escrever a expressão como uma adequada diferença de dois quadrados. Caso conseguisse, o problema estaria resolvido, pois um fator seria a soma e outro, a diferença. Arbitrei o primeiro quadrado como (x^2 + ax + 1)^2, que já geraria o termo de quarto grau e o termo independente corretos. E coloquei o segundo quadrado como 5x(x+b)^2, pois como x = 5^397, 5x = 5^398 seria um quadrado perfeito. Igualando as expressões (e rezando para encontrar valores de a e b compatíveis), veio: (x^2 + ax + 1)^2 - 5x(x+b)^2 = x^4 + (2a -5)x^3 + (a^2 - 10b + 2)x^2 + (2a - 5b^2)x + 1 = x^4 + x^3 + x^2 + x + 1 Assim: 2a -5 = 1 = a = 3 a^2 - 10b + 2 = 1 = b = 1 Agora era hora da onça beber água: 2a - 5b^2 = 1 Mas a = 3 e b = 1 satisfazem ! Eureka ! x^4 + x^3 + x^2 + x + 1 = (x^2 + 3x + 1)^2 - 5x(x+1)^2 Substituindo x por 5^397: ((5^397)^2 + 3*5^397 +1)^2 - 5*5^397*(5^397 + 1)^2 = = ((5^397)^2 + 3*5^397 +1)^2 - 5^398*(5^397 + 1)^2 (diferença de quadrados) = = (((5^397)^2 + 3*5^397 +1) - 5^199*(5^397 + 1)) * (((5^397)^2 + 3*5^397 +1) + 5^199*(5^397 + 1)) (produto da diferença pela soma) = = (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397 + 5^199 + 1) Os três fatores são claramente maiores que 5^100, conforme solicitado. Então: 5^1985 -1 = (5^397 - 1) * (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397 + 5^199 + 1) Como já são três da manhã e já perdi o sono mesmo, resolvi fazer umas continhas de cabeça, tal como o Ralph fez outro dia desses... 5^397-1 = 2 x 2 x 1.043.801.929 x 7.768.438.039 x C258 5^794 -5^596 + 3*5^397 - 5^199 + 1 = 71 x 399.091.951.801 x C542 5^794 + 5^596 + 3*5^397 + 5^199 + 1 = 11 x 146.891 x C549 Logo: 5^1985 -1 = 2 x 2 x 11 x 71 x 146.891 x 1.043.801.929 x 7.768.438.039 x 399.091.951.801 x C258 x C542 x C549 (onde Cn são números compostos de n algarismos). A fatoração de C258, C542 e C549 fica como exercício ... :) Abraços, Vidal. P.S. Nehab: Apesar de não nos conhecermos pessoalmente, temos um grande amigo em comum: o Manuel Martins Filho, professor de Informática da Carioca ! Abraços ! :: vi...@mail.com *** 2009/4/5 Carlos Nehab ne...@infolink.com.br Oi, gente, Fabricio postou este interessante problema e aparentemente ninguém deu muita bola, talvez achando que é óbvio. Não achei óbvio não. Quem resolveu? Abraços, Nehab fabrici...@usp.br escreveu: Caros colegas, mexendo em algumas listas antigas de exercícios, um me chamou muito a atenção. Pede pra fatorar 5^1985 - 1 num produto de três inteiros maiores que 5^100. Pra facilitar um possível avanço, 1985 pode ser escrito como 5 x 397 (ambos primos). . = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html=
[obm-l] Re: [obm-l] Re: [obm-l] Método De Newton
Bernardo, valeu mesmo.Não fui eu quem formulou a pergunta, muito interessante
por sinal.
Escrevo para parabenizá-lo, acima de tudo pela sua atenção, da a questão
formulada pelo denisson .Tudo muito detalhado,legal mesmo.Todos aprendemos.
Um abraço
paulo Barclay
--- Em dom, 5/4/09, Bernardo Freitas Paulo da Costa bernardo...@gmail.com
escreveu:
De: Bernardo Freitas Paulo da Costa bernardo...@gmail.com
Assunto: [obm-l] Re: [obm-l] Método De Newton
Para: obm-l@mat.puc-rio.br
Data: Domingo, 5 de Abril de 2009, 7:48
2009/4/5 Denisson denisso...@gmail.com:
Estava relendo sobre o método de newton e a demonstração fala que numa
vizinhança suficientemente próxima da raiz o método converge. Implementei o
algoritmo em um computador e o polinômio x^2 + 3x + 2 por exemplo de raizes
-1 e -2 ao tomar uma aproximação inicial de valor 10 ele encontra a raiz
-1. Pergunto o que caracteriza exatamente esse intervalo suficientemente
próximo.
Bom, isso é realmente um problema da demonstração (e provavelmente
de todas as demonstrações que dizem suficientemente pequeno ou
suficientemente grande). Mas acho que não tem jeito melhor de fazer.
Deixa eu explicar o que eu quero dizer:
Se você leu a demonstração, o cara precisa de duas hipóteses sobre os
valores da derivada de f (uma para f', outra para f'', se a memória
não falha), para garantir que o próximo ponto está mais próximo da
raiz do que o atual. Para isso, o cara usa a continuidade de f, f' e
f'', o que é um método bastante geral para obter que a função não
varia muito, mas em compensação, o resultado que ele dá é somente o
suficientemente pequeno que você encontrou, e ainda por cima, a
continuidade não te dá o tamanho desse intervalo. Assim, ele diz
apenas suficientemente pequeno, existe, e o matemático está contente.
Agora, você quer implementar o algoritmo, e gostaria que saber quando
ele funciona. Muito bem, basta reler a demonstração e ver quais são
*exatamente* as hipóteses que a prova exige para a convergência. Se
você lembra do algoritmo de escolha do próximo ponto, temos a_{n+1} =
a_n - f(a_n) / f'(a_n), e a gente testa a convergência usando o único
critério disponível, ou seja, o de Cauchy, e para isso temos que
tentar calcular (a_{n+2} - a_{n+1}) / (a_{n+1} - a_n) e ver se dá um
comportamento de série geométrica. Com a fórmula, isso quer dizer que
é pra calcular f(a_{n+1}) / f(a_n) * f'(a_n) / f'(a_{n+1}). Agora, use
uma aproximação de segunda ordem para a função perto de a_n, ou seja,
diga que f(a_n + x) = f(a_n) + f'(a_n)x + f''(a_n)x^2/2 + erro
pequenininho, e vamos estimar f(a_{n+1}) / f(a_n). Pela definição do
a_{n+1} (lembre da reta tangente batendo no zero !), a distância do
a_{n+1} ao a_n é tal que os dois primeiros termos de taylor
desaparecem, resta portanto só o último, que vale f''(a_n)/2 *
(a_{n+1} - a_n)^2 = f''(a_n)/2 * f(a_n)^2 / f'(a_n)^2. Assim, o
quociente a gente pode estimar com f(a_{n+1}) / f(a_n) ~= f''(a_n)/2 *
f(a_n) / f'(a_n)^2. Daí, resta estimar o quociente das derivadas, e se
eu não me engano, a demonstração simplesmente exige que a f' esteja no
intervalo [a, A], com 0 a A, e portanto o quociente é no máximo
A/a que é limitado. Daí, se você começar suficientemente perto, o erro
é menor do que f(a_n) * (f''(a_n)/2 / f'(a_n)^2) * A/a e isso tudo
será menor do que 1 (pro critério de Cauchy, lembra ?) bastando que a
f''(a_n) seja limitada, e que f(a_n) seja muuuito pequeno (ou
seja, isso é o suficientemente perto da raiz em questão). Bom, isso
é o primeiro passo.
Agora, vamos ver o teu exemplo ! Você pegou um polinômio do segundo
grau para testar, portanto, só pra início de conversa, a f''(x) é
limitada *na reta toda* ! O que já é uma boa mão na roda na hora de
fazer o algoritmo convergir. Se você refizer as contas que eu dei,
simplificando quando puder, vai dar pra ver que o quociente entre as
diferenças sucessivas (o que a gente tem que calcular no critério de
Cauchy) é f(a_n) * f''(a_n) / 2( f'(a_n) * f'(a_{n+1}) = Constante *
f(a_n) / ( f'(a_n) f'(a_{n+1} ) . Desenvolvendo mais uma vez por
Taylor (no denominador agora, a gente quase nunca usa isso na prova
porque não precisa, mas no teu caso é legal ver no que dá), a gente
obtém um treco que é aproximadamente (veja que, na verdade, é
exatamente, porque a aproximação de Taylor de ordem 2 de um polinômio
de ordem dois é *exata* !)
f(a_n) * f''(a_n) / 2 ( f'(a_n) ^2 - f(a_n)*f''(a_n) )
e substituindo o polinômio, você vai ver que dá sempre menor do que 1,
exceto quando você começa entre as raízes. Isso tem também uma
explicação geométrica : como a função é convexa, o método sempre
aproxima quando você está depois das raízes (esse é um excelente
exercício pra você ver que você entendeu direitinho o método !), mas
pode se afastar quando você começa entre. Aliás, a melhor maneira de
tentar começar a solução é justamente fazer o desenho !
O segundo ponto, o que acontece no método quando você toma como aproximação
inicial exatamente a média entre duas
Re: [obm-l] Re: [obm-l] Fatoração de 5^1985 - 1.
Vidal, muito boa a sacada. Eu tinha tentado escrever como o produto de dois polinômios de grau 2, sem sucesso. Parabéns pela solução. Um abraço. . On Apr 6, 2009, at 03:21 , *Vidal wrote: Caros Fabrício e Nehab, Achar um fator foi fácil, o problema foi quebrar o quociente nos outros dois. Fiz assim: 5^1985 - 1 = (5^397)^5 - 1 Seja x = 5^397. Então queremos fatorar x^5 - 1 que, de imediato, resulta em (x - 1) (x^4 + x^3 + x^2 + x + 1), ou seja, um dos fatores é 5^397 - 1. Falta fatorar x^4 + x^3 + x^2 + x + 1 de uma forma conveniente. Após um tempinho (pouca coisa, até no Fla x Flu no Maracanã estava rabiscando...), tive a idéia de tentar escrever a expressão como uma adequada diferença de dois quadrados. Caso conseguisse, o problema estaria resolvido, pois um fator seria a soma e outro, a diferença. Arbitrei o primeiro quadrado como (x^2 + ax + 1)^2, que já geraria o termo de quarto grau e o termo independente corretos. E coloquei o segundo quadrado como 5x(x+b)^2, pois como x = 5^397, 5x = 5^398 seria um quadrado perfeito. Igualando as expressões (e rezando para encontrar valores de a e b compatíveis), veio: (x^2 + ax + 1)^2 - 5x(x+b)^2 = x^4 + (2a -5)x^3 + (a^2 - 10b + 2) x^2 + (2a - 5b^2)x + 1 = x^4 + x^3 + x^2 + x + 1 Assim: 2a -5 = 1 = a = 3 a^2 - 10b + 2 = 1 = b = 1 Agora era hora da onça beber água: 2a - 5b^2 = 1 Mas a = 3 e b = 1 satisfazem ! Eureka ! x^4 + x^3 + x^2 + x + 1 = (x^2 + 3x + 1)^2 - 5x(x+1)^2 Substituindo x por 5^397: ((5^397)^2 + 3*5^397 +1)^2 - 5*5^397*(5^397 + 1)^2 = = ((5^397)^2 + 3*5^397 +1)^2 - 5^398*(5^397 + 1)^2 (diferença de quadrados) = = (((5^397)^2 + 3*5^397 +1) - 5^199*(5^397 + 1)) * (((5^397)^2 + 3*5^397 +1) + 5^199*(5^397 + 1)) (produto da diferença pela soma) = = (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397 + 5^199 + 1) Os três fatores são claramente maiores que 5^100, conforme solicitado. Então: 5^1985 -1 = (5^397 - 1) * (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397 + 5^199 + 1) Como já são três da manhã e já perdi o sono mesmo, resolvi fazer umas continhas de cabeça, tal como o Ralph fez outro dia desses... 5^397-1 = 2 x 2 x 1.043.801.929 x 7.768.438.039 x C258 5^794 -5^596 + 3*5^397 - 5^199 + 1 = 71 x 399.091.951.801 x C542 5^794 + 5^596 + 3*5^397 + 5^199 + 1 = 11 x 146.891 x C549 Logo: 5^1985 -1 = 2 x 2 x 11 x 71 x 146.891 x 1.043.801.929 x 7.768.438.039 x 399.091.951.801 x C258 x C542 x C549 (onde Cn são números compostos de n algarismos). A fatoração de C258, C542 e C549 fica como exercício ... :) Abraços, Vidal. P.S. Nehab: Apesar de não nos conhecermos pessoalmente, temos um grande amigo em comum: o Manuel Martins Filho, professor de Informática da Carioca ! Abraços ! :: vi...@mail.com *** 2009/4/5 Carlos Nehab ne...@infolink.com.br Oi, gente, Fabricio postou este interessante problema e aparentemente ninguém deu muita bola, talvez achando que é óbvio. Não achei óbvio não. Quem resolveu? Abraços, Nehab fabrici...@usp.br escreveu: Caros colegas, mexendo em algumas listas antigas de exercícios, um me chamou muito a atenção. Pede pra fatorar 5^1985 - 1 num produto de três inteiros maiores que 5^100. Pra facilitar um possível avanço, 1985 pode ser escrito como 5 x 397 (ambos primos). . = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = == === Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html == === = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] RE: [obm-l] Re: [obm-l] RE: [obm-l] Re: [obm -l] RE: [obm-l] Re: [obm-l] Um problema cl ássico da Teoria dos Números
Caríssimo Vidal: Agradeço-lhe pelas palavras de consolo (consolo? Sou espada!), mas, fortuitamente, estou acorrentado ao fatalismo judaico-cristão e, assim, a cada uma das muitas vezes em que me descubro em falha de qualquer espécie, nomeadamente a do conhecimento (ou do xadrez), lanço-me no calvário de meu próprio martírio, a fim de abrandar a minha vaidade (que é grande!). A propósito, concordo com você: ao homem ápice da evolução darwinista ou da criação divina (no chute, fico com a 1ª hipótese!) deveriam ser dados 3 dons: o da onisciência holística, o da ubiquidade e o da imortalidade. Em contrapartida, deveríamos ser vítimas das 3 maldições chinesas: Que os seus desejos se realizem!; Que você viva em uma época de interesse histórico!; e, como agora não me lembro da 3ª, fica aí a maldição de Asaverus, o judeu errante. Quanto ao convite para o chope, este, é claro, já está aceito. Aproveito para estendê-lo ao Nehab, Rogério Ponce, Ralph e demais velhinhos (se bem que não sei se o Ralph é velhinho, contudo vale o convite!). E mais: já proponho o Guimas, na Praça do Jockey, em alguma 6ª feira, às 19:00h. Lá reunidos, sem dúvida, poderemos resolver, na pequena toalha da mesa, todos os 6 Problemas do Milênio que ainda estão em aberto e abiscoitar, cada um, US$ 1 milhão. Saudações, Albert. mailto:bousk...@gmail.com bousk...@gmail.com mailto:bousk...@ymail.com bousk...@ymail.com From: owner-ob...@mat.puc-rio.br [mailto:owner-ob...@mat.puc-rio.br] On Behalf Of *Vidal Sent: Monday, April 06, 2009 2:39 AM To: OBM Subject: [obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Um problema clássico da Teoria dos Números Caro Bouskela, Não se martirize ! Somos todos ignorantes, não no sentido pejorativo da palavra, mas na acepção de ignorarmos, desconhecermos os milhares, talvez milhões, de teoremas, conjecturas, problemas abertos e resultados já existentes, afora os que estão sendo gerados neste exato momento em todo o mundo, e os que ainda estão por vir até o fim dos nossos dias. E se, nesta ocasião derradeira, os terroristas suicidas islâmicos são agraciados com setenta virgens cada, talvez para nós esteja reservada como prêmio a onisciência matemática, a fim de nos livrar de todo este martírio terreno. Em tempo, o Gelfond e o Schneider só fizeram a parte fácil do sétimo problema de Hilbert, o caso de b (expoente) irracional e algébrico. Ficou faltando a melhor parte, quando b é irracional, mas não algébrico. Quem sabe um dia a gente não marca um chope, num destes bares com toalha de papel na mesa, e termina o trabalho que eles deixaram inacabado? :) Abraços, Vidal. :: vi...@mail.com *** 2009/4/5 Albert Bouskela bousk...@ymail.com Olá Vidal, Pois é, vivendo e aprendendo. Fiquei meio envergonhado por não conhecer esse Teorema de Gelfond (aliás, bem famoso e recente!). E é mesmo pra sentir vergonha, já que ele resolve o 7º Problema de Hilbert. Bem, obrigado. Mas admito: fiquei meio chateado pela minha ignorância. AB bousk...@gmail.com bousk...@ymail.com From: owner-ob...@mat.puc-rio.br [mailto:owner-ob...@mat.puc-rio.br] On Behalf Of *Vidal Sent: Sunday, April 05, 2009 2:36 AM To: OBM Subject: [obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Um problema clássico da Teoria dos Números Caro Bouskela, Mas 2^sqrt(2) parece e é bem irracional ! Aleksander Gelfond provou em 1934 que se *a* é algébrico não nulo diferente de um e *b* é algébrico e irracional, então *a^b* é transcendente (e portanto, irracional). Apesar de Schneider também ter demonstrado a mesma proposição de forma independente no mesmo ano, o resultado ficou conhecido como Teorema de Gelfond (em mais uma destas injustiças históricas que grassam na Matemática). Assim, 2^sqrt(2) é irracional, assim como também o é e^pi, já que e^pi = (-1)^(-i). Desta forma, eles resolveram *parcialmente* o sétimo dos vinte e três famosos problemas de Hilbert, propostos em 1900. Mas ainda falta resolver o caso de *b* ser irracional, mas não algébrico. Não sabemos até hoje, por exemplo, se 2^e é irracional (apesar de parecer sê-lo). Abraços, Vidal. :: vi...@mail.com *** 2009/4/5 Albert Bouskela bousk...@ymail.com Olá! Hummm... acho que não... 2^sqrt(2) tem, de fato, toda a aparência de um irracional, bem irracional. Entretanto, é preciso demonstrá-lo. A solução deste problema (pelo menos, a solução que eu conheço) não passa pela determinação (identificação) de x e y, i.e., consegue-se apenas demonstrar que x e y existem, mas não identificá-los. Sds., AB bousk...@gmail.com bousk...@ymail.com From: owner-ob...@mat.puc-rio.br [mailto:owner-ob...@mat.puc-rio.br] On Behalf Of *Vidal Sent: Saturday, April 04, 2009 3:27 PM To: OBM Subject: [obm-l] Re: [obm-l] Um problema clássico da Teoria dos Números Caro Bouskela, x = 2^sqrt(2) y = sqrt(2) x^y = 4 Bom final de semana ! Abraços, Vidal. :: vi...@mail.com
[obm-l] Re: [obm-l] Re: [obm-l] Fatoração de 5^1985 - 1.
Caro Fabrício, Eu também passei por esta etapa (produto de dois polinômios de grau 2) durante o pequeno tempo que pensei na solução, depois de provocado pelo Nehab. Mas infelizmente os fatores não eram inteiros. Abraços, Vidal. :: vi...@mail.com 2009/4/6 fabrici...@usp.br fabrici...@usp.br Vidal, muito boa a sacada. Eu tinha tentado escrever como o produto de dois polinômios de grau 2, sem sucesso. Parabéns pela solução. Um abraço. . On Apr 6, 2009, at 03:21 , *Vidal wrote: Caros Fabrício e Nehab, Achar um fator foi fácil, o problema foi quebrar o quociente nos outros dois. Fiz assim: 5^1985 - 1 = (5^397)^5 - 1 Seja x = 5^397. Então queremos fatorar x^5 - 1 que, de imediato, resulta em (x - 1) (x^4 + x^3 + x^2 + x + 1), ou seja, um dos fatores é 5^397 - 1. Falta fatorar x^4 + x^3 + x^2 + x + 1 de uma forma conveniente. Após um tempinho (pouca coisa, até no Fla x Flu no Maracanã estava rabiscando...), tive a idéia de tentar escrever a expressão como uma adequada diferença de dois quadrados. Caso conseguisse, o problema estaria resolvido, pois um fator seria a soma e outro, a diferença. Arbitrei o primeiro quadrado como (x^2 + ax + 1)^2, que já geraria o termo de quarto grau e o termo independente corretos. E coloquei o segundo quadrado como 5x(x+b)^2, pois como x = 5^397, 5x = 5^398 seria um quadrado perfeito. Igualando as expressões (e rezando para encontrar valores de a e b compatíveis), veio: (x^2 + ax + 1)^2 - 5x(x+b)^2 = x^4 + (2a -5)x^3 + (a^2 - 10b + 2)x^2 + (2a - 5b^2)x + 1 = x^4 + x^3 + x^2 + x + 1 Assim: 2a -5 = 1 = a = 3 a^2 - 10b + 2 = 1 = b = 1 Agora era hora da onça beber água: 2a - 5b^2 = 1 Mas a = 3 e b = 1 satisfazem ! Eureka ! x^4 + x^3 + x^2 + x + 1 = (x^2 + 3x + 1)^2 - 5x(x+1)^2 Substituindo x por 5^397: ((5^397)^2 + 3*5^397 +1)^2 - 5*5^397*(5^397 + 1)^2 = = ((5^397)^2 + 3*5^397 +1)^2 - 5^398*(5^397 + 1)^2 (diferença de quadrados) = = (((5^397)^2 + 3*5^397 +1) - 5^199*(5^397 + 1)) * (((5^397)^2 + 3*5^397 +1) + 5^199*(5^397 + 1)) (produto da diferença pela soma) = = (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397 + 5^199 + 1) Os três fatores são claramente maiores que 5^100, conforme solicitado. Então: 5^1985 -1 = (5^397 - 1) * (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397 + 5^199 + 1) Como já são três da manhã e já perdi o sono mesmo, resolvi fazer umas continhas de cabeça, tal como o Ralph fez outro dia desses... 5^397-1 = 2 x 2 x 1.043.801.929 x 7.768.438.039 x C258 5^794 -5^596 + 3*5^397 - 5^199 + 1 = 71 x 399.091.951.801 x C542 5^794 + 5^596 + 3*5^397 + 5^199 + 1 = 11 x 146.891 x C549 Logo: 5^1985 -1 = 2 x 2 x 11 x 71 x 146.891 x 1.043.801.929 x 7.768.438.039 x 399.091.951.801 x C258 x C542 x C549 (onde Cn são números compostos de n algarismos). A fatoração de C258, C542 e C549 fica como exercício ... :) Abraços, Vidal. P.S. Nehab: Apesar de não nos conhecermos pessoalmente, temos um grande amigo em comum: o Manuel Martins Filho, professor de Informática da Carioca ! Abraços ! :: vi...@mail.com *** 2009/4/5 Carlos Nehab ne...@infolink.com.br Oi, gente, Fabricio postou este interessante problema e aparentemente ninguém deu muita bola, talvez achando que é óbvio. Não achei óbvio não. Quem resolveu? Abraços, Nehab fabrici...@usp.br escreveu: Caros colegas, mexendo em algumas listas antigas de exercícios, um me chamou muito a atenção. Pede pra fatorar 5^1985 - 1 num produto de três inteiros maiores que 5^100. Pra facilitar um possível avanço, 1985 pode ser escrito como 5 x 397 (ambos primos). . = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html= = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html =
Re: [obm-l] Re: [obm-l] Re: [obm-l] Fatoração de 5^1985 - 1.
Oi, Vidal (e Fabricio), J que meu neto no est aqui em casa... :-) e como gostei tanto de suas continhas de cabea, fucei um site que tenho certeza que vocs vo gostar Tem coisas surreais http://www.leyland.vispa.com/numth/factorization/main.htm Abraos, Nehab ( *Vidal escreveu: Caro Fabrcio, Eu tambm passei por esta etapa (produto de dois polinmios de grau 2) durante o "pequeno" tempo que pensei na soluo, depois de "provocado" pelo Nehab. Mas infelizmente os fatores no eram inteiros. Abraos, Vidal. :: vi...@mail.com 2009/4/6 fabrici...@usp.br fabrici...@usp.br Vidal, muito boa a sacada. Eu tinha tentado escrever como o produto de dois polinmios de grau 2, sem sucesso. Parabns pela soluo. Um abrao. . On Apr 6, 2009, at 03:21 , *Vidal wrote: Caros Fabrcio e Nehab, Achar um fator foi fcil, o problema foi "quebrar" o quociente nos outros dois. Fiz assim: 5^1985 - 1 = (5^397)^5 - 1 Seja x = 5^397. Ento queremos fatorar x^5 - 1 que, de imediato, resulta em (x - 1) (x^4 + x^3 + x^2 + x + 1), ou seja, um dos fatores 5^397 - 1. Falta fatorar x^4 + x^3 + x^2 + x + 1 de uma forma conveniente. Aps um tempinho (pouca coisa, at no Fla x Flu no Maracan estava rabiscando...), tive a idia de tentar escrever a expresso como uma adequada diferena de dois quadrados. Caso conseguisse, o problema estaria resolvido, pois um fator seria a soma e outro, a diferena. Arbitrei o primeiro quadrado como (x^2 + ax + 1)^2, que j geraria o termo de quarto grau e o termo independente corretos. E coloquei o segundo quadrado como 5x(x+b)^2, pois como x = 5^397, 5x = 5^398 seria um quadrado perfeito. Igualando as expresses (e rezando para encontrar valores de a e b compatveis), veio: (x^2 + ax + 1)^2 - 5x(x+b)^2 = x^4 + (2a -5)x^3 + (a^2 - 10b + 2)x^2 + (2a - 5b^2)x + 1 = x^4 + x^3 + x^2 + x + 1 Assim: 2a -5 = 1 = a = 3 a^2 - 10b + 2 = 1 = b = 1 Agora era hora da ona beber gua: 2a - 5b^2 = 1 Mas a = 3 e b = 1 satisfazem ! Eureka ! x^4 + x^3 + x^2 + x + 1 = (x^2 + 3x + 1)^2 - 5x(x+1)^2 Substituindo x por 5^397: ((5^397)^2 + 3*5^397 +1)^2 - 5*5^397*(5^397 + 1)^2 = = ((5^397)^2 + 3*5^397 +1)^2 - 5^398*(5^397 + 1)^2 (diferena de quadrados) = = (((5^397)^2 + 3*5^397 +1) - 5^199*(5^397 + 1)) * (((5^397)^2 + 3*5^397 +1) + 5^199*(5^397 + 1)) (produto da diferena pela soma) = = (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397 + 5^199 + 1) Os trs fatores so claramente maiores que 5^100, conforme solicitado. Ento: 5^1985 -1 = (5^397 - 1) * (5^794 - 5^596 + 3*5^397 - 5^199 + 1) * (5^794 + 5^596 + 3*5^397 + 5^199 + 1) Como j so trs da manh e j perdi o sono mesmo, resolvi fazer umas "continhas de cabea", tal como o Ralph fez outro dia desses... 5^397-1 = 2 x 2 x 1.043.801.929 x 7.768.438.039 x C258 5^794 -5^596 + 3*5^397 - 5^199 + 1 = 71 x 399.091.951.801 x C542 5^794 + 5^596 + 3*5^397 + 5^199 + 1 = 11 x 146.891 x C549 Logo: 5^1985 -1 = 2 x 2 x 11 x 71 x 146.891 x 1.043.801.929 x 7.768.438.039 x 399.091.951.801 x C258 x C542 x C549 (onde Cn so nmeros compostos de n algarismos). A fatorao de C258, C542 e C549 fica como exerccio ... :) Abraos, Vidal. P.S. Nehab: Apesar de no nos conhecermos pessoalmente, temos um grande amigo em comum: o Manuel Martins Filho, professor de Informtica da Carioca ! Abraos ! :: vi...@mail.com *** 2009/4/5 Carlos Nehab ne...@infolink.com.br Oi, gente, Fabricio postou este interessante problema e aparentemente ningum deu muita bola, talvez achando que bvio. No achei bvio no. Quem resolveu? Abraos, Nehab fabrici...@usp.br escreveu: Caros colegas, mexendo em algumas listas antigas de exerccios, um me chamou muito a ateno. Pede pra fatorar 5^1985 - 1 num produto de trs inteiros maiores que 5^100. Pra facilitar um possvel avano, 1985 pode ser escrito como 5 x 397 (ambos primos). . = Instrues para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = = Instrues para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = = Instrues para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Uma difícil de Combinatória
Pessoal esta questão caiu em uma avaliação que fiz e o gabarito foi bem diferente do que ei fiz. Por favor se alguém tiver um tempinho me dê uma mão, ok ? Questão: Sejam 10 caixas de madeira, exatamente iguais. Queremos pintar cada uma delas com uma cor dentre quatro cores disponíveis: Azul, amarelo, verde e vermelho. De quantos modos podemos pintar as caixas, sabendo que pelo menos uma das caixas deve ser pintada de azul ? Minha resolução: Busquei encontrar o número ma´ximo de possibilidades para pintar as caixas. Então pensei da seguinte maneira: Na primeira caixa poderiam entra 4 cores, e na segunda 4 e na terceira 4 e.assim até a décima caixa. Então o número máximo de possibilidades de se pintar as 10 caixas pela minha conta seria 4^10. Em seguida busquei encontrar o número de possibilidades onde a cor azul não aparecesse. Então analisei que na rimeira caixa poderiam entrar 3 cores, na segunda 3 cores, na terceira 3 corese na décima 3 cores. Então pela minha conta eu teria 3^10 onde o azul não aparece. Então como preciso ter pelo menos uma caixa azul, fiz: 4^10 - 3^10 = achei 989.527 maneiras Bem pessoal pelo gabarito eu errei e muito! O gabarito deu 220 modos. Não entendi nada! Peço que vocês me ajudem por favor, para compreender o enorme erro que fiz. Abração a todos. Marcelo.
[obm-l] duvida
Será que vcs poderiam me ajudar? Com os algarismos 0,1,2,3,4,5,6. Determine quantos números de quatro algarismos distintos maiores que 4320 podem ser formados? Obrigada, Onde posso obter exercícios resolvidos deste assunto?
[obm-l] Re: [obm-l] Uma difícil de Combinatória
Ola Marcelo e demais colegas desta lista ... OBM-L, ( escreverei sem acentos ) Sejam : A - caixas na cor azul B - caixas na cor amarelo C - caixas na cor verde D - caixas na cor vermelho. Uma solucao de A+B+C+D=10 na qual so figurem numeros inteiros nao-negativos pode ser interpretada como uma maneira de pintar as caixas. Assim, a 4-upla (A,B,C,D)=(3,2,0,5) significa que tres caixas foram pintadas de azul, duas caixas foram pintadas de amarela, nenhuma caixa foi pintada verde e cinco caixas foram pintadas de vermelho. O total de solucoes inteiras nao-negativas de A+B+C+D=10 nos da, portanto, o numero de maneiras possiveis de pintarmos as 10 caixas com as quatro cores disponiveis - claro, supondo-se que duas caixas ainda nao pintadas sao indistinguíveis ! Isto posto, fica facil ver que considerando agora as solucoes de A+B+C+D=10 nas quais A 0 ( A e positivo ), vale dizer, todas as solucoes de A+B+C+D=9, teremos todas as maneiras de pintar as caixas nas quais AO MENOS UMA CAIXA FOI PINTADAS DE AZUL. Existe um algoritmo direto, mesmo uma formula, para o total de solucoes inteiras e nao negativas de uma equacao diofantina da forma X1 + ... + Xn = M, o que responde a sua questao. A formula e : Binom(N+M-1,M) No seu caso : N=4 e M=9. Logo : Binom(4+9-1,9)=220 Um Abraco a Todos ! Paulo Santa Rita 20604092020 2009/4/6 Marcelo Gomes elementos@gmail.com: Pessoal esta questão caiu em uma avaliação que fiz e o gabarito foi bem diferente do que ei fiz. Por favor se alguém tiver um tempinho me dê uma mão, ok ? Questão: Sejam 10 caixas de madeira, exatamente iguais. Queremos pintar cada uma delas com uma cor dentre quatro cores disponíveis: Azul, amarelo, verde e vermelho. De quantos modos podemos pintar as caixas, sabendo que pelo menos uma das caixas deve ser pintada de azul ? Minha resolução: Busquei encontrar o número ma´ximo de possibilidades para pintar as caixas. Então pensei da seguinte maneira: Na primeira caixa poderiam entra 4 cores, e na segunda 4 e na terceira 4 e.assim até a décima caixa. Então o número máximo de possibilidades de se pintar as 10 caixas pela minha conta seria 4^10. Em seguida busquei encontrar o número de possibilidades onde a cor azul não aparecesse. Então analisei que na rimeira caixa poderiam entrar 3 cores, na segunda 3 cores, na terceira 3 corese na décima 3 cores. Então pela minha conta eu teria 3^10 onde o azul não aparece. Então como preciso ter pelo menos uma caixa azul, fiz: 4^10 - 3^10 = achei 989.527 maneiras Bem pessoal pelo gabarito eu errei e muito! O gabarito deu 220 modos. Não entendi nada! Peço que vocês me ajudem por favor, para compreender o enorme erro que fiz. Abração a todos. Marcelo. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
