RE: [obm-l] Problemas em aberto
Oi, Paulo: Se existir um tal polinomio p(q), entao eh facil ver que os coeficientes serao inteiros (eh soh montar a recorrencia). No entanto, nao pode existir um tal polinomio pois, se tivermos: p(q) * SOMA(k=1) q^(k(k-1)/2) = SOMA(n=0) q^n = 1/(1-q), se |q| 1. entao, com q = 1/2, teriamos: SOMA(k=1) (1/2^(k(k-1)/2)) = 2/p(1/2) == Mas, pelo teorema das raizes racionais, p(1/2) 0 e, alem disso, eh claramente racional. Logo, 2/p(1/2) eh racional. No entanto, SOMA(k=1) (1/2^(k(k-1)/2)) eh irracional (basta ver que, em base 2, esta soma eh uma decimal infinita e nao periodica) == contradicao == nao existe p(q). []s, Claudio. -- Cabeçalho original --- De: [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Tue, 13 Feb 2007 17:58:20 + Assunto: RE: [obm-l] Problemas em aberto Ola Ronaldo e demais colegas desta lista ... OBM-L, Parabens, a sua intuicao e muito boa. Eu acho que se voce parar para pensar com mais calma, sem pressupostos, vai resolver... Talvez falte voce observar o seguinte : Na serie geometrica bem conhecida Sn = 1 + q + q^2 + ... + q^(N-1), 0 q 1, como calculamos o LIM Sn quando N vai para o infinito ? Em geral, fixamos N e multiplicamos Sn por UM POLINOMIO p(q) EM q, CONVENIENTE, tal que p(q)*Sn = ALGO SOMAVEL OU MAIS SIMPLES. no caso particular da serie geomentrica temos que p(q) = q - 1 pois (q - 1)*Sn =q^N - 1. A seguir, dado que q^N - 0 quando N vai para o infinito seque que Sn = 1/(1-q). Note que aqui p(q)*sn= ALGO MAIS SIMPLES. Poderia ser tambem algo somavel ou computavel ... Seja agora Sn = 1 + q + q^3 + ... + q^[(N(N-1))/2]. Quem e p(q) tal que p(q)*Sn = ALGO SOMAVEL OU MAIS SIMPLES ? Eis uma questao na qual um software como o MAXIMA ou OCTAVE facilita muito as coisas, pois nos permite fazer experiencias com as diversas possibilidades do polinomio p(q) que precisamos descobrir. E com os melhores votos de paz profunda, sou Paulo Santa Rita 3,0F38,130207 Date: Tue, 13 Feb 2007 12:50:30 -0300 From: [EMAIL PROTECTED] To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] Problemas em aberto Se o termo n(n-1)/2 fosse n(n+1)/2 ele seria a soma de uma P.A. com os n primeiros naturais. Não parei ainda para pensar com calma, mas será que esse problema não está relacionado com partições de inteiros e a função de Euler ? http://en.wikipedia.org/wiki/Integer_partition Note que o termo de x^n que é p(n) conta o número de vezes em que é possível escrever n = a_1 + 2a_2 + 3a_3 + ... onde cada a_i aparece i vezes. Bem, alguém já deve ter pensado nisso, então o que eu falei não ajuda muito ... :) []s Ronaldo _ Busque em qualquer página da Web com alta proteção. Obtenha o Windows Live Toolbar GRATUITO ainda hoje! http://toolbar.live.com/ = 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 = = 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] Problemas em aberto
Oi claudio, Leia com atencao. Eu disse que NO CASO DA SERIE GEOMETRICA . Alem disso, voce ja sabe a forma definitiva do polinomio TRABALHAVEL ou SOMAVEL ? E aqui que esta a graca do problema ... Se nos ficarmos discutindo detalhes nao chegaremos a lugar algum. O que e importante e o total sentido da questao e que ha uma resposta definitiva em formula fechada. Se voce quer trabalhar nisso pense assim : Dado S = 1 + q + ... + q^[N(N+1)/2] + ... . Exprima esta soma em funca de q SUGESTAO 1 : usando o exemplo da serie geometrica, multiplique S por um expressao conveniente de forma que o resultado seja mais facilmente trabalhavel SUGESTAO 2 : IMAGINE que os termos de S foram retirado de uma PG infinita T = 1 + q + q^2 + q^3 + ... O que sobra em T sao PG's facilmente somaveis. Isso permite obter uma formula de recorrencia para Sn. Trabalhe nesta formula Este resultado e uma generalizacao do conceito de Progressao Geometrica. Eu chamava de PROGRESSAO GEOMETRICA DE 2 ORDEM, quando era crianca. Eis aqui o problema para a terceira ordem : Seja reais positivos A1, A2, ..., An, ... tal que An+1 / An = q^[N(N-1)/2]. Onde 0 q 1. Exprima em funcao 'q a soma infinita A1 + A2 + A3 + ...+ An + ... De maneira geral, se 0q1, a serie S = q^A1 + q^A2 + q^A3 + ... + q^An + ... e uma PROGRESSAO GEOMETRICA INFINITA DE ORDEM R SE A SEQUENCIA A1, A2, ... e uma progressao aritmetica de ordem R. Estas designacoes de PG's de ordem superior eu criei para o meu uso particular, quando ainda era crianca, e muito provavelmente nao sao usadas por nenhum outro Matematico. Foi apenas uma brincadeira infantil. Seja S = S = q^A1 + q^A2 + q^A3 + ... + q^An + ... uma PROGRESSAO GEOMETRICA INFINITA DE ORDEM R. Exprima, em funcao de q e de A1, A2, ... o valor para onde S converge ( 0 q 1) Um Abracao Paulo Santa Rita 4,0C56,140207 Em 14/02/07, claudio.buffara[EMAIL PROTECTED] escreveu: Oi, Paulo: Se existir um tal polinomio p(q), entao eh facil ver que os coeficientes serao inteiros (eh soh montar a recorrencia). No entanto, nao pode existir um tal polinomio pois, se tivermos: p(q) * SOMA(k=1) q^(k(k-1)/2) = SOMA(n=0) q^n = 1/(1-q), se |q| 1. entao, com q = 1/2, teriamos: SOMA(k=1) (1/2^(k(k-1)/2)) = 2/p(1/2) == Mas, pelo teorema das raizes racionais, p(1/2) 0 e, alem disso, eh claramente racional. Logo, 2/p(1/2) eh racional. No entanto, SOMA(k=1) (1/2^(k(k-1)/2)) eh irracional (basta ver que, em base 2, esta soma eh uma decimal infinita e nao periodica) == contradicao == nao existe p(q). []s, Claudio. -- Cabeçalho original --- De: [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Tue, 13 Feb 2007 17:58:20 + Assunto: RE: [obm-l] Problemas em aberto Ola Ronaldo e demais colegas desta lista ... OBM-L, Parabens, a sua intuicao e muito boa. Eu acho que se voce parar para pensar com mais calma, sem pressupostos, vai resolver... Talvez falte voce observar o seguinte : Na serie geometrica bem conhecida Sn = 1 + q + q^2 + ... + q^(N-1), 0 q 1, como calculamos o LIM Sn quando N vai para o infinito ? Em geral, fixamos N e multiplicamos Sn por UM POLINOMIO p(q) EM q, CONVENIENTE, tal que p(q)*Sn = ALGO SOMAVEL OU MAIS SIMPLES. no caso particular da serie geomentrica temos que p(q) = q - 1 pois (q - 1)*Sn =q^N - 1. A seguir, dado que q^N - 0 quando N vai para o infinito seque que Sn = 1/(1-q). Note que aqui p(q)*sn= ALGO MAIS SIMPLES. Poderia ser tambem algo somavel ou computavel ... Seja agora Sn = 1 + q + q^3 + ... + q^[(N(N-1))/2]. Quem e p(q) tal que p(q)*Sn = ALGO SOMAVEL OU MAIS SIMPLES ? Eis uma questao na qual um software como o MAXIMA ou OCTAVE facilita muito as coisas, pois nos permite fazer experiencias com as diversas possibilidades do polinomio p(q) que precisamos descobrir. E com os melhores votos de paz profunda, sou Paulo Santa Rita 3,0F38,130207 Date: Tue, 13 Feb 2007 12:50:30 -0300 From: [EMAIL PROTECTED] To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] Problemas em aberto Se o termo n(n-1)/2 fosse n(n+1)/2 ele seria a soma de uma P.A. com os n primeiros naturais. Não parei ainda para pensar com calma, mas será que esse problema não está relacionado com partições de inteiros e a função de Euler ? http://en.wikipedia.org/wiki/Integer_partition Note que o termo de x^n que é p(n) conta o número de vezes em que é possível escrever n = a_1 + 2a_2 + 3a_3 + ... onde cada a_i aparece i vezes. Bem, alguém já deve ter pensado nisso, então o que eu falei não ajuda muito ... :) []s Ronaldo _ Busque em qualquer página da Web com alta proteção. Obtenha o Windows Live Toolbar GRATUITO ainda hoje! http://toolbar.live.com/ = 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] Problemas em aberto
2. Num espaco metrico compacto, uma sequencia (x(n)) eh tal que lim(n-+inf) dist(x(n+1),x(n)) = 0. Prove que o conjunto de valores de aderencia de (x(n)) eh conexo. Eu provei no caso de (x(n)) ser uma sequencia limitada na reta. Se x(n) - a, entao A = conjunto dos valores de aderencia de (x(n)) = {a}, que eh conexo. Se x(n) nao converge, sejam a = liminf(x(n)) e b = limsup(x(n)). (a e b existem pois (x(n)) eh limitada e, alem disso, a b, pois (x(n)) diverge) Finalmente, seja c tal que a c b. Tomemos eps 0. Podemos supor spdg que eps eh pequeno o bastante para que os intervalos (a-eps,a+eps), (c-eps,c+eps) e (b-eps,b+eps) sejam disjuntos dois a dois. Seja k_0 em N tal que k k_0 == |x(k+1) - x(k)| eps. Seja m k_0 tal que x(m) pertence a (a-eps,a+eps). Seja n o menor inteiro maior do que m tal que x(n) pertence a (b-eps,b+eps). (m e n existem pois a e b sao limites de subsequencias de (x(n)) ) Eh claro que x(m) c-eps c+eps x(n). Seja X = {r em N | m = r = n e x(r) = c-eps}. Naturalmente, X eh nao-vazio (m pertence a X) e limitado superiormente (por n, que nao pertence a X, mas isso nao importa). Seja r = maior elemento de X. Entao, x(r) = c-eps x(r+1) e, portanto, x(r+1) c+eps, pois se fosse x(r+1) = c+eps, entao: |x(r+1) - x(r)| = 2*eps, o que eh impossivel pois r = m k. Logo, x(r+1) pertence a (c-eps,c+eps). Ou seja, para cada eps 0, existe n em N tal que x(n) pertence a (c-eps,c+eps) == c eh um valor de aderencia de (x(n)). Como c eh um elemento arbitrario de (a,b), concluimos que (a,b) estah contido em A. Como a = min(A) e b = max(A), concluimos que A = [a,b] = conexo. No caso geral, temos que A (conjunto de valores de aderência de (x(n)) é fechado (um bom exercício é provar isso). Como o espaço é compacto, A é compacto. Suponhamos que A não seja conexo. Então, podemos escrever A = B uniao C, onde B e C são compactos disjuntos e não-vazios. Temos dist(B,C) = d 0 (outro bom exercício) B pode ser coberto por um número finitos de bolas abertas com centro em algum ponto de B e raio = d/3 (Heine-Borel-Lebesgue). Idem para C. Chame a união dessas bolas de VB e VC respectivamente (V de vizinhança...). Temos que dist(VB,VC) = d/3 (mais um exercício) Seja k_0 em N tal que para todo k k_0, dist(x(k+1),x(k)) d/3. Seja m k_0 tal que x(m) pertence a VB. Um tal m existe pois alguma subsequencia de (x(n)) converge para algum ponto de B. Seja p o menor inteiro maior que m tal que x(p+1) pertence a VC. Um tal p também existe pois alguma subsequencia de (x(n)) converge para algum ponto de C. Não é difícil ver que x(p) não pertence a VB nem a VC. Não pertence a VC pela escolha de p e não pertence a VB pois, se esse fosse o caso, como p m k_0, teríamos: d/3 dist(x(p+1),x(p)) = dist(VC,VB) = d/3, o que é uma contradição. Assim, para cada par (m,n) em NxN com m n tal que x(m) pertence a VB e x(n) pertence a VC, vai existir p com m p n tal que x(p) não pertence a VB união VC. Como o conjunto dos pares (m,n) é infinito, o conjunto dos p também é. Ou seja, (x(p)) é uma subsequência de (x(n)) cujos pontos não pertencem a VB união VC. Como o espaço é compacto, (x(p)) é limitada e, portanto, possui uma subsequência convergente para um ponto c, o qual também não pertence a VB unão VC (pois o complementar de VB união VC é fechado). Logo, c é um valor de aderência de (x(n)) que não pertence a VB união VC e, com mais razão ainda, não pertence a B união C = A == contradição. A única origem possível dessa contradição é a hipótese feita inicialmente de A não ser conexo. Logo, concluímos que A é conexo. Belo problema esse! Eu levei um bom tempo pra formalizar uma solução apesar da idéia básica ser simples: pra sequência alternar infinitas vezes entre VB e VC, uma infinidade de termos teria que estar no complementar de B união C, já que, a partir de um certo ponto, a distância entre dois termos consecutivos é menor do que a distância entre VB e VC. Por causa da compacidade do espaço, esses termos teriam que se acumular no espaço entre B e C e formar uma ponte conexa entre os dois conjuntos. []s, Claudio.
Re: [obm-l] Problemas em aberto
On 2/13/07, claudio.buffara [EMAIL PROTECTED] wrote: Antes de postar um problema bonitinho sobre complexos, quero lembrar que ainda temos (pelo menos) dois problemas em aberto na lista, um do PSRita e o outro do ACSteiner: 1. Calcule o valor de SOMA(n=1...+inf) q^(n(n-1)/2), onde |q| 1. Consultei meus alfarrabios e descobri que esta soma eh igual a um certo produto infinito, mas nao achei nenhuma formula fechada e suspeito que nenhuma exista, a menos que envolva alguma funcao nao elementar - alias, como a serie acima converge, ela pode ser usada pra definir uma funcao de (-1,1) - R. Se o termo n(n-1)/2 fosse n(n+1)/2 ele seria a soma de uma P.A. com os n primeiros naturais. Não parei ainda para pensar com calma, mas será que esse problema não está relacionado com partições de inteiros e a função de Euler? http://en.wikipedia.org/wiki/Integer_partition Note que o termo de x^n que é p(n) conta o número de vezes em que é possível escrever n = a_1 + 2a_2 + 3a_3 + ... onde cada a_i aparece i vezes. Bem, alguém já deve ter pensado nisso, então o que eu falei não ajuda muito ... :) []s Ronaldo
Re: [obm-l] Problemas em aberto
Olá, tomemos os numeros complexos a, b, c, entao: considerando que ||b-a|| = ||c-a|| = ||b-c||, temos: (b-a)/(c-a) = cis(alfa), onde alfa é o ângulo entre as arestas AB e AC... (a-c)/(b-c) = cis(beta), onde beta é o ângulo entre as arestas CA e CB... se alfa = beta... temos: (b-a)/(c-a) = (a-c)/(b-c) assim: bb - ab - bc + ac = ca - cc - aa + ac logo: aa + bb + cc = ac + ab + bc logo, se o triangulo é equilatero, vale a relacao! para fazer a volta, basta fatorarmos, chegando a (b-a)/(c-a) = (a-c)/(b-c) assim, os modulos tem q ser iguais e os angulos tb! abracos, Salhab - Original Message - From: claudio.buffara [EMAIL PROTECTED] To: obm-l obm-l@mat.puc-rio.br Sent: Tuesday, February 13, 2007 10:37 AM Subject: [obm-l] Problemas em aberto Antes de postar um problema bonitinho sobre complexos, quero lembrar que ainda temos (pelo menos) dois problemas em aberto na lista, um do PSRita e o outro do ACSteiner: 1. Calcule o valor de SOMA(n=1...+inf) q^(n(n-1)/2), onde |q| 1. Consultei meus alfarrabios e descobri que esta soma eh igual a um certo produto infinito, mas nao achei nenhuma formula fechada e suspeito que nenhuma exista, a menos que envolva alguma funcao nao elementar - alias, como a serie acima converge, ela pode ser usada pra definir uma funcao de (-1,1) - R. 2. Num espaco metrico compacto, uma sequencia (x(n)) eh tal que lim(n-+inf) dist(x(n+1),x(n)) = 0. Prove que o conjunto de valores de aderencia de (x(n)) eh conexo. Eu provei no caso de (x(n)) ser uma sequencia limitada na reta. Se x(n) - a, entao A = conjunto dos valores de aderencia de (x(n)) = {a}, que eh conexo. Se x(n) nao converge, sejam a = liminf(x(n)) e b = limsup(x(n)). (a e b existem pois (x(n)) eh limitada e, alem disso, a b, pois (x(n)) diverge) Finalmente, seja c tal que a c b. Tomemos eps 0. Podemos supor spdg que eps eh pequeno o bastante para que os intervalos (a-eps,a+eps), (c-eps,c+eps) e (b-eps,b+eps) sejam disjuntos dois a dois. Seja k_0 em N tal que k k_0 == |x(k+1) - x(k)| eps. Seja m k_0 tal que x(m) pertence a (a-eps,a+eps). Seja n o menor inteiro maior do que m tal que x(n) pertence a (b-eps,b+eps). (m e n existem pois a e b sao limites de subsequencias de (x(n)) ) Eh claro que x(m) c-eps c+eps x(n). Seja X = {r em N | m = r = n e x(r) = c-eps}. Naturalmente, X eh nao-vazio (m pertence a X) e limitado superiormente (por n, que nao pertence a X, mas isso nao importa). Seja r = maior elemento de X. Entao, x(r) = c-eps x(r+1) e, portanto, x(r+1) c+eps, pois se fosse x(r+1) = c+eps, entao: |x(r+1) - x(r)| = 2*eps, o que eh impossivel pois r = m k. Logo, x(r+1) pertence a (c-eps,c+eps). Ou seja, para cada eps 0, existe n em N tal que x(n) pertence a (c-eps,c+eps) == c eh um valor de aderencia de (x(n)). Como c eh um elemento arbitrario de (a,b), concluimos que (a,b) estah contido em A. Como a = min(A) e b = max(A), concluimos que A = [a,b] = conexo. *** O probleminha sobre complexos eh o seguinte: a, b, c sao numeros complexos. Prove que: a, b, c sao os vertices de um triangulo equilatero no plano complexo se e somente se a^2 + b^2 + c^2 = ab + ac + bc. []s, Claudio. = 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 = = 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] Problemas em aberto
Ola Ronaldo e demais colegas desta lista ... OBM-L, Parabens, a sua intuicao e muito boa. Eu acho que se voce parar para pensar com mais calma, sem pressupostos, vai resolver... Talvez falte voce observar o seguinte : Na serie geometrica bem conhecida Sn = 1 + q + q^2 + ... + q^(N-1), 0 q 1, como calculamos o LIM Sn quando N vai para o infinito ? Em geral, fixamos N e multiplicamos Sn por UM POLINOMIO p(q) EM q, CONVENIENTE, tal que p(q)*Sn = ALGO SOMAVEL OU MAIS SIMPLES. no caso particular da serie geomentrica temos que p(q) = q - 1 pois (q - 1)*Sn =q^N - 1. A seguir, dado que q^N - 0 quando N vai para o infinito seque que Sn = 1/(1-q). Note que aqui p(q)*sn= ALGO MAIS SIMPLES. Poderia ser tambem algo somavel ou computavel ... Seja agora Sn = 1 + q + q^3 + ... + q^[(N(N-1))/2]. Quem e p(q) tal que p(q)*Sn = ALGO SOMAVEL OU MAIS SIMPLES ? Eis uma questao na qual um software como o MAXIMA ou OCTAVE facilita muito as coisas, pois nos permite fazer experiencias com as diversas possibilidades do polinomio p(q) que precisamos descobrir. E com os melhores votos de paz profunda, sou Paulo Santa Rita 3,0F38,130207 Date: Tue, 13 Feb 2007 12:50:30 -0300 From: [EMAIL PROTECTED] To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] Problemas em aberto Se o termo n(n-1)/2 fosse n(n+1)/2 ele seria a soma de uma P.A. com os n primeiros naturais. Não parei ainda para pensar com calma, mas será que esse problema não está relacionado com partições de inteiros e a função de Euler ? http://en.wikipedia.org/wiki/Integer_partition Note que o termo de x^n que é p(n) conta o número de vezes em que é possível escrever n = a_1 + 2a_2 + 3a_3 + ... onde cada a_i aparece i vezes. Bem, alguém já deve ter pensado nisso, então o que eu falei não ajuda muito ... :) []s Ronaldo _ Busque em qualquer página da Web com alta proteção. Obtenha o Windows Live Toolbar GRATUITO ainda hoje! http://toolbar.live.com/ = 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] Problemas em aberto
Oi, Claudio, O problema de complexos que você mencionou é uma ferramenta extremamente útil que já usei para demonstrar inúmeros problemas de geometria, como por exemplo o famoso teorema atribuido ao Napoleão (o Bonaparte, mesmo, acredite se quiser... :-)), que eu acho surpreendente: Sobre os lados de um triângulo arbitrário construa três triângulos equiláteros exteriores ao mesmo. Mostre que os centros destes 3 triângulos equiláteros determinam um novo triângulo equilátero. O teorema do Napoleão também é relacionado a outro problema (atribuído a Pascal) igualmente interessante: Dado um triângulo qualquer, determine o ponto de seu plano cuja soma das distâncias aos vértices é mínima. Os aficcionados em Geometria que se regozigem... São bonitos, assim, como as soluções. Quanto ao somatório (com expoentes sendo os números triangulares) tô pensando... Abraços, Nehab At 13:50 13/2/2007, you wrote: On 2/13/07, claudio.buffara mailto:[EMAIL PROTECTED][EMAIL PROTECTED] wrote: Antes de postar um problema bonitinho sobre complexos, quero lembrar que ainda temos (pelo menos) dois problemas em aberto na lista, um do PSRita e o outro do ACSteiner: 1. Calcule o valor de SOMA(n=1...+inf) q^(n(n-1)/2), onde |q| 1. Consultei meus alfarrabios e descobri que esta soma eh igual a um certo produto infinito, mas nao achei nenhuma formula fechada e suspeito que nenhuma exista, a menos que envolva alguma funcao nao elementar - alias, como a serie acima converge, ela pode ser usada pra definir uma funcao de (-1,1) - R. Se o termo n(n-1)/2 fosse n(n+1)/2 ele seria a soma de uma P.A. com os n primeiros naturais. Não parei ainda para pensar com calma, mas será que esse problema não está relacionado com partições de inteiros e a função de Euler? http://en.wikipedia.org/wiki/Integer_partitionhttp://en.wikipedia.org/wiki/Integer_partition Note que o termo de x^n que é p(n) conta o número de vezes em que é possível escrever n = a_1 + 2a_2 + 3a_3 + ... onde cada a_i aparece i vezes. Bem, alguém já deve ter pensado nisso, então o que eu falei não ajuda muito ... :) []s Ronaldo
Re: [obm-l] PROBLEMAS EM ABERTO!
On Mon, Dec 26, 2005 at 12:44:58PM +, Jorge Luis Rodrigues e Silva Luis wrote: Afinal! Existe alguma fração ordinária que possa dar a fração 0,...? 1/1. Este é o problema trivial que mais recebeu espaço nesta lista. Procure usando os engenhos de busca ou veja http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200310/msg00348.html []s, N. = 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] Problemas em aberto - prob 10
Caro Demetrio, Parece que os únicos contra-exemplos para isso são (A,B,C)=(2^m+1,2^m-1,2), para m=1. Além disso, acho que é possível provar algo bem mais forte (para k grande): P tem pelo menos 2^k-k fatores primos distintos. Isso já é maior que k+1 se k=3. Vamos então provar isso primeiro e depois analisar os casos k=1 e k=2. Vamos usar polinômios ciclotômicos, que são polinômios phi_n(x), indexados pelos inteiros positivos n que aparecem na fatoração de x^n-1: para cada inteiro positivo n, x^n-1=produto(d divide n)(phi_d(x)). Isso define os phi_n(x) por recorrência; temos phi_n(x)=produto(1=k=n,mdc(k,n)=1)(x-e^(2.k.pi.i/n)), donde o grau de phi_n(x) é phi(n) (aqui phi é a função de Euler). Segue da primeira definição, via fatoração, por indução, que, para todo n, phi_n(x) tem coeficientes inteiros e coeficiente líder 1. É possível provar que, para todo n, phi_n(x) é um polinômio irredutível, mas não vamos usar isso aqui. Temos A^c-B^c=B^c.((A/B)^c-1)=B^c.produto(d divide c)(phi_d(A/B))= =produto(d divide c)(B^phi(d).phi_d(A/B)). Como phi_d(x) é um polinômio mônico com coeficientes inteiros de grau phi(d), m_d:=B^phi(d).phi_d(A/B) é inteiro, e produto(d divide c)(m_d)=A^c-B^c (e logo m_d é divisor de A^c-B^c, para todo d divisor de c). Note que c tem 2^k divisores, e assim conseguimos escrever A^c-B^c como produto dos 2^k números m_d. Vamos agora examinar possíveis fatores primos comuns dos m_d. Vejamos primeiramente que se q é um primo que não divide mmc(d,r) então q não pode dividir simultaneamente m_d e m_r (desde que d seja distinto de r). De fato, f(x)=B^d.phi_d(x/B) e g(x)=B^r.phi_r(x/B) são fatores de x^mmc(d,r)-B^mmc(d,r), e se m_d=f(A) e m_r=g(A) são múltiplos de q, A é raiz pelo menos dupla de x^mmc(d,r)-B^mmc(d,r) módulo q (isto é, sobre o corpo Z/qZ), donde é raiz de sua derivada mmc(d,r).x^(mmc(d,r)-1). Como q não divide mmc(d,r), deve dividir A^(mmc(d,r)-1), donde divide A, mas A é primo com B, e logo q não divide d e portanto não pode pode dividir A^d-B^d, absurdo. Isso mostra que se q é um primo que divide dois termos distintos m_d e m_r então q tem que ser um dos divisores n_i de c, e nesse caso n_i deve ser um divisor de d ou de r, donde n_i divide no máximo um termo m_d sem que d seja múltiplo de n_i. Observemos agora que, se q é primo e q não divide r, então phi_(qr)(x)=phi_r(x^q)/phi_r(x), o que pode ser verificado a partir das raízes dos polinômios envolvidos. Se olharmos tudo módulo q (i.e., em Z/qZ[x]), temos phi_r(x^q)=(phi_r(x))^q (pois (x+y)^q=x^q+y^q mod q para quaisquer x,y e n^q=n mod q para n inteiro), donde phi_(qr)(x)=(phi_r(x))^(q-1) módulo q, donde phi_(qr)(x)=0 (mod q) se e só se phi_r(x)=0 (mod q) para todo x em Z/qZ. Em particular, fazendo q=n_i, x=A/B, e usando o fato de c (e logo todos os n_i) ser primo com B, temos que, se n_i não divide d, m_d é divisível por n_i se e só se n_i divide m_(n_i.d). Isso mostra que cada n_i divide no máximo dois termos m_r (para r=d e para r=n_i.d, se existir esse d divisor de c/n_i tal que n_i divide m_d). Assim, como A^c-B^c é produto dos 2^k números m_r, todos maiores que 1, e no máximo k pares desses números têm fator comum, A^c-B^c tem pelo menos 2^k-k fatores primos distintos. (cqd). Se k=1, c=p é primo e, pela prova acima, se A^c-B^c só tem um fator primo, A^c-B^c=A^p-B^p deve ser uma potência de p, e A-B também. Assim, A=B+p^k, e A^p-B^p=(B+p^k)^p-B^p=B^(p-1).p^(k+1) (mod p^(k+2)) se p=3 ou se p=2 e k1. Assim, nesses casos, a maior potência de p que divide A^p-B^p é p^(k+1), donde a maior potência de p que divide (A^p-B^p)/(A-B) é p, e logo A^(p-1)+A^(p-2).b+...+B^(p-1)=(A^p-B^p)/(A-B)=p (pois é uma potência de p), e logo 2^(p-1)=A^(p-1)p, absurdo. Assim, p=2 e k=1, donde A^p-B^p=(B+2)^2-B^2=4(B+1), que é uma potência de 2, donde B=2^m-1 e A=2^m+1, como havíamos dito no começo desta mensagem. Finalmente, se k=2, c=p.q, com pq, A^c-B^c=m_1.m_p.m_q.m_(pq), e, pela prova acima, se tivessemos exatamente 2=2^2-2 fatores primos distintos de A^c-B^c, esses fatores deveriam ser p e q. Assim, A^(pq)-B^(pq) é uma potência de p vezes uma potência de q, e logo (A^(pq)-B^(pq))/(A^p-B^p)=m_q.m_(pq) também é uma potência de p vezes uma potência de q. Se A^p-B^p é múltiplo de p, digamos A^p=B^p+k.p^r, onde p não divide k, A^(pq)-B^(pq)=(B^p+k.p^r)^q-B^(pq)=q.B^p.(k.p^r) (mod p^(2r)), donde é múltiplo de p^r e não de p^(r+1), e logo (A^(pq)-B^(pq))/(A^p-B^p) não é múltiplo de p. Por outro lado, se A^(pq)-B^(pq) é múltiplo de p, e A^p-B^p não é múltiplo de p, A^p/B^p não é 1 módulo p, mas (A^p/B^p)^q é 1 módulo q, donde a ordem módulo p de (A^p/B^p) é q, pois q é primo, mas q não divide phi(p)=p-1 (pois q é maior que p), absurdo. Assim, (A^(pq)-B^(pq))/(A^p-B^p) não é múltiplo de p e logo é uma potência de q. Assim, A^(pq)-B^(pq) é múltiplo de q, e, como A^(pq)=(A^p)^q é congruente a A6p módulo q, assim como B^(pq) é congruente a B^p módulo q, A^p-B^p também é múltiplo de q, digamos A^p=B^p+s.q^r, donde
Re: [obm-l] Problemas em aberto
Caros colegas: Seguem abaixo problemas propostos na lista obm-l desde outubro de 2004 que ainda nao foram resolvidos: []s, Claudio. 28) Seja A = conjunto dos inteiros positivos livres de quadrados e que tem um numero ímpar de fatores primos (distintos, claro!) Assim, A contém todos os primos e seu menor elemento composto é 30 = 2*3*5. Calcule o valor de Soma(n em A) 1/n^2. Pode usar, sem demonstrar, que: Soma(n em N) 1/n^2 = Pi^2/6 e Soma(n em N) 1/n^4 = Pi^4/90. Para s1, por fatoração única e convergência absoluta, soma(n=1 a infinito)(1/n^s)=produto(p primo)(1+1/p^s+1/p^(2s)+...)= =produto(p primo)(1-1/p^s)^(-1) (essa é a popular fórmula de Euler). Por razões análogas, se B = conjunto dos inteiros positivos livres de quadrados e que têm um numero ímpar de fatores primos distintos, soma(n em B)(1/n^2)-soma(n em A)(1/n^2)=produto(p primo)(1-1/p^2)= =(soma(n=1 a infinito)(1/n^2))^(-1)=6/pi^2, enquanto soma(n em B)(1/n^2)+soma(n em A)(1/n^2)=produto(p primo)(1+1/p^2)= =produto(p primo)((1-1/p^4)/(1-1/p^2))=(pi^2/6)/(pi^4/90)=15/pi^2. Assim, soma(n em A)(1/n^2)=(15/pi^2-6/pi^2)/2=9/(2.pi^2)= =0,45594532639051997149745758444377 Abraços, Gugu = 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] Problemas em aberto
Caro Domingos, Note que a diferenca entre as duas somas e' soma(p=n,k=2)[n/p^k]= soma(p=n)(n/p(p-1))=O(n) (aqui p percorre os primos), donde, como voce mostrou que uma das somas e' assintoticamente n.loglog(n), a outra automaticamente tambem e'. Note que voce so' usou ii), que e' mais facil de provar que i) (veja o Hardy e Wright). Alem disso, para ver que os limites sao infinitos, basta usar que a serie dos inversos dos primos da' infinito, o que provavelmente ja' foi provado nesta lista (senao me avisem que eu provo). Abracos, Gugu 20) Seja f: S = {2, 3, 4, 5, 6, ...} - S a função que leva um número n no seu número de fatores primos. Por exemplo, f(6) = 2 e f(12) = f(8) = 3. Quanto vale lim[n-inf] (f(2) + f(3) + ... + f(n))/(n-1)? A resposta é bonitinha quando f não conta os primos repetidamente... Vamos usar aquele princípio básico da combinatória que nos ensina a contar a mesma coisa de duas maneiras distintas :-) Note que f(2) + ... + f(n) é equivalente a Soma_{p primo} Piso{n/p}. Para verificar isso, disponha caixas indexadas por todos os primos = n. Olhe para cada elemento i = n, colocando um marcador na caixa p em cada primo p que é divisor de i. É evidente que o número de marcadores de todas as caixas é f(2) + ... + f(n). Por outro lado, quantos marcadores teremos numa caixa p? Cada inteiro i = n que é múltiplo de p colocou exatamente um marcador em tal caixa, logo temos Piso{n/p} marcadores em tal caixa. Sempre que o termo p aparecer, fica implícito que p é primo, ok? Como Piso{n/p} n/p - 1, temos: f(2) + ... + f(n) Soma_{p = n} [n/p - 1] = -pi(n) + n Soma_{p =n} [1/p], onde pi(n) é a função que conta o número de primos = n. Resultados clássicos nos grantem que: i) pi(n) ~ n/(log n) ii) Soma_{p =n} [1/p] ~ log log n, logo Soma_{p = n} [n/p - 1] ~ n[log log n - 1/(log n)]. Isso prova que lim_{n - oo} [f(2) + ... + f(n)]/n = oo. Como a nossa f tem valores sempre menores ou iguais aos valores da f do problema original, o resultado vale também para o problema original. Se f conta os primos de forma repetida então a nossa contagem passa a ser f(2) + ... + f(n) = Soma_{k = 0..oo} Soma_{p primo} Piso{n/p^k}. Talvez alguém da lista tenha paciência de analisar assintoticamente o mostrinho... [ ]'s = 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 = = 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] Problemas em aberto - prob 10
Caro Demetrio, No fim da sua explicacao, A-B nao pode ser uma potencia de y ? Nesse caso, todos os fatores primos de A-B sao fatores primos de y.A^(y-1), e eu nao entendi como voce conclui. Abracos, Gugu --- Claudio Buffara [EMAIL PROTECTED] escreveu: * 10) Seja P = A^c - B^c, onde: A, B e c são inteiros e primos entre si, A - B 1, c = n1*n2*...*ni*...nk , (os ni são fatores primos distintos, ou seja, c tem k fatores primos distintos). Mostre que P é um número composto com, no mínimo, k+1 fatores primos distintos. * Deixe eu colocar uma restrição adicional c = impar. Em primeiro lugar é fácil ver que todos os números da forma A^ni - B^ni dividem P. Portanto, um caminho seria mostrar que, dados quaisquer números da forma S1 = A^x - B^x e S2 = A^y - B^y, x e y primos entre si, S1 e S2 não podem ser múltiplos, isto é, possuem algum fator primo distinto entre si. 1** suponha A, B e x,y primos entre si. x e y primos diferentes de 2 e x y. Hipótese: se A^x - B^x tem fatores primos em comum com A^y - B^y, estes fatores estão em A - B. Suponha que S1 = A^x - B^x contém um fator em comum com S2 = A^y - B^y. Seja F1 = A^(x-y) * S2 = A^(x-y) * (A^y - B^y) = A^x - [A^(x-y)*(B^y)]. Naturalmente F1 contém o mesmo fator em comum com S1 e S2, e portanto F1 - S1 o conterá também. F1 - S1 = B^x - [A^(x-y)*(B^y)] = B^y * [B^(x-y) - A^(x-y)]. Dado que A e B são primos entre si, o fator comum não pode estar em B^y, e portanto está em B^(x-y) - A^(x-y). Agora pode-se repetir o raciocínio para B^(x-y) - A^(x-y) e A^y - B^y, verificando qual dos dois expoentes é maior. Suponhamos que x-y y. Neste caso podemos provar que o fator comum também está em B^(x-2y) - A^(x-2y). Observe que, caso y x-y provaríamos para o expoente 2y - x. Repetindo o raciocínio interativamente vamos chegar até o expoente 1. Note que, como x e y são primos, a sequencia de expoentes decrescentes não coincidirá com y. Por exemplo x = 19, y = 3. 19 - 16 - 13 - 10 - 7 - 4 -1 Por exemplo x = 17, y = 3. 17 - 14 - 11 - 8 - 5 - 2 -1 Por exemplo x = 19 y = 11. 19 - 8 - 3 (11 - 8) - 5 (8 - 3) - 2 (5 - 3) - 1 (3 - 2) 2** S2 = A^y - B^y também possui ao menos um fator primo distinto da decomposição em fatores primos de A - B. Note-se que S2 = (A - B) * F3, onde F3 = A^y-1 + (A^(y-2))*B + ... + B^y-1 Portanto, se a hipótese estiver correta e S2 contiver ao menos um fator primo distinto de A - B, este fator estará em F3 Note-se que F3 tem exatamente y termos. Se a Hipótese estiver incorreta, isto é, se A - B contiver todos os fatores primos de F3, então qualquer combinação linear do tipo k1*(A - B) + k2*F3 também conterá todos estes fatores. Esta idéia pode ser usada para reduzir-se os termos de F3 até um único termo que obrigatoriamente teria de conter todos os fatores primos. Por exemplo vamos considerar y = 3. Neste caso F3 = A^2 +A*B +B^2 F3 + A(A - B) = A^2 + A*B - A*B + B^2 = 2*A^2 + B^2 2*A^2 + B^2 + (A + B)*(A - B) = 2*A^2 + B^2 + A^2 - B^2 = 3*A^2 y = 5, F3=A^4 +A^3*B +A^2*B^2 +A*B^3 +B^4 F3 + A^3*(A - B) + A*B^2*(A - B) = 2*A^4 +2*A^2*B^2 +B^4 = X1 X1 + 2*A^2*(A + B)*(A - B) = X1 + 2*A^4 - 2*A^2*B^2= 4*A^4 + B^4 4*A^4 + B^4 + A^4 - B^4 = 5*A^4 Na verdade, caso (A - B) tenha todos os fatores primos de F3, é possível transformar F3 em outras expressões que devem conter os mesmos fatores primos, através de operações elementares, até uma expressão na forma y*A^y-1 (ou y*B^y-1). Mas vamos recordar que A,B e y são primos entre si, portanto não é possível que y*A^y-1 contenha os mesmos fatores primos de A - B. Em resumo, temos que **1** - Se S1 e S2 possuem fatores primos em comum, estes fatores estão em A - B. **2** - S1 e S2 possuem ao menos um fator primo não contido em A - B Logo S1 e S2 possuem ao menos um fator distinto entre si. A extensão para c par é direta fazendo A^2 - B^2 = D - C []´s ___ Yahoo! Acesso Grátis - Instale o discador do Yahoo! agora. http://br.acesso.yahoo.com/ - Internet rápida e grátis = 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 = = 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] Problemas em aberto - prob 10
Acho q vc tem razão... não me ocorre como consertar, exceto colocando uma restrição adicional. Acho que só vale para A-B e c, primos entre si. []´s --- Carlos Gustavo Tamm de Araujo Moreira [EMAIL PROTECTED] escreveu: Caro Demetrio, No fim da sua explicacao, A-B nao pode ser uma potencia de y ? Nesse caso, todos os fatores primos de A-B sao fatores primos de y.A^(y-1), e eu nao entendi como voce conclui. Abracos, Gugu --- Claudio Buffara [EMAIL PROTECTED] escreveu: * 10) Seja P = A^c - B^c, onde: A, B e c são inteiros e primos entre si, A - B 1, c = n1*n2*...*ni*...nk , (os ni são fatores primos distintos, ou seja, c tem k fatores primos distintos). Mostre que P é um número composto com, no mínimo, k+1 fatores primos distintos. * Deixe eu colocar uma restrição adicional c = impar. Em primeiro lugar é fácil ver que todos os números da forma A^ni - B^ni dividem P. Portanto, um caminho seria mostrar que, dados quaisquer números da forma S1 = A^x - B^x e S2 = A^y - B^y, x e y primos entre si, S1 e S2 não podem ser múltiplos, isto é, possuem algum fator primo distinto entre si. 1** suponha A, B e x,y primos entre si. x e y primos diferentes de 2 e x y. Hipótese: se A^x - B^x tem fatores primos em comum com A^y - B^y, estes fatores estão em A - B. Suponha que S1 = A^x - B^x contém um fator em comum com S2 = A^y - B^y. Seja F1 = A^(x-y) * S2 = A^(x-y) * (A^y - B^y) = A^x - [A^(x-y)*(B^y)]. Naturalmente F1 contém o mesmo fator em comum com S1 e S2, e portanto F1 - S1 o conterá também. F1 - S1 = B^x - [A^(x-y)*(B^y)] = B^y * [B^(x-y) - A^(x-y)]. Dado que A e B são primos entre si, o fator comum não pode estar em B^y, e portanto está em B^(x-y) - A^(x-y). Agora pode-se repetir o raciocínio para B^(x-y) - A^(x-y) e A^y - B^y, verificando qual dos dois expoentes é maior. Suponhamos que x-y y. Neste caso podemos provar que o fator comum também está em B^(x-2y) - A^(x-2y). Observe que, caso y x-y provaríamos para o expoente 2y - x. Repetindo o raciocínio interativamente vamos chegar até o expoente 1. Note que, como x e y são primos, a sequencia de expoentes decrescentes não coincidirá com y. Por exemplo x = 19, y = 3. 19 - 16 - 13 - 10 - 7 - 4 -1 Por exemplo x = 17, y = 3. 17 - 14 - 11 - 8 - 5 - 2 -1 Por exemplo x = 19 y = 11. 19 - 8 - 3 (11 - 8) - 5 (8 - 3) - 2 (5 - 3) - 1 (3 - 2) 2** S2 = A^y - B^y também possui ao menos um fator primo distinto da decomposição em fatores primos de A - B. Note-se que S2 = (A - B) * F3, onde F3 = A^y-1 + (A^(y-2))*B + ... + B^y-1 Portanto, se a hipótese estiver correta e S2 contiver ao menos um fator primo distinto de A - B, este fator estará em F3 Note-se que F3 tem exatamente y termos. Se a Hipótese estiver incorreta, isto é, se A - B contiver todos os fatores primos de F3, então qualquer combinação linear do tipo k1*(A - B) + k2*F3 também conterá todos estes fatores. Esta idéia pode ser usada para reduzir-se os termos de F3 até um único termo que obrigatoriamente teria de conter todos os fatores primos. Por exemplo vamos considerar y = 3. Neste caso F3 = A^2 +A*B +B^2 F3 + A(A - B) = A^2 + A*B - A*B + B^2 = 2*A^2 + B^2 2*A^2 + B^2 + (A + B)*(A - B) = 2*A^2 + B^2 + A^2 - B^2 = 3*A^2 y = 5, F3=A^4 +A^3*B +A^2*B^2 +A*B^3 +B^4 F3 + A^3*(A - B) + A*B^2*(A - B) = 2*A^4 +2*A^2*B^2 +B^4 = X1 X1 + 2*A^2*(A + B)*(A - B) = X1 + 2*A^4 - 2*A^2*B^2= 4*A^4 + B^4 4*A^4 + B^4 + A^4 - B^4 = 5*A^4 Na verdade, caso (A - B) tenha todos os fatores primos de F3, é possível transformar F3 em outras expressões que devem conter os mesmos fatores primos, através de operações elementares, até uma expressão na forma y*A^y-1 (ou y*B^y-1). Mas vamos recordar que A,B e y são primos entre si, portanto não é possível que y*A^y-1 contenha os mesmos fatores primos de A - B. Em resumo, temos que **1** - Se S1 e S2 possuem fatores primos em comum, estes fatores estão em A - B. **2** - S1 e S2 possuem ao menos um fator primo não contido em A - B Logo S1 e S2 possuem ao menos um fator distinto entre si. A extensão para c par é direta fazendo A^2 - B^2 = D - C []´s ___ Yahoo! Acesso Grátis - Instale o discador do Yahoo! agora. http://br.acesso.yahoo.com/ - Internet rápida e grátis = 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 = = Instruções para entrar na lista, sair da lista e usar a
Re: [obm-l] Problemas em aberto
Carlos Gustavo Tamm de Araujo Moreira wrote: Caro Domingos, Note que a diferenca entre as duas somas e' soma(p=n,k=2)[n/p^k]= soma(p=n)(n/p(p-1))=O(n) (aqui p percorre os primos), donde, como voce mostrou que uma das somas e' assintoticamente n.loglog(n) Já imaginava que fosse dar a mesma coisa :-) , a outra automaticamente tambem e'. Note que voce so' usou ii), que e' mais facil de provar que i) (veja o Hardy e Wright). Alem disso, para ver que os limites sao infinitos, basta usar que a serie dos inversos dos primos da' infinito, o que provavelmente ja' foi provado nesta lista (senao me avisem que eu provo). Você está dizendo que dá pra provar que o limite é +oo somente usando que a soma dos inversos dos primos diverge? Como seria a prova? Abraços, Domingos. = 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] Problemas em aberto
Caro Domingos, Você observou quef(2) + ... + f(n) é equivalente a Soma_{p primo} Piso{n/p}, mas isso é n.soma{p primo, p=n}(1/p) + O(n), donde isso dividido por n é soma{p primo, p=n}(1/p) + O(1), que tende a infinito pois a serie dos inversos dos primos diverge. Abraços, Gugu Carlos Gustavo Tamm de Araujo Moreira wrote: Caro Domingos, Note que a diferenca entre as duas somas e' soma(p=n,k=2)[n/p^k]= soma(p=n)(n/p(p-1))=O(n) (aqui p percorre os primos), donde, como voce mostrou que uma das somas e' assintoticamente n.loglog(n) Já imaginava que fosse dar a mesma coisa :-) , a outra automaticamente tambem e'. Note que voce so' usou ii), que e' mais facil de provar que i) (veja o Hardy e Wright). Alem disso, para ver que os limites sao infinitos, basta usar que a serie dos inversos dos primos da' infinito, o que provavelmente ja' foi provado nesta lista (senao me avisem que eu provo). Você está dizendo que dá pra provar que o limite é +oo somente usando que a soma dos inversos dos primos diverge? Como seria a prova? Abraços, Domingos. = 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 = = 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] Problemas em aberto
Carlos Gustavo Tamm de Araujo Moreira wrote: Caro Domingos, Você observou quef(2) + ... + f(n) é equivalente a Soma_{p primo} Piso{n/p}, mas isso é n.soma{p primo, p=n}(1/p) + O(n), donde isso dividido por n é soma{p primo, p=n}(1/p) + O(1), que tende a infinito pois a serie dos inversos dos primos diverge. Abraços, Gugu Era bem óbvio mas eu nem tinha percebido! Tudo bem, eu tenho uma boa desculpa, estou doente... [ ]'s = 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] Problemas em aberto - prob 10
--- Claudio Buffara [EMAIL PROTECTED] escreveu: * 10) Seja P = A^c - B^c, onde: A, B e c são inteiros e primos entre si, A - B 1, c = n1*n2*...*ni*...nk , (os ni são fatores primos distintos, ou seja, c tem k fatores primos distintos). Mostre que P é um número composto com, no mínimo, k+1 fatores primos distintos. * Deixe eu colocar uma restrição adicional c = impar. Em primeiro lugar é fácil ver que todos os números da forma A^ni - B^ni dividem P. Portanto, um caminho seria mostrar que, dados quaisquer números da forma S1 = A^x - B^x e S2 = A^y - B^y, x e y primos entre si, S1 e S2 não podem ser múltiplos, isto é, possuem algum fator primo distinto entre si. 1** suponha A, B e x,y primos entre si. x e y primos diferentes de 2 e x y. Hipótese: se A^x - B^x tem fatores primos em comum com A^y - B^y, estes fatores estão em A - B. Suponha que S1 = A^x - B^x contém um fator em comum com S2 = A^y - B^y. Seja F1 = A^(x-y) * S2 = A^(x-y) * (A^y - B^y) = A^x - [A^(x-y)*(B^y)]. Naturalmente F1 contém o mesmo fator em comum com S1 e S2, e portanto F1 - S1 o conterá também. F1 - S1 = B^x - [A^(x-y)*(B^y)] = B^y * [B^(x-y) - A^(x-y)]. Dado que A e B são primos entre si, o fator comum não pode estar em B^y, e portanto está em B^(x-y) - A^(x-y). Agora pode-se repetir o raciocínio para B^(x-y) - A^(x-y) e A^y - B^y, verificando qual dos dois expoentes é maior. Suponhamos que x-y y. Neste caso podemos provar que o fator comum também está em B^(x-2y) - A^(x-2y). Observe que, caso y x-y provaríamos para o expoente 2y - x. Repetindo o raciocínio interativamente vamos chegar até o expoente 1. Note que, como x e y são primos, a sequencia de expoentes decrescentes não coincidirá com y. Por exemplo x = 19, y = 3. 19 - 16 - 13 - 10 - 7 - 4 -1 Por exemplo x = 17, y = 3. 17 - 14 - 11 - 8 - 5 - 2 -1 Por exemplo x = 19 y = 11. 19 - 8 - 3 (11 - 8) - 5 (8 - 3) - 2 (5 - 3) - 1 (3 - 2) 2** S2 = A^y - B^y também possui ao menos um fator primo distinto da decomposição em fatores primos de A - B. Note-se que S2 = (A - B) * F3, onde F3 = A^y-1 + (A^(y-2))*B + ... + B^y-1 Portanto, se a hipótese estiver correta e S2 contiver ao menos um fator primo distinto de A - B, este fator estará em F3 Note-se que F3 tem exatamente y termos. Se a Hipótese estiver incorreta, isto é, se A - B contiver todos os fatores primos de F3, então qualquer combinação linear do tipo k1*(A - B) + k2*F3 também conterá todos estes fatores. Esta idéia pode ser usada para reduzir-se os termos de F3 até um único termo que obrigatoriamente teria de conter todos os fatores primos. Por exemplo vamos considerar y = 3. Neste caso F3 = A^2 +A*B +B^2 F3 + A(A - B) = A^2 + A*B - A*B + B^2 = 2*A^2 + B^2 2*A^2 + B^2 + (A + B)*(A - B) = 2*A^2 + B^2 + A^2 - B^2 = 3*A^2 y = 5, F3=A^4 +A^3*B +A^2*B^2 +A*B^3 +B^4 F3 + A^3*(A - B) + A*B^2*(A - B) = 2*A^4 +2*A^2*B^2 +B^4 = X1 X1 + 2*A^2*(A + B)*(A - B) = X1 + 2*A^4 - 2*A^2*B^2= 4*A^4 + B^4 4*A^4 + B^4 + A^4 - B^4 = 5*A^4 Na verdade, caso (A - B) tenha todos os fatores primos de F3, é possível transformar F3 em outras expressões que devem conter os mesmos fatores primos, através de operações elementares, até uma expressão na forma y*A^y-1 (ou y*B^y-1). Mas vamos recordar que A,B e y são primos entre si, portanto não é possível que y*A^y-1 contenha os mesmos fatores primos de A - B. Em resumo, temos que **1** - Se S1 e S2 possuem fatores primos em comum, estes fatores estão em A - B. **2** - S1 e S2 possuem ao menos um fator primo não contido em A - B Logo S1 e S2 possuem ao menos um fator distinto entre si. A extensão para c par é direta fazendo A^2 - B^2 = D - C []´s ___ Yahoo! Acesso Grátis - Instale o discador do Yahoo! agora. http://br.acesso.yahoo.com/ - Internet rápida e grátis = 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] Problemas em aberto
--- Claudio Buffara [EMAIL PROTECTED] escreveu: Caros colegas: Seguem abaixo problemas propostos na lista obm-l desde outubro de 2004 que ainda nao foram resolvidos: []s, Claudio. * 20) Seja f: S = {2, 3, 4, 5, 6, ...} - S a função que leva um número n no seu número de fatores primos. Por exemplo, f(6) = 2 e f(12) = f(8) = 3. Quanto vale lim[n-inf] (f(2) + f(3) + ... + f(n))/(n-1)? * 21) E se f associar n ao seu número de fatores primos *distintos*? Por exemplo, f(6) = 2 mas f(12) = 2 e f(8) = 1? Creio que este problema é muito avançado. Não sei demonstrar mas referências e a resposta podem ser encontradas em http://mathworld.wolfram.com/DistinctPrimeFactors.html []´s ___ Yahoo! Acesso Grátis - Instale o discador do Yahoo! agora. http://br.acesso.yahoo.com/ - Internet rápida e grátis = 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] Problemas em aberto
20) Seja f: S = {2, 3, 4, 5, 6, ...} - S a função que leva um número n no seu número de fatores primos. Por exemplo, f(6) = 2 e f(12) = f(8) = 3. Quanto vale lim[n-inf] (f(2) + f(3) + ... + f(n))/(n-1)? A resposta é bonitinha quando f não conta os primos repetidamente... Vamos usar aquele princípio básico da combinatória que nos ensina a contar a mesma coisa de duas maneiras distintas :-) Note que f(2) + ... + f(n) é equivalente a Soma_{p primo} Piso{n/p}. Para verificar isso, disponha caixas indexadas por todos os primos = n. Olhe para cada elemento i = n, colocando um marcador na caixa p em cada primo p que é divisor de i. É evidente que o número de marcadores de todas as caixas é f(2) + ... + f(n). Por outro lado, quantos marcadores teremos numa caixa p? Cada inteiro i = n que é múltiplo de p colocou exatamente um marcador em tal caixa, logo temos Piso{n/p} marcadores em tal caixa. Sempre que o termo p aparecer, fica implícito que p é primo, ok? Como Piso{n/p} n/p - 1, temos: f(2) + ... + f(n) Soma_{p = n} [n/p - 1] = -pi(n) + n Soma_{p =n} [1/p], onde pi(n) é a função que conta o número de primos = n. Resultados clássicos nos grantem que: i) pi(n) ~ n/(log n) ii) Soma_{p =n} [1/p] ~ log log n, logo Soma_{p = n} [n/p - 1] ~ n[log log n - 1/(log n)]. Isso prova que lim_{n - oo} [f(2) + ... + f(n)]/n = oo. Como a nossa f tem valores sempre menores ou iguais aos valores da f do problema original, o resultado vale também para o problema original. Se f conta os primos de forma repetida então a nossa contagem passa a ser f(2) + ... + f(n) = Soma_{k = 0..oo} Soma_{p primo} Piso{n/p^k}. Talvez alguém da lista tenha paciência de analisar assintoticamente o mostrinho... [ ]'s = 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] Problemas em aberto
Caros colegas: Seguem abaixo problemas propostos na lista obm- l desde outubro de 2004 que ainda nao foram resolvidos: []s, Claudio. * 3) Decomponha o numero real positivo A numa soma de parcelas positivas: x_1 + x_2 + ... + x_r = A de forma que o produto x_1*x_2*...*x_r seja o maior possivel. (ninguem falou que as parcelas precisam ser inteiras) Para r fixo, sabemos que o produto eh maximo se as parcelas forem iguais. Isto pode ser provado por varias formas, tais como calculo, inducao finita, desigualdade das medias aritmetica e geometrica (que talvez seja a mais simples). Para r fixo, temos entao que o produto p(r) eh dado por p(r) = (A/r)^r, r inteiro positivo. Para x0, podemos encontrar o maximo da funcao p(x) = (A/x)^x diferenciando-se p e obtendo p'(x) = (A/x)*[ln(A/x) + x*(-1/x)] = A/x)*[ln(A/x) - 1]. Vemos que p' se anula se e somente se x = x* = A/e e que p' eh negativa em (0, A/e) e positiva em (A/e, oo). Logo, p alcanca um maximo global em x* = A/e. Mas r tem que ser inteiro e A/e, de modo geral, nao eh inteiro. Com p eh estritamente crescente em (0, A/e) e estritamente decrescente em (A/e, oo), precisamos computar f em x1 e x2, sendo x1 = piso(A/e) e x2 = teto(A/e). Se A/e for inteiro, teremos que x1 = x2 = r* = A/e eh o ponto de maximo. Caso contrario, teremos que comparar p(x1) e p(x2), ecolhendo o que der maior valor para p. Acho que nao dah para determinar analiticamente r8 em funcao de A. Artur OPEN Internet e Informática @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = 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] Problemas em aberto
10) Seja P = A^c - B^c, onde: A, B e c são inteiros e primos entre si, A - B 1, c = n1*n2*...*ni*...nk , (os ni são fatores primos distintos, ou seja, c tem k fatores primos distintos). Mostre que P é um número composto com, no mínimo, k+1 fatores primos distintos. Isso eh falso. Tome A = 5, B = 3 e c = 2. Claro que A, B e c satisfazem o enunciado e temos k = 1. Porem P = 16 = 2^4 soh tem 1 fator primo distinto ao inves de 2. Porem eh verdadeiro que P possui ao menos k + 1 fatores primos nao necessariamente distintos se c for o produto de k primos nao necessariamente distintos, o que se prova facilmente por inducao sobre k e pela famosa fatoracao A^(xy) - B^(xy) = (A^x - B^x)(A^[x(y-1)] + ... + A^[x(y - i)]*B^ (xi) + ... + B^[x(y - 1)]). []s, Daniel = 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] Problemas em aberto
16) Ache o menor inteiro positivo tal que se deslocarmos o seu algarismo mais a esquerda para a posicao mais a direita (ou seja, das unidades) obteremos um inteiro uma vez e meia maior do que o original. Seja k = a_n*10^n + a_(n-1)*10^(n-1) + ... + 1_a*10 + a_0, onde 0=a_i=9 com a_n 0. Após a mudança, obtemos t = a_(n-1)*10^n + a_(n-2)*10^(n-1) + ... + a_1*10^2 + a_0*10 + a_n = 10*k - a_n*10^(n+1) + a_n = 10*k - a_n*(10^(n+1) - 1). A condição é 2*t = 3*k, o que implica 20*k - 2*a_n*(10^(n+1) - 1) = 3*k == 17*k = 2*a_n*(10^(n+1) - 1). Primeiramente, 17 tem que dividir 10^(n+1) - 1, ou seja, 10^(n+1) == 1 (mod 17). Sabemos por Euler-Fermat que para n = 15 isso ocorre. Agora, pensando no grupo Z/(17_Z), e usando Lagrange, qualquer outro (n+1) menor e que satisfaça a igualdade deverá ser divisor de 16. Ou seja, n = 0, 1, 3 ou 7. A minha calculadora diz que isso não vale para nenhum destes valores de n. Logo, n = 15 é o menor possível. Resta mostrar que para algum a_n tem-se k = 2*a_n*(10^(n+1) - 1)/17 um número com no máximo n casas decimais, ou seja, k = 10^(n+1) - 1. Mas é imediato que k 10^(n+1) - 1 para a_n = 1, o que mostra que o menor inteiro positivo satisfazendo a relação é 2*(10^(n+1) - 1)/17. []s, Daniel = 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] Problemas em aberto (remate do 16)
16) Ache o menor inteiro positivo tal que se deslocarmos o seu algarismo mais a esquerda para a posicao mais a direita (ou seja, das unidades) obteremos um inteiro uma vez e meia maior do que o original. Seja k = a_n*10^n + a_(n-1)*10^(n-1) + ... + 1_a*10 + a_0, onde 0=a_i=9 com a_n 0. (...) Logo, n = 15 é o menor possível. Resta mostrar que para algum a_n tem-se k = 2*a_n*(10^(n+1) - 1)/17 um número com no máximo n casas decimais, ou seja, k = 10^(n+1) - 1. Mas é imediato que k 10^(n+1) - 1 para a_n = 1, o que mostra que o menor inteiro positivo satisfazendo a relação é 2*(10^(n+1) - 1)/17. Na verdade existe um outro erro aí além do número n de casas em vez de n+1 É preciso mostrar que para algum a_n tem-se k = 2*a_n*(10^(n+1) - 1)/17, onde n = 15, um número com EXATAMENTE n + 1 casas decimais E CUJO PRIMEIRO DÍGITO É DE FATO a_n. Ou seja, exibir um a_n tal que valham as desigualdades a_n*10^n= k = 2*a_n*(10^(n+1) - 1)/17 = (a_n + 1)*10^n - 1 Começando pela esquerda: 17*a_n*10^n = 2_a_n*(10^(n+1) - 1) == 17*10^n = 20*10^n - 2 == 2 = 3*10^n, que vale sempre. Para a desigualdade da direita, temos: 2*a_n*(10^(n+1) - 1) = 17*(a_n + 1)*10^n - 17 == 20*a_n*10^n - 2*a_n = 17*(a)n + 1)*10^n - 17 == 3*a_n*10^n + 17 = 17*10^n + 2*a_n Em particular, a_n = 1 satisfaz essa relação, e portanto é legítimo dar o problema por concluído tomando-se k = 2*(10^16 - 1)/17, um número, de fato, com exatamente 16 casas decimais e cujo dígito mais à esquerda é 1. []s, Daniel = 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] Problemas em aberto
7) Ache todos os primos p tais que (2^(p-1) - 1)/p eh quadrado perfeito. Este problema ja esta resolvido numa Eureka! E bem interessante alias. Depois dou a referencia (a rede esta horrivel!) ___ Yahoo! Acesso Grátis - Instale o discador do Yahoo! agora. http://br.acesso.yahoo.com/ - Internet rápida e grátis = 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] Problemas em aberto
1) Construir uma estrutura rígida usando apenas três varetas rígidas de mesmo comprimento e barbante, de modo que duas varetas quaisquer não se toquem. 3) Decomponha o numero real positivo A numa soma de parcelas positivas: x_1 + x_2 + ... + x_r = A de forma que o produto x_1*x_2*...*x_r seja o maior possivel. (ninguem falou que as parcelas precisam ser inteiras) Caro Claudio, só você para me fazer cortar fios de cobre e pedaços de barbante num dia como esse... Mas é possível! Não ficou muito bonito (a obra está claramente mais ligada a OBM que ao MAM), mas dá pra se entender... o resultado é um octaedro não-regular, em que as varetas são as diagonais internas, e as arestas são de barbante. Já o (3) faz parte da solução do ¨água e cachaça¨, que propus há muito. Era essa a idéia? Em relação ao (6): ainda hoje escrevo a solução combinatória do ¨amigo oculto¨, ok? Grande abraço e ótimo 2005! Rogério. PS: e o chopp com o Prof. Morgado? _ MSN Messenger: converse online com seus amigos . 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 =
Re:[obm-l] Problemas em Aberto
eu queria ver como a larissa lima iria resolver esse, ela sempre tem uma carta escondida na manga. Aqui vai outra solucao (longa) ... Eu ainda gostaria de ver uma solucao grega pra esse problema. 2. Três lados consecutivos de um quadrilátero convexo são a, b e c. Determine o quadrilátero de área máxima . Seja ABCD o quadrilatero, de forma que: AB = a, BC = b, CD = c. Ponhamos AC = x. Entao, 2*[ABCD] = a*b*sen(ABC) + c*x*sen(ACD) Lei dos Cossenos == x = raiz(a^2 + b^2 - 2*a*b*cos (ABC)). Assim: 2*[ABCD] = a*b*sen(ABC) + c*raiz(a^2 + b^2 - 2*a*b*cos(ABC))*sen(ACD). Ou seja, temos duas variaveis independentes para escolher: ABC e ACD. Eh facil ver que 2*[ABCD] maximo == sen(ACD) maximo == sen(ACD) = 1 == ACD = Pi/2 == 2*[ABCD]max = a*b*sen(ABC) + c*raiz(a^2 + b^2 - 2*a*b*cos(ABC)) Pondo cos(ABC) = t, teremos sen(ABC) = raiz(1 - t^2) = 0, pois 0 = ABC = Pi. Se F(t) = 2*[ABCD], entao: F(t) = a*b*raiz(1 - t^2) + c*raiz(a^2 + b^2 - 2*a*b*t) Naturalmente, F(t) serah maximo para t em [-1,0]. Para achar os pontos criticos de F, temos que calcular F'(t): F'(t) = -a*b*t/raiz(1 - t^2) - a*b*c/raiz(a^2 + b^2 - 2*a*b*t) F'(0) = -a*b*c/raiz(a^2+b^2) 0 F'(t) - +infinito quando t - -1 pela direita. Logo, t = 0 e t = -1 nao sao pontos de maximo. Assim, o ponto de maximo estarah no intervalo (-1,0) F'(t) = 0 == t/raiz(1 - t^2) = - c/raiz(a^2 + b^2 - 2*a*b*t) == t^2/(1 - t^2) = c^2/(a^2 + b^2 - 2*a*b*t) e -1 t 0 (*) Como o triangulo ACD eh retangulo em C, teremos que cos(ADC) = CD/AD. Pondo cos(ADC) = s 0 (pois ADC Pi/2), teremos: s = c/raiz(c^2+x^2) = c/raiz(a^2 + b^2 + c^2 - 2*a*b*t) == s^2 = c^2/(a^2 + b^2 + c^2 - 2*a*b*t) == s^2/(1 - s^2) = c^2/(a^2 + b^2 - 2*a*b*t) (**) (*) e (**) == t^2/(1 - t^2) = s^2/(1 - s^2) == t^2 = s^2 == t = -s, pois t 0 e s 0 == cos(ABC) = -cos(ADC) == ABC = Pi - ADC == ABCD eh ciclico Alem disso, como o triangulo ACD eh retangulo, AD serah o diametro do circulo circunscrito a ABCD. Interessante observar que para obtermos o valor de t = cos(ABC), precisaremos resolver uma equacao do 3o. grau: 2*a*b*t^3 - (a^2 + b^2 + c^2)*t^2 + c^2 = 0 (t serah a raiz negativa dessa equacao) []s, Claudio. === == 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 === == Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.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 =
Re: [obm-l] Problemas em Aberto
2. Três lados consecutivos de um quadrilátero convexo são a, b e c. Determine o quadrilátero de área máxima . Algumas consideracoes intuitivas (*) me levaram a crer tal quadrilatero eh inscritivel e seu quarto lado eh o diametro do circulo circunscrito a ele. Verifiquei essa conjectura para diversos valores de a,b,c num programa que fiz em MAPLE (**) e o resultado foi sempre confirmado [ ]'s Eric = CONSIDERACOES INTUITIVAS (*) Seja ABCD uma linha poligonal com a = AB, b = BC, c = CD; aumente o angulo B (gerando um novo ponto A' com a = A'B) e desenhe linhas tracejadas ligando AD e A'D; verifique as areas ganhas e perdidas; Note que havera ganho de area para o quadrilatero ABCD quando a area do triangulo DAA' for maior que a area do triangulo BAA' e como estes triangulos tem mesma base AA', o ganho de area so ocorrera quando a altura de DAA' for maior que a de BAA'. Seja agora um aumento muito pequeno do angulo B (aumento infinitesimal) Nao havera nem ganho nem perda de area (infinitesimal) quando as alturas de BAA' e DAA' sao iguais (ponto de extremo relativo), isto eh, quando o angulo ABD = Pi/2. Do mesmo modo prova-se que o angulo ACD = Pi/2. = (**) Programa Maple (10Kb, em caso de interesse mando por e-mail) FIM. = 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] Problemas em Aberto
Acho que dá para pensar assim: AB = lado a BC = lado b CD = lado c DA = lado d A área do quadrilátero pode ser calculada como a área do triângulo ABC + área do triângulo ACD. Vamos supor que conhecemos a configuração final, de área máxima, apenas para os pontos ABC. Ou seja, dada qualquer configuração do triângulo ABC, como o comprimento CD é fixo, fica fácil ver que a posição do ponto D para a área máxima vai ocorrer apenas quando o triângulo ACD for retângulo em C. Daí fica fácil, basta repetir o mesmo raciocínio utilizando como referência a outra diagonal. -Original Message- From: Eric [mailto:[EMAIL PROTECTED] Sent: Wednesday, June 02, 2004 1:21 PM To: [EMAIL PROTECTED] Subject: [obm-l] Problemas em Aberto 2. Tres lados consecutivos de um quadrilatero convexo sao a, b e c. Determine o quadrilatero de area maxima . Fiz um programa em Maple que dados os lados a,b,c (em ordem) do quadrilatero, encontra os angulos x e y entre os lados a,b e b,c respectivamente que tornam a area do quadrilatero maxima. Alem disso o programa encontra essa area maxima e faz dois tipos diferentes de testes para verificar o resultado. Um deles comparando a area maxima encontrada com 1000 areas calculadas aleatoriamente para diferentes valores de x e y entre Pi/2 e Pi. Alem desse teste tambem uso o teste da derivada segunda para funcoes de duas variaveis, mas por algum motivo que nao compreendo totalmente este teste nao funciona sempre (por exemplo, nao funciona para (a,b,c)=(1,1,1), onde x=y=2Pi/3, nem para (a,b,c)=(1,1,6)) (pode ser algum erro de programacao minha). Segue abaixo alguns resultados encontrados pelo programina (se alguem achar um erro me comunique para que eu faca as correcoes no programa). Fora o primeiro, os outros valores estao aproximados (os angulos x, y estao em radianos). (a,b,c)(x,y)Area maxima encontrada (1,1,1) (2Pi/3,2Pi/3) 3*(3^(1/2))/4 (1,2,1) (1.94553; 1.94553)2.20183 (1,2,3) (2.38820; 1.81638)4.90482 (2,3,1) (1.81638; 2.07859)4.90482 (1,1,6) (2.82363; 1.72977)6.08065 para (a,b,c) = (1,1,1) ou (1,1,6) o teste fornece valores que nao passam no teste da derivada segunda (usa uma matriz hessiana 2x2 (acho que o nome eh esse)). Minha duvida eh justamente essa: sera que as primeira e ultima areas encontradas sao mesmo maximas? Elas passam no teste de comparacao com 1000 areas calculadas aleatoriamente, mas nao passam no teste da derivada segunda... OBS: teste da derivada segunda para funcoes de duas variaveis: (f_xx)(f_yy) - (f_xy)^2 0 e f_xx 0 == maximo local de f [ ]'s Eric. = 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 = = 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] Problemas em Aberto
bom sendo assim admitimos que sabemos que os triang. sao retangulos, ou seja, esse quadrilatero é inscritivel e CD é diametro... mais como eu faço isso alguma sugestao? to quebrando a cabeça aki... Acho que dá para pensar assim: AB = lado a BC = lado b CD = lado c DA = lado d A área do quadrilátero pode ser calculada como a área do triângulo ABC + área do triângulo ACD. Vamos supor que conhecemos a configuração final, de área máxima, apenas para os pontos ABC. Ou seja, dada qualquer configuração do triângulo ABC, como o comprimento CD é fixo, fica fácil ver que a posição do ponto D para a área máxima vai ocorrer apenas quando o triângulo ACD for retângulo em C. Daí fica fácil, basta repetir o mesmo raciocínio utilizando como referência a outra diagonal. -Original Message- From: Eric [mailto:[EMAIL PROTECTED] Sent: Wednesday, June 02, 2004 1:21 PM To: [EMAIL PROTECTED] Subject: [obm-l] Problemas em Aberto 2. Tres lados consecutivos de um quadrilatero convexo sao a, b e c. Determine o quadrilatero de area maxima . Fiz um programa em Maple que dados os lados a,b,c (em ordem) do quadrilatero, encontra os angulos x e y entre os lados a,b e b,c respectivamente que tornam a area do quadrilatero maxima. Alem disso o programa encontra essa area maxima e faz dois tipos diferentes de testes para verificar o resultado. Um deles comparando a area maxima encontrada com 1000 areas calculadas aleatoriamente para diferentes valores de x e y entre Pi/2 e Pi. Alem desse teste tambem uso o teste da derivada segunda para funcoes de duas variaveis, mas por algum motivo que nao compreendo totalmente este teste nao funciona sempre (por exemplo, nao funciona para (a,b,c)=(1,1,1), onde x=y=2Pi/3, nem para (a,b,c)=(1,1,6)) (pode ser algum erro de programacao minha). Segue abaixo alguns resultados encontrados pelo programina (se alguem achar um erro me comunique para que eu faca as correcoes no programa). Fora o primeiro, os outros valores estao aproximados (os angulos x, y estao em radianos). (a,b,c)(x,y)Area maxima encontrada (1,1,1) (2Pi/3,2Pi/3) 3*(3^(1/2))/4 (1,2,1) (1.94553; 1.94553)2.20183 (1,2,3) (2.38820; 1.81638)4.90482 (2,3,1) (1.81638; 2.07859)4.90482 (1,1,6) (2.82363; 1.72977)6.08065 para (a,b,c) = (1,1,1) ou (1,1,6) o teste fornece valores que nao passam no teste da derivada segunda (usa uma matriz hessiana 2x2 (acho que o nome eh esse)). Minha duvida eh justamente essa: sera que as primeira e ultima areas encontradas sao mesmo maximas? Elas passam no teste de comparacao com 1000 areas calculadas aleatoriamente, mas nao passam no teste da derivada segunda... OBS: teste da derivada segunda para funcoes de duas variaveis: (f_xx)(f_yy) - (f_xy)^2 0 e f_xx 0 == maximo local de f [ ]'s Eric. === == 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 === == === == 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 === == Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.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 =
Re: [obm-l] Problemas em Aberto
2. Tres lados consecutivos de um quadrilatero convexo sao a, b e c. Determine o quadrilatero de area maxima . on 02.06.04 14:25, João Gilberto Ponciano Pereira at [EMAIL PROTECTED] wrote: Acho que dá para pensar assim: AB = lado a BC = lado b CD = lado c DA = lado d A área do quadrilátero pode ser calculada como a área do triângulo ABC + área do triângulo ACD. Vamos supor que conhecemos a configuração final, de área máxima, apenas para os pontos ABC. Ou seja, dada qualquer configuração do triângulo ABC, como o comprimento CD é fixo, fica fácil ver que a posição do ponto D para a área máxima vai ocorrer apenas quando o triângulo ACD for retângulo em C. Daí fica fácil, basta repetir o mesmo raciocínio utilizando como referência a outra diagonal. Tudo bem, isso prova se [ABCD] eh maxima, entao ABCD eh ciclico e AD eh o diametro, mas dado o segmento BC (de medida b) e as medidas dos lados AB (a) e CD (c), como fazer para construir ABCD convexo de area maxima? Essa seriua a solucao grega a que me referi na minha msg anterior. []s, Claudio. = 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] Problemas em Aberto
Eu acho que, nesse caso, e so usar a Desigualdade Isoperimetrica (a demo do Gugu, para ser mais especifico...). Depois, acho que um pouco de Desigualdade das Medias deve sair.Vou fazer as contas em casa e depois eu divulgo algo alem de meras suposiçoes... Claudio Buffara [EMAIL PROTECTED] wrote: on 31.05.04 16:25, niski at [EMAIL PROTECTED] wrote: 2. Três lados consecutivos de um quadrilátero convexo são a, b e c. Determine o quadrilátero de área máxima . Bom a area de um quadrilatero ciclico (que pode ser inscrito num circulo) é a maior possivel para qualquer quadrilatero com lados dados.E demonstrar isso eh um bom exercicio de trigonometria.Soh que o quarto lado nao eh dado. Serah que, mesmo assim, o quadrilatero demaior area eh o inscritivel? E a area deste quadrilatero ciciclo pode ser dada como sqrt((s-a)(s-b)(s-c)(s-d)) onde s é o semiperimetro, talvez derivando e pesquisando pontos de maximo e minimo saia a resposta..Se concluirmos que o quadrilatero de area maxima eh o inscritivel, nao haduvidas. Soh que voce vai cair numa equacao de 3o. grau em d.Eu me pergunto se nao ha uma solucao mais elementar.[]s,Claudio.=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html= TRANSIRE SVVM PECTVS MVNDOQVE POTIRI CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE Fields Medal(John Charles Fields) N.F.C. (Ne Fronti Crede)Yahoo! Mail - Participe da pesquisa global sobre o Yahoo! Mail. Clique aqui!
Re: [obm-l] Problemas em Aberto
O problema e que esse quadrilatero e muito livre. Ou seja, e dificil demais(e eu to achando impossivel) que voce ache x sem inserir novos dados. Com isso, acho quex e um dos parametros de liberdade do quadrilatero ciclico. Assim sendo, ce tem uma equaçao de grau 2 em cosn x e com isso, a maximizaçao seja facil. Uma pergunta mais chata: e possivel determinar os maximos e minimos de um polinomio de grau 2t sem (a principio) usar derivada? Explicando: defina a derivada de um polinomio como o nao-usual : (d/dx)(x^n)=n*x^(n-1) Soma de derivadas=derivada da soma Prove que os maximos e minimos dum polinomioestao entre as raizes da suaderivada. Osvaldo [EMAIL PROTECTED] wrote: E ai Niski!Eu tentei fazer supondo que fosse mesmo inscritível e dpois usar bramagupta, como vc sugeriu, mais nao encontrei um dos angulos ai, vc tem uma dica pra mim?Seja ABCD tal quadrilátero e a, b, c e d os lados AB, BC. CD e DA respectivamente. É facil ver que med(ABC) = me(CDA) pois "enxergam" uma mesma corda de uma certa circunferência.I) T. cos. tring. ABC: AC=sqrt(a^2+b^2-2abcosx); onde med(ABC)=xII) T. cos. triang. CDA:AC=sqrt(c^2+d^2-2cdcosx)De I e II podemos tirar d em função de a, b e c e x:c^2+d^2-2cdcosx=a^2+b^2-2abcosx=d^2+(-2c cosx)d+(c^2-a^2-b^2+2abcosx)Daí d=c.cos(x)+sqrt(c^2.(cosx)^2-c^2+a^2+b^2-2abcosx)Preciso achar x.Tentei pelo T. dos senos, mais nao saiu.Tentei usar o T. la que fala que o produto das diagonais é a soma dos produtos dos lados opostos, tudo em vão.Alguem sabe como acho esse bendito angulo?falow ! on 31.05.04 16:25, niski at [EMAIL PROTECTED] wrote: 2. Três lados consecutivos de um quadrilátero convexo são a, b e c. Determine o quadrilátero de área máxima .Bom a area de um quadrilatero ciclico (que pode ser inscrito num circulo) é a maior possivel para qualquer quadrilatero com lados dados. E demonstrar isso eh um bom exercicio de trigonometria. Soh que o quarto lado nao eh dado. Serah que, mesmo assim, o quadrilatero de maior area eh o inscritivel? E a area deste quadrilatero ciciclo pode ser dada como sqrt((s-a)(s-b)(s-c)(s-d)) onde s é o semiperimetro, talvez derivando e pesquisando pontos de maximo e minimo saia a resposta.. Se concluirmos que o quadrilatero de area maxima eh o inscritivel, nao ha duvidas. Soh que voce vai cair numa equacao de 3o. grau em d. Eu me pergunto se nao ha uma solucao mais elementar. []s, Claudio. = 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 = Atenciosamente,Engenharia Elétrica - UNESP Ilha SolteiraOsvaldo Mello Sponquiado Usuário de GNU/Linux__Acabe com aquelas janelinhas que pulam na sua tela.AntiPop-up UOL - É grátis!http://antipopup.uol.com.br/=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html= TRANSIRE SVVM PECTVS MVNDOQVE POTIRI CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE Fields Medal(John Charles Fields) N.F.C. (Ne Fronti Crede)Yahoo! Mail - Participe da pesquisa global sobre o Yahoo! Mail. Clique aqui!
Re: [obm-l] Problemas em Aberto
2. Três lados consecutivos de um quadrilátero convexo são a, b e c. Determine o quadrilátero de área máxima . As vezes da vontade de voltar no tempo e prestar atencao no que e dito em sala de aula. Eu tenho uma suspeita pra essa questao, mas nao sei nem por onde comecar, entao vou so dar uma de maluco e mandar assim: a area maxima e A= (a+c)/2*b. Eu tava pensando que se vc tem um triangulo tipo LAL (lado-angulo-lado) nao deve ser dificil provar que a area desse triangulo e maxima quando A = pi/2. Se eu soubesse alguma coisa de matematica eu apartir dai ia tentar provar que a area e maxima quando o maior numero de angulos internos e pi/2. Dai ia concluir a//c e chegava na area que escrevi no comeco. Como nao sei nada escrevo essa ideia maluca porque pode ou dar um estalo em quem entende do assunto ou pelo menos fazer rir _ Express yourself with the new version of MSN Messenger! Download today - it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/ = 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] Problemas em Aberto
on 01.06.04 16:11, Qwert Smith at [EMAIL PROTECTED] wrote: 2. Três lados consecutivos de um quadrilátero convexo são a, b e c. Determine o quadrilátero de área máxima . As vezes da vontade de voltar no tempo e prestar atencao no que e dito em sala de aula. Eu tenho uma suspeita pra essa questao, mas nao sei nem por onde comecar, entao vou so dar uma de maluco e mandar assim: a area maxima e A= (a+c)/2*b. Isso eh consequencia do teorema de Chutagoras... Voce tambem podia ter usado o metodo das acoxambracoes sucessivas. Eu tava pensando que se vc tem um triangulo tipo LAL (lado-angulo-lado) nao deve ser dificil provar que a area desse triangulo e maxima quando A = pi/2. Area = (1/2)*a*b*sen(C). Se a e b sao fixos, entao: A serah maxima == sen(C) = 1 == C = Pi/2. Se eu soubesse alguma coisa de matematica eu apartir dai ia tentar provar que a area e maxima quando o maior numero de angulos internos e pi/2. Eu pensei nisso tambem, mas veja o que aconteceu: Seja ABCD o quadrilatero, de forma que: AB = a, BC = b, CD = c. Ponha AC = x. Entao, 2*[ABCD] = a*b*sen(ABC) + c*x*sen(ACD) Lei dos Cossenos == x = raiz(a^2 + b^2 - 2*a*b*cos(ABC)). Assim: 2*[ABCD] = a*b*sen(ABC) + c*raiz(a^2 + b^2 - 2*a*b*cos(ABC))*sen(ACD). Ou seja, temos duas variaveis independentes para escolher: ABC e ACD. Eh facil ver que 2*[ABCD] maximo == sen(ACD) maximo == sen(ACD) = 1 == ACD = Pi/2 == 2*[ABCD]max = a*b*sen(ABC) + c*raiz(a^2 + b^2 - 2*a*b*cos(ABC)) Pondo cos(ABC) = t, teremos sen(ABC) = raiz(1 - t^2) = 0, pois 0 = ABC = Pi. Se F(t) = 2*[ABCD], entao: F(t) = a*b*raiz(1 - t^2) + c*raiz(a^2 + b^2 - 2*a*b*t) Nesse ponto, nao eh obvio que devemos ter ABC = Pi/2 (t = 0), pois se Pi/2 ABC Pi, t = cos(ABC) serah negativo, o que aumentarah ainda mais o radicando, apesar de reduzir a primeira parcela. De qualquer forma, F(t) serah maximo para t no intervalo [-1,0] (eh soh olhar e ver). Se t = -1, entao ABC = 0 e o quadrilatero de area maxima degenera no triangulo ACD, cuja area eh igual a (1/2)*(a+b)*c. Se t = 0,entao [ABCD] = (1/2)*(a*b + c*|a-b|). Para achar os pontos criticos de F, temos que derivar e igualar a zero: F'(t) = -a*b*t/raiz(1 - t^2) - a*b*c/raiz(a^2 + b^2 - 2*a*b*t) F'(t) = 0 == t/raiz(1 - t^2) = - c/raiz(a^2 + b^2 - 2*a*b*t) == t^2/(1 - t^2) = c^2/(a^2 + b^2 - 2*a*b*t) e t 0 == t = raiz negativa de 2*a*b*t^3 - (a^2 + b^2 + c^2)*t^2 + c^2 = 0 E ai, meu caro, vai depender dos valores de a, b, c... (incluir receita de torta de chocolate nesse ponto) Dai ia concluir a//c e chegava na area que escrevi no comeco. Como nao sei nada escrevo essa ideia maluca porque pode ou dar um estalo em quem entende do assunto ou pelo menos fazer rir Epa! Essa eh a minha area. Nao sei se essa lista tem espaco para dois palhacos... []s, Claudio. = 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] Problemas em Aberto
2. Três lados consecutivos de um quadrilátero convexo são a, b e c. Determine o quadrilátero de área máxima . Bom a area de um quadrilatero ciclico (que pode ser inscrito num circulo) é a maior possivel para qualquer quadrilatero com lados dados. E a area deste quadrilatero ciciclo pode ser dada como sqrt((s-a)(s-b)(s-c)(s-d)) onde s é o semiperimetro, talvez derivando e pesquisando pontos de maximo e minimo saia a resposta.. -- Niski - http://www.linux.ime.usp.br/~niski [upon losing the use of his right eye] Now I will have less distraction Leonhard Euler = 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] Problemas em Aberto
on 31.05.04 16:25, niski at [EMAIL PROTECTED] wrote: 2. Três lados consecutivos de um quadrilátero convexo são a, b e c. Determine o quadrilátero de área máxima . Bom a area de um quadrilatero ciclico (que pode ser inscrito num circulo) é a maior possivel para qualquer quadrilatero com lados dados. E demonstrar isso eh um bom exercicio de trigonometria. Soh que o quarto lado nao eh dado. Serah que, mesmo assim, o quadrilatero de maior area eh o inscritivel? E a area deste quadrilatero ciciclo pode ser dada como sqrt((s-a)(s-b)(s-c)(s-d)) onde s é o semiperimetro, talvez derivando e pesquisando pontos de maximo e minimo saia a resposta.. Se concluirmos que o quadrilatero de area maxima eh o inscritivel, nao ha duvidas. Soh que voce vai cair numa equacao de 3o. grau em d. Eu me pergunto se nao ha uma solucao mais elementar. []s, Claudio. = 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] Problemas em Aberto
E ai Niski! Eu tentei fazer supondo que fosse mesmo inscritível e dpois usar bramagupta, como vc sugeriu, mais nao encontrei um dos angulos ai, vc tem uma dica pra mim? Seja ABCD tal quadrilátero e a, b, c e d os lados AB, BC. CD e DA respectivamente. É facil ver que med(ABC) = me(CDA) pois enxergam uma mesma corda de uma certa circunferência. I) T. cos. tring. ABC: AC=sqrt(a^2+b^2-2abcosx); onde med(ABC)=x II) T. cos. triang. CDA: AC=sqrt(c^2+d^2-2cdcosx) De I e II podemos tirar d em função de a, b e c e x: c^2+d^2-2cdcosx=a^2+b^2-2abcosx=d^2+(-2c cosx)d+(c^2- a^2-b^2+2abcosx) Daí d=c.cos(x)+sqrt(c^2.(cosx)^2-c^2+a^2+b^2-2abcosx) Preciso achar x. Tentei pelo T. dos senos, mais nao saiu. Tentei usar o T. la que fala que o produto das diagonais é a soma dos produtos dos lados opostos, tudo em vão. Alguem sabe como acho esse bendito angulo? falow ! on 31.05.04 16:25, niski at [EMAIL PROTECTED] wrote: 2. Três lados consecutivos de um quadrilátero convexo são a, b e c. Determine o quadrilátero de área máxima . Bom a area de um quadrilatero ciclico (que pode ser inscrito num circulo) é a maior possivel para qualquer quadrilatero com lados dados. E demonstrar isso eh um bom exercicio de trigonometria. Soh que o quarto lado nao eh dado. Serah que, mesmo assim, o quadrilatero de maior area eh o inscritivel? E a area deste quadrilatero ciciclo pode ser dada como sqrt((s-a)(s-b)(s-c)(s-d)) onde s é o semiperimetro, talvez derivando e pesquisando pontos de maximo e minimo saia a resposta.. Se concluirmos que o quadrilatero de area maxima eh o inscritivel, nao ha duvidas. Soh que voce vai cair numa equacao de 3o. grau em d. Eu me pergunto se nao ha uma solucao mais elementar. []s, Claudio. = 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 = Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.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 =
Re: [obm-l] Problemas em Aberto - Algarismos
Nao seria 3*10^(k+1) + 6*10^k? -Auggy - Original Message - From: Johann Peter Gustav Lejeune Dirichlet [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Tuesday, August 05, 2003 12:42 PM Subject: Re: [obm-l] Problemas em Aberto - Algarismos Retorno do Abertos da lista? Que tal a gente achar quadrados perfeitos do tipo 3*10^k+6*10^l? O tres nao pode vir no final.Talvez modulo...Depois eu penso... --- Claudio Buffara [EMAIL PROTECTED] escreveu: Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. ___ Conheça o novo Cadê? - Mais rápido, mais fácil e mais preciso. Toda a web, 42 milhões de páginas brasileiras e nova busca por imagens! http://www.cade.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 = = 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 =
[obm-l] Re: [obm-l] Problemas em Aberto - Algarismos
Esse segundo problema caiu na OBM 2000, numa versão mais fácil. Acho que foi essa versão a que vc resolveu, jah que ele dizia que as duas potências têm que ter o mesmo número de algarismos, de modo que os zeros não modificavam a quantidade de algarismos. Ateh mais, Yuri -- Mensagem original -- Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. []'s, Yuri ICQ: 64992515 -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.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 =
Re: [obm-l] Problemas em Aberto - Algarismos
Vou mais longe: Os candidatos são os quadrados da forma: (3*10^m + A)*10^(2n) onde A pertence a {1,4,6} e m e n são inteiros não negativos. Até agora, só encontrei números do tipo: 36, 3600, 36, ..., 36*10^(2n), ... mas não consegui provar que são os únicos. Um abraço, Claudio. - Original Message - From: Johann Peter Gustav Lejeune Dirichlet [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Tuesday, August 05, 2003 1:42 PM Subject: Re: [obm-l] Problemas em Aberto - Algarismos Retorno do Abertos da lista? Que tal a gente achar quadrados perfeitos do tipo 3*10^k+6*10^l? O tres nao pode vir no final.Talvez modulo...Depois eu penso... --- Claudio Buffara [EMAIL PROTECTED] escreveu: Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. ___ Conheça o novo Cadê? - Mais rápido, mais fácil e mais preciso. Toda a web, 42 milhões de páginas brasileiras e nova busca por imagens! http://www.cade.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 = = 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] Problemas em Aberto - Algarismos
Title: Re: [obm-l] Problemas em Aberto - Algarismos on 05.08.03 19:03, Domingos Jr. at [EMAIL PROTECTED] wrote: Uma idéia para o segundo: Considere, SPG, j i, tq: 2^j = a0 + a1*10 + ... + a[k]*10^k e f uma permutação tq. 2^i = f(a0) + f(a1)*10 + ... + f(a[k])*10^k então 2^j - 2^i = a0 - f(a0) + [a1 - f(a1)]*10 + ... + [a[k] - f(a[k])]*10^k logo 2^j - 2^i ~ a0 - f(a0) + ... + a[k] - f(a[k]) = 0 (mod 9) 2^i[2^(j-i) - 1] = 0 (mod 9) = j - i = 6k para algum k será que sai alguma coisa a partir daqui? o que fiz até aqui já mostra que a permutação tem que colocar pelo menos 1 zero a esquerda... Pois eh. O problema eh justamente se: 2^(i+6k) = a b c d 0 0 0 e f g e 2^i = f g a b d c ou algo do genero. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio.
Re: [obm-l] Problemas em Aberto - Algarismos
Nenhum nº qudrado perfeito termina em 3, logo o 3 deverá ser sempre o 1ºalg. da esq. p/ a dir.;já o seis é mais complicado. os nº serão da forma: 30000600...00=3*10^(f+2q+1)+6*10^(2q) onde onde f é o nºde zeros entre o 3 e o 6 e 2q é o nºde zeros depois do 6, f e q sendo inteiros não-negativos. Agora vamos mostrar que f só poderá ser 0(admitindo q=0): 3*10^(f+1)+6=30*10^(f)+6=k^2 ; k inteiro positivo k^2=6*(5*10^(f)+1) :. 6*a=k*k ; k=a=6 ou (a=6c e 6c=q^2) {a,c,q}C(Z*+), c=1 :. 5*10^(n)+1=6*c :. c=(5*10^(f)+1)/6 6*c deverá ser múltiplo de 6, logo deverá ser múltiplo de 2 e de 3 ao mesmo tempo, assim a soma dos alg. de c deve ser múltiplo de 3(o que é fácil de observar que sempre ocorre) e c deverá ser par. temos duas hipóteses, 1- n0 ou 2- n=0 1-se f0 então 6*c=50...001, isto é 6*c nunca será par. 2-se f=0 então c=6, que é par CONCLUSÃO: 6*c=6 Se c=1 então a=6=k, logo 3*10^(f+1)+6=36 = f=0 Logo o conjunto pedido será o dos números da forma: 36000...0; com nº par de zeros, ou: 3,6*10^(2q+1) Em 5 Aug 2003, [EMAIL PROTECTED] escreveu: Vou mais longe: Os candidatos são os quadrados da forma: (3*10^m + A)*10^(2n) onde A pertence a {1,4,6} e m e n são inteiros não negativos. Até agora, só encontrei números do tipo: 36, 3600, 36, ..., 36*10^(2n), ... mas não consegui provar que são os únicos. Um abraço, Claudio. - Original Message - From: Johann Peter Gustav Lejeune Dirichlet To: Sent: Tuesday, August 05, 2003 1:42 PM Subject: Re: [obm-l] Problemas em Aberto - Algarismos Retorno do Abertos da lista? Que tal a gente achar quadrados perfeitos do tipo 3*10^k+6*10^l? O tres nao pode vir no final.Talvez modulo...Depois eu penso... --- Claudio Buffara escreveu: Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. ___ Conheça o novo Cadê? - Mais rápido, mais fácil e mais preciso. Toda a web, 42 milhões de páginas brasileiras e nova busca por imagens! http://www.cade.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 = = 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 = -- _ Voce quer um iGMail protegido contra vírus e spams? Clique aqui: http://www.igmailseguro.ig.com.br Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/ Ofertas imperdíveis! = 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] Re: [obm-l] Problemas em Aberto - Algarismos
Exatamente. O enunciado da Olimpiada Iraniana de 1999 está aqui: http://www.geocities.com/CollegePark/Lounge/5284/math/99.html e não fala nada sobre zeros ou número de algarismos. Ainda estou tentando... Um abraço, Claudio. - Original Message - From: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Tuesday, August 05, 2003 12:45 PM Subject: [obm-l] Re: [obm-l] Problemas em Aberto - Algarismos Esse segundo problema caiu na OBM 2000, numa versão mais fácil. Acho que foi essa versão a que vc resolveu, jah que ele dizia que as duas potências têm que ter o mesmo número de algarismos, de modo que os zeros não modificavam a quantidade de algarismos. Ateh mais, Yuri -- Mensagem original -- Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. []'s, Yuri ICQ: 64992515 -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.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 = = 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] Problemas em aberto 1
Agora vou contar só as regiões limitadas. Para isso, vou começar contando as ilimitadas. Vamos imaginar que já desenhamos n retas. Agora vamos desenhar um círculo bem grande, de modo que todas as interseções de retas estejam dentro do círculo. Todas as regiões ilimitadas intersectam o círculo. E só as regiões ilimitadas intersectam o círculo. Então, para contá-las, basta contar quantas regiões intersectam o círculo. Vamos desenhar um ponto vermelho no círculo, sem ele estar sobre nenhuma reta. Agora vamos passarum filme do ponto andando pelo cículo, até dar uma volta. Ele começa em alguma região. Daí, quando bate em uma reta, pula para outra região. E assim continua, até que ele bate em uma reta pela última vez e volta para a primeira região. Então o número de regiões é o número de vezes que ele bate nas retas. Como ele bate duas vezes em cada reta, são 2n regiões ilimitadas. Como já tinhamos contado o número total de regiões R(n), o número máximo de regiões limitadas é R(n) menos as 2n regiões limitadas. Vamos chamar esse cara de L(n): L(n) = R(n) - 2n = n(n+1)/2 + 1 - 2n = n(n-3)/2 + 1 Agora vamos desenhar alguns casos para testar a fórmula: L(0)=0 L(1)=0 L(2)=0 L(3)=1 L(4)=3 Êpa!!! A fórmula deu errado pra n=0! Bem, isso era de se esperar, já que o argumento acima é totalmente furado quando não tem nenhuma reta. Mas ela deu certo para todos os outros valores, então parece que vale para n0. Agora aos números. L(58)=1596 e L(59)=1653. Mas esse é o número máximo de regiões que pode ser atingido. Se algumas retas forem paralelas, o número de regiões é menor. Mas será que dá pra consegui 1597 com 59 retas? Dá! Se duas forem paralelas, o número de regiões diminui por um. Se três forem paralelas, o número de regiões diminui por 3. Então basta desenhar 59 retas, sendo 54 paralelastrês atrês e 4 paralelas duas a duas. - Original Message - From: Eduardo Azevedo To: [EMAIL PROTECTED] Sent: Wednesday, August 06, 2003 7:49 PM Subject: Re: [obm-l] Problemas em aberto 1 Esse é clássico. Estou surpreso que ninguém respondeu até agora. Só não entendi o que é :(A area externa aos vertices das extremidades nao entra na contagem). Imagino que seja pra contar só as regiões limitadas? Bom, vou fazer contando todas (que o 1597 indica ser a interpretação correta do problema), que, depois que você explicar melhor, deve dar pra ajustar as contas. Vou chamar de R(n) o número máximo de regiões em que o plano plano pode ser dividido por n retas. Isso contando as regiões "de fora", aquelas que são ilimitadas. Claramente R(0)=1 R(1)=2 R(2)=4 (faço um X com as retas) R(3)=7 (desenho a 3a não paralela as 2 primeiras) Agora vou tentar achar uma relação entre R(n) e R(n-1). Para isso vamos imaginar um filme da 3a reta sendo desenhada. Antes dela encostar nas outras duas só há R(2)=4 regiões. Quando ela bate na 1a reta surge mais uma. Quando bate na segunda surge outra. Quando ela chega no infinito (no final do filme) aparece mais outra. Hummm. Parece que R(n) é R(n), mais (n -1) regiões que aparecem quandoa reta novabate nas (n - 1) outras retas(é só desenha-la paralela as anteriores), mais 1 quando ela bate no infinito. Ou seja, R(n)= n+R(n-1) = n+ (n-1) +R(n-2) = = n + (n-1) + (n-2) + ... + 1 + R(0) = n(n+1)/2 + 1 Felizmente isso bate com os valores que a gente calculou antes. Ufa! Agora, você pediu o menor n tal que R(n)= n(n+1)/2 + 1 é pelo menos 1597. Resolvendo a eq. do 2o grau, R(56)=1597, na mosca!
Re: [obm-l] Problemas em Aberto - Algarismos
Cláudio obrigado pelas correções, e aqui vai a solução, gostaria procurasse erros nela, ou tentasse simplificá-la. Não há quadrado perfeito que termine em 3, logo o 3 deverá ser o 1º alg. da esq. p/ dir. Sendo assim os números do tal conjunto deverão ser da forma 300...0n00...0 ou W=3*10^(p+2q+1)+n*10^(2q) ; Sendo todas as incógnitas inteiras não-negativas, onde n só poderá assumir os valores de: 1, 4, 5, 6, 9 Provemos agora que p só pode ser zero. W=300...0n*10^(2q)=K*K, K inteiro :. 300...0n=q*q, q inteiro, logo: q*q=3*10^(p+1)+n=30*10^(p)+n :. q*q-n=(q+n^0,5)(q-n^0,5)=[3*10^(t)]*[10^(s)], t,s reais q+n^0,5=3*10^t q+n^0,5=10^s q=3*10^t+n^0,5 temos dois casos: t=s :. e outs :. e ; ou q-n^0,5=10^sq-n^0,5=3*10^t q=10^s+n^0,5 a-)q*q=9*10^(2t)+6*n^(0,5)*10^(t)+n ou b-)q*q=10^(2s)+2*n^(0,5)*10^(s)+n a-)10^(2t)=10^(a)/3, a inteiro positivo, pois 9*10^(2t)=3*10^(a)=300...0 Desse jeito q*q=3*10^(a)+6*((n*10^(a))/3)^(0,5)+n=3*10^(a)+2(n*3*10^(a))+n q*q só será inteiro se n*3*10^(a) o for também. Mas nehum dos valores possíveis de n faz essa condição ser obedecida. Daí, hipótese a é falsa. b-)10^(2s)=3*10^(a), a inteiro positivo, pois 10^(2s)=3*10^(a)=300...0 Desse jeito q*q=3*10^(a)+2*(n*3*10^(a))+n, ora recaímos no caso anterior, logo a hipótese b também é falsa Disso concluímos que no número W=300...0n00...0, entre 3 e n não deve haver zeros, com isso W=3n00...0=3n*10^(2q)=K*K :. 3n=q*q :. n=6 Logo a resposta será: 3600...0, onde o nº de zeros é par, ou 3,6*10^(2q+1); q=0 e q inteiro --- Claudio Buffara escreveu: Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. ___ Conheça o novo Cadê? - Mais rápido, mais fácil e mais preciso. Toda a web, 42 milhões de páginas brasileiras e nova busca por imagens! http://www.cade.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 = = 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 = -- _ Voce quer um iGMail protegido contra vírus e spams? Clique aqui: http://www.igmailseguro.ig.com.br Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/ Ofertas imperdíveis! = 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 = = 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 = -- _ Voce quer um iGMail protegido contra vírus e spams? Clique aqui: http://www.igmailseguro.ig.com.br Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/ Ofertas imperdíveis! = 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 =
[obm-l] Re: [obm-l] Problemas em Aberto - Algarismos
Essa primeira questão pode conte repetições, como por exemplo 33600??? -- Mensagem original -- Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. []'s, Yuri ICQ: 64992515 -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.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 =
Re: [obm-l] Problemas em Aberto - Algarismos
Title: Problemas em Aberto - Algarismos Uma idéia para o segundo: Considere, SPG,j i, tq: 2^j = a0 + a1*10+ ... + a[k]*10^k e f uma permutação tq. 2^i = f(a0) + f(a1)*10 + ... + f(a[k])*10^k então 2^j - 2^i = a0 - f(a0) + [a1 - f(a1)]*10 + ... + [a[k] - f(a[k])]*10^k logo 2^j - 2^i ~ a0 - f(a0) + ... + a[k] - f(a[k]) = 0(mod 9) 2^i[2^(j-i) - 1] = 0 (mod 9) = j - i = 6k para algum k será que sai alguma coisa a partir daqui? o que fiz até aqui já mostra que a permutação tem que colocar pelo menos 1 zero a esquerda... 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2.Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos "0" internos (ou seja, numeros do tipo "abcdefg"). Um abraco,Claudio.
Re: [obm-l] Problemas em Aberto - Algarismos
Oi, e_lema (qual o seu nome?): Meus comentários estão ao longo da sua mensagem. Um abraço, Claudio. - Original Message - From: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Wednesday, August 06, 2003 8:21 PM Subject: Re: [obm-l] Problemas em Aberto - Algarismos Cláudio obrigado pelas correções, e aqui vai a solução, gostaria procurasse erros nela, ou tentasse simplificá-la. Não há quadrado perfeito que termine em 3, logo o 3 deverá ser o 1º alg. da esq. p/ dir. Sendo assim os números do tal conjunto deverão ser da forma 300...0n00...0 ou W=3*10^(p+2q+1)+n*10^(2q) ; Sendo todas as incógnitas inteiras não-negativas, onde n só poderá assumir os valores de: 1, 4, 5, 6, 9 Até aqui, estou 100% de acordo. De fato, numa mensagem anterior você provou que o único quadrado com n = 6 é o 36. Além disso, usando congruência mod 9, também eliminamos o 5 e o 9, da seguinte forma: Os quadrados (mod 9) são: 0, 1, 4 e 7. Como W é quadrado e W == 3+n (mod 9), teremos que: 3+n == 0, 1, 4 ou 7 (mod 9) == n == 6, 7, 1 ou 4 (mod 9) == (dado que n pertence a {1,4,5,6,9}) n só pode ser 1, 4 ou 6 == (em virtude da sua análise do caso n = 6) n só pode ser 1 ou 4. Resumindo, o problema é provar que não existem quadrados da forma: 3*10^p + 1 e 3*10^p + 4. Provemos agora que p só pode ser zero. W=300...0n*10^(2q)=K*K, K inteiro :. 300...0n=q*q, q inteiro, logo: q*q=3*10^(p+1)+n=30*10^(p)+n :. Você deveria ter escolhido outra letra que não q, pois esta já estava sendo usada pra representar o número de zeros à direita (em 10^(2q)), mas tudo bem... O problema começa a partir daqui, onde você introduz expoentes possivelmente irracionais (o que é um pouco inusitado para este problema, mas pode até dar certo no final) e a formatação/tabulação está bem difícil de entenderSe você puder dar uma limpada no argumento e na formatação eu agradeceria. q*q-n=(q+n^0,5)(q-n^0,5)=[3*10^(t)]*[10^(s)], t,s reais q+n^0,5=3*10^t q+n^0,5=10^s q=3*10^t+n^0,5 temos dois casos: t=s :. e outs :. e ; ou q-n^0,5=10^sq-n^0,5=3*10^t q=10^s+n^0,5 a-)q*q=9*10^(2t)+6*n^(0,5)*10^(t)+n ou b-)q*q=10^(2s)+2*n^(0,5)*10^(s)+n a-)10^(2t)=10^(a)/3, a inteiro positivo, pois 9*10^(2t)=3*10^(a)=300...0 Desse jeito q*q=3*10^(a)+6*((n*10^(a))/3)^(0,5)+n=3*10^(a)+2(n*3*10^(a))+n q*q só será inteiro se n*3*10^(a) o for também. Mas nehum dos valores possíveis de n faz essa condição ser obedecida. Daí, hipótese a é falsa. b-)10^(2s)=3*10^(a), a inteiro positivo, pois 10^(2s)=3*10^(a)=300...0 Desse jeito q*q=3*10^(a)+2*(n*3*10^(a))+n, ora recaímos no caso anterior, logo a hipótese b também é falsa Disso concluímos que no número W=300...0n00...0, entre 3 e n não deve haver zeros, com isso W=3n00...0=3n*10^(2q)=K*K :. 3n=q*q :. n=6 Logo a resposta será: 3600...0, onde o nº de zeros é par, ou 3,6*10^(2q+1); q=0 e q inteiro = 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] Problemas em Aberto - Algarismos
on 05.08.03 18:45, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote: Nenhum nº qudrado perfeito termina em 3, logo o 3 deverá ser sempre o 1ºalg. da esq. p/ a dir.;já o seis é mais complicado. os nº serão da forma: 30000600...00=3*10^(f+2q+1)+6*10^(2q) onde onde f é o nºde zeros entre o 3 e o 6 e 2q é o nºde zeros depois do 6, f e q sendo inteiros não-negativos. Agora vamos mostrar que f só poderá ser 0(admitindo q=0): 3*10^(f+1)+6=30*10^(f)+6=k^2 ; k inteiro positivo k^2=6*(5*10^(f)+1) A partir daqui, bastava considerar que: 6 divide k^2 == 6 divide k == 6^2 divide k^2 == 6 divide 5*10^f + 1, que eh impar se f =1 == contradicao. Mas tudo bem, a sua demonstracao estah perfeita. :. 6*a=k*k ; k=a=6 ou (a=6c e 6c=q^2) {a,c,q}C(Z*+), c=1 :. 5*10^(n)+1=6*c :. c=(5*10^(f)+1)/6 6*c deverá ser múltiplo de 6, logo deverá ser múltiplo de 2 e de 3 ao mesmo tempo, assim a soma dos alg. de c deve ser múltiplo de 3(o que é fácil de observar que sempre ocorre) e c deverá ser par. temos duas hipóteses, 1- n0 ou 2- n=0 1-se f0 então 6*c=50...001, isto é 6*c nunca será par. 2-se f=0 então c=6, que é par CONCLUSÃO: 6*c=6 Se c=1 então a=6=k, logo 3*10^(f+1)+6=36 = f=0 Logo o conjunto pedido será o dos números da forma: 36000...0; com nº par de zeros, ou: 3,6*10^(2q+1) OK. Voce provou que a menos dos 2q zeros a direita, o unico quadrado com 1o. algarismo 3 e ultimo 6 eh o 36. Ainda restam os casos: 3*10^(f+1) + 1 e 3*10^(f+1) + 4 mas certamente o fim estah mais proximo! Um abraco, Claudio. Em 5 Aug 2003, [EMAIL PROTECTED] escreveu: Vou mais longe: Os candidatos são os quadrados da forma: (3*10^m + A)*10^(2n) onde A pertence a {1,4,6} e m e n são inteiros não negativos. Até agora, só encontrei números do tipo: 36, 3600, 36, ..., 36*10^(2n), ... mas não consegui provar que são os únicos. Um abraço, Claudio. - Original Message - From: Johann Peter Gustav Lejeune Dirichlet To: Sent: Tuesday, August 05, 2003 1:42 PM Subject: Re: [obm-l] Problemas em Aberto - Algarismos Retorno do Abertos da lista? Que tal a gente achar quadrados perfeitos do tipo 3*10^k+6*10^l? O tres nao pode vir no final.Talvez modulo...Depois eu penso... --- Claudio Buffara escreveu: Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. ___ Conheça o novo Cadê? - Mais rápido, mais fácil e mais preciso. Toda a web, 42 milhões de páginas brasileiras e nova busca por imagens! http://www.cade.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 = = 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 = -- _ Voce quer um iGMail protegido contra vírus e spams? Clique aqui: http://www.igmailseguro.ig.com.br Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/ Ofertas imperdíveis! = 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 = = 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] Problemas em Aberto - Algarismos
Retorno do Abertos da lista? Que tal a gente achar quadrados perfeitos do tipo 3*10^k+6*10^l? O tres nao pode vir no final.Talvez modulo...Depois eu penso... --- Claudio Buffara [EMAIL PROTECTED] escreveu: Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. ___ Conheça o novo Cadê? - Mais rápido, mais fácil e mais preciso. Toda a web, 42 milhões de páginas brasileiras e nova busca por imagens! http://www.cade.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 =
Re: [obm-l] Problemas em Aberto - Algarismos
Olá, Cláudio: O problema, é que ao copiar a solução do bloco de notas, e colá-la na mensagem, ela embaralhou toda, vê se assim fica melhor, as correções foram feitas diretamente na mensagem original: Em 7 Aug 2003, [EMAIL PROTECTED] escreveu: Oi, e_lema (qual o seu nome?): Meus comentários estão ao longo da sua mensagem. Um abraço, Claudio. - Original Message - From: To: Sent: Wednesday, August 06, 2003 8:21 PM Subject: Re: [obm-l] Problemas em Aberto - Algarismos Cláudio obrigado pelas correções, e aqui vai a solução, gostaria procurasse erros nela, ou tentasse simplificá-la. Não há quadrado perfeito que termine em 3, logo o 3 deverá ser o 1º alg. da esq. p/ dir. Sendo assim os números do tal conjunto deverão ser da forma 300...0n00...0 ou W=3*10^(p+2q+1)+n*10^(2q) ; Sendo todas as incógnitas inteiras não-negativas, onde n só poderá assumir os valores de: 1, 4, 5, 6, 9 Até aqui, estou 100% de acordo. De fato, numa mensagem anterior você provou que o único quadrado com n = 6 é o 36. Além disso, usando congruência mod 9, também eliminamos o 5 e o 9, da seguinte forma: Os quadrados (mod 9) são: 0, 1, 4 e 7. Como W é quadrado e W == 3+n (mod 9), teremos que: 3+n == 0, 1, 4 ou 7 (mod 9) == n == 6, 7, 1 ou 4 (mod 9) == (dado que n pertence a {1,4,5,6,9}) n só pode ser 1, 4 ou 6 == (em virtude da sua análise do caso n = 6) n só pode ser 1 ou 4. Resumindo, o problema é provar que não existem quadrados da forma: 3*10^p + 1 e 3*10^p + 4. Provemos agora que p só pode ser zero. W=300...0n*10^(2q)=K*K, K inteiro :. 300...0n=q*q, q inteiro, logo: q*q=3*10^(p+1)+n=30*10^(p)+n :. Você deveria ter escolhido outra letra que não q, pois esta já estava sendo usada pra representar o número de zeros à direita (em 10^(2q)), mas tudo bem... foi mal, nem vi. O problema começa a partir daqui, onde você introduz expoentes possivelmente irracionais (o que é um pouco inusitado para este problema, mas pode até dar certo no final) e a formatação/tabulação está bem difícil de entenderSe você puder dar uma limpada no argumento e na formatação eu agradeceria. q*q-n=(q+n^0,5)(q-n^0,5)=[3*10^(t)]*[10^(s)], t,s reais temos dois casos possíveis: t=sq+n^0,5=3*10^t e q-n^0,5=10^s sistema 1 ou ts q+n^0,5=10^s e q-n^0,5=3*10^t sistema 2 Logo, só temos 2 valores possíveis para q: t=s a-)q=3*10^t+n^0,5 ou ; ts b-)q=10^s+n^0,5 a-)q*q=9*10^(2t)+6*n^(0,5)*10^(t)+n b-)q*q=10^(2s)+2*n^(0,5)*10^(s)+n a-)10^(2t)=10^(a)/3, a inteiro positivo, pois 9*10^(2t)=3*10^(a)=300...0 Desse jeito q*q=3*10^(a)+6*((n*10^(a))/3)^(0,5)+n=3*10^(a)+2(n*3*10^(a))+n q*q só será inteiro se n*3*10^(a) o for também. Mas nehum dos valores possíveis de n faz essa condição ser obedecida. Daí, hipótese a é falsa. b-)10^(2s)=3*10^(a), a inteiro positivo, pois 10^(2s)=3*10^(a)=300...0 Desse jeito q*q=3*10^(a)+2*(n*3*10^(a))+n, ora recaímos no caso anterior, logo a hipótese b também é falsa Disso concluímos que no número W=300...0n00...0, entre 3 e n não deve haver zeros, com isso W=3n00...0=3n*10^(2q)=K*K :. 3n=q*q :. n=6 Logo a resposta será: 3600...0, onde o nº de zeros é par, ou 3,6*10^(2q+1); q=0 e q inteiro Caso não tenha entendido, volte aos sistemas 1 e 2, e resolvá-os admitindo f=1 ou f=4, só que isso dá uma solução um pouco grande... Um abraço, Eduardo = 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 = -- _ Voce quer um iGMail protegido contra vírus e spams? Clique aqui: http://www.igmailseguro.ig.com.br Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/ Ofertas imperdíveis! = 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] Re: [obm-l] Problemas em Aberto - Algarismos
Isto e mais interpretaçao.Eu acho que nao aceita pelo seguinte motivo:fala-se em EXATAMENTE DOIS algarismos.E os tres sao diferentes pelo sistema posicional. --- [EMAIL PROTECTED] escreveu: Essa primeira questão pode conte repetições, como por exemplo 33600??? -- Mensagem original -- Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. []'s, Yuri ICQ: 64992515 -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.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 = ___ Conheça o novo Cadê? - Mais rápido, mais fácil e mais preciso. Toda a web, 42 milhões de páginas brasileiras e nova busca por imagens! http://www.cade.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 =
Re: [obm-l] Problemas em aberto 1
Esse é clássico. Estou surpreso que ninguém respondeu até agora. Só não entendi o que é :(A area externa aos vertices das extremidades nao entra na contagem). Imagino que seja pra contar só as regiões limitadas? Bom, vou fazer contando todas (que o 1597 indica ser a interpretação correta do problema), que, depois que você explicar melhor, deve dar pra ajustar as contas. Vou chamar de R(n) o número máximo de regiões em que o plano plano pode ser dividido por n retas. Isso contando as regiões "de fora", aquelas que são ilimitadas. Claramente R(0)=1 R(1)=2 R(2)=4 (faço um X com as retas) R(3)=7 (desenho a 3a não paralela as 2 primeiras) Agora vou tentar achar uma relação entre R(n) e R(n-1). Para isso vamos imaginar um filme da 3a reta sendo desenhada. Antes dela encostar nas outras duas só há R(2)=4 regiões. Quando ela bate na 1a reta surge mais uma. Quando bate na segunda surge outra. Quando ela chega no infinito (no final do filme) aparece mais outra. Hummm. Parece que R(n) é R(n), mais (n -1) regiões que aparecem quandoa reta novabate nas (n - 1) outras retas, mais 1 quando ela bate no infinito. Ou seja, R(n)= n+R(n-1) = n+ (n-1) +R(n-2) = = n + (n-1) + (n-2) + ... + 1 + R(0) = n(n+1)/2 + 1 Felizmente isso bate com os valores que a gente calculou antes. Ufa! Agora, você pediu o menor n tal que R(n)= n(n+1)/2 + 1 é pelo menos 1597. Resolvendo a eq. do 2o grau, R(56)=1597, na mosca!
Re: [obm-l] Problemas em aberto 1
Caro colega, a area externa (ilimitada) nao entra na contagem conforme o enunciado diz. Ha uma coisa importante a ressaltar:Se o enunciado se referisse a plano ao invez de superficie plana, a regiao ilimitada contaria!Isso quer dizer que sua soluçaoinfelizmente estaincorreta... O problema fica mais dificil e interessante quando nao se conta a regiao ilimitada MSN Hotmail, o maior webmail do Brasil. Faça o seu agora. = 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] =?Re: [obm-l] Problemas em Aberto - Algarismos?=
Não. O enunciado afirma que os números possuem somente dois algs. não-nulos. Em 5 Aug 2003, [EMAIL PROTECTED] escreveu: Essa primeira questão pode conte repetições, como por exemplo 33600??? -- Mensagem original -- Caros colegas: Aqui vao dois problemas que ainda estao em aberto na lista. O primeiro foi enviado pelo Duda Stabel. O segundo eh da olimpiada iraniana, se nao me engano. 1) Determinar o conjunto de números inteiros positivos que satisfazem à duas condições: (i) todo número possui exatamente dois algarismos não-nulos, sendo um deles o três(3), (ii) todo número é quadrado perfeito. 2) Prove ou disprove: existe uma potencia de 2 tal que ao se permutar os algarismos de sua representacao decimal obtem-se uma outra potencia de 2. Esse segundo tem uma solucao aparentemente simples, mas esta solucao exclui o caso de potencias de 2 com algarismos 0 internos (ou seja, numeros do tipo abcdefg). Um abraco, Claudio. []'s, Yuri ICQ: 64992515 -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.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 = -- _ Voce quer um iGMail protegido contra vírus e spams? Clique aqui: http://www.igmailseguro.ig.com.br Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/ Ofertas imperdíveis! = 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] Problemas em Aberto III
Sauda,c~oes, Oi Cláudio, Acho que no livro (dos anos 60/70?) Flow Network de Ford and Fulkerson vc encontra a demonstração deste teorema. []'s Luís -Mensagem Original- De: Nicolau C. Saldanha [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Enviada em: sexta-feira, 7 de março de 2003 16:03 Assunto: Re: [obm-l] Problemas em Aberto III On Fri, Mar 07, 2003 at 12:05:14PM -0300, Cláudio (Prática) wrote: Seja G um grafo direcionado e sejam x e y vértices distintos de G. Um fluxo de tamanho n de x para y é uma família de n caminhos indo de x para y que são disjuntos por arestas (ou seja, eles podem ter vértices em comum mas não arestas). Um corte de tamanho m é um conjunto de m arestas direcionadas tais que, se removidas, tornam impossível ir de x até y. Maxflow-mincut é o seguinte teorema: o tamanho (n) máximo possível (N) para um fluxo é igual ao tamanho (m) mínimo possível (M) para um corte. Será que esta demonstração está correta? = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em Aberto III
- Original Message - From: Nicolau C. Saldanha [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, March 07, 2003 9:15 AM Subject: Re: [obm-l] Problemas em Aberto III On Thu, Mar 06, 2003 at 04:28:24PM -0300, Cláudio (Prática) wrote: Caro Nicolau: No no. 24, eu empaquei exatamente na hora de provar que existem 3 caminhos disjuntos de X até Y. Como eu não conheço teoria dos grafos, maxflow-mincut (seja lá o que isso for) é novidade pra mim. Seja G um grafo direcionado e sejam x e y vértices distintos de G. Um fluxo de tamanho n de x para y é uma família de n caminhos indo de x para y que são disjuntos por arestas (ou seja, eles podem ter vértices em comum mas não arestas). Um corte de tamanho m é um conjunto de m arestas direcionadas tais que, se removidas, tornam impossível ir de x até y. Maxflow-mincut é o seguinte teorema: o tamanho (n) máximo possível (N) para um fluxo é igual ao tamanho (m) mínimo possível (M) para um corte. Observe que M = N é trivial. Caro Nicolau: Será que esta demonstração está correta? Suponhamos que M N. Isso significa que qualquer corte tem mais do que N arestas. Tome um (possivelmente o único) fluxo de tamanho N, o qual liga os vértices X e Y e remova uma aresta de cada um dos N caminhos deste fluxo. Após a remoção das arestas será impossível ir de X a Y, pois cada caminho possível terá sido interrompido. Logo, as N arestas removidas constituem um corte == contradição, pois qualquer corte tem mais do que N arestas == M = N. Assim, concluimos que M = N. Um abraço, Claudio. = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em Aberto III
On Thu, Mar 06, 2003 at 04:28:24PM -0300, Cláudio (Prática) wrote: Caro Nicolau: No no. 24, eu empaquei exatamente na hora de provar que existem 3 caminhos disjuntos de X até Y. Como eu não conheço teoria dos grafos, maxflow-mincut (seja lá o que isso for) é novidade pra mim. Seja G um grafo direcionado e sejam x e y vértices distintos de G. Um fluxo de tamanho n de x para y é uma família de n caminhos indo de x para y que são disjuntos por arestas (ou seja, eles podem ter vértices em comum mas não arestas). Um corte de tamanho m é um conjunto de m arestas direcionadas tais que, se removidas, tornam impossível ir de x até y. Maxflow-mincut é o seguinte teorema: o tamanho (n) máximo possível (N) para um fluxo é igual ao tamanho (m) mínimo possível (M) para um corte. Observe que M = N é trivial. []s, N. = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em Aberto III
On Fri, Mar 07, 2003 at 12:05:14PM -0300, Cláudio (Prática) wrote: Seja G um grafo direcionado e sejam x e y vértices distintos de G. Um fluxo de tamanho n de x para y é uma família de n caminhos indo de x para y que são disjuntos por arestas (ou seja, eles podem ter vértices em comum mas não arestas). Um corte de tamanho m é um conjunto de m arestas direcionadas tais que, se removidas, tornam impossível ir de x até y. Maxflow-mincut é o seguinte teorema: o tamanho (n) máximo possível (N) para um fluxo é igual ao tamanho (m) mínimo possível (M) para um corte. Será que esta demonstração está correta? Suponhamos que M N. Isso significa que qualquer corte tem mais do que N arestas. Tome um (possivelmente o único) fluxo de tamanho N, o qual liga os vértices X e Y e remova uma aresta de cada um dos N caminhos deste fluxo. Após a remoção das arestas será impossível ir de X a Y, pois cada caminho possível terá sido interrompido. Logo, as N arestas removidas constituem um corte == contradição, pois qualquer corte tem mais do que N arestas == M = N. Assim, concluimos que M = N. Infelizmente não é tão simples. Retirar N arestas quaisquer, uma por caminho, não necessariamente desconecta o grafo (mesmo se N for máximo). Exemplo: x .---.---.---.---.---.---. | | | | | | | .---.---.---.---.---.---. y Neste exemplo claramente M=N=2 mas se tomarmos os dois caminhos como sendo o bordo superior e o bordo inferior e retirarmos duas arestas para obter x .---.---. .---.---.---. | | | | | | | .---.---.---. .---.---. y isso não desconectou o grafo. É claro que *teríamos* desconectado se tivéssemos escolhido ao invés x .---.---. .---.---.---. | | | | | | | .---.---. .---.---.---. y e é preciso provar que sempre existe uma escolha de N arestas que de fato desconecta (se N for máximo, claro). []s, N. = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em aberto IV
Sauda,c~oes, Mandei hoje já há muito tempo uma longa msg a este respeito. Enquanto não chega, mando um pedaço dela: tan(3 Pi/11) + 4 sin(2 Pi/11) = sqrt(11) (1) Solution: The identity below is true for all s. (\tan(3s) + 4\sin(2s))^2 = 11 - \frac{(\tan(8s) + \tan(3s))\cos(8s)}{\sin(s)\cos(3s)} (2) Substituting s = Pi/11 into (2) we prove (1) since it is obvious that \tan(8s) + \tan(3s) = 0 for s = Pi/11, and \tan(3*Pi/11) + 4*\sin(2*Pi/11) 0 Não me perguntem como o prof. Markelov chegou a (2). E também não tenho a prova de (2). Claro que o Luís Lopes e o Morgado podem achar que uma solução geométrica seria mais elegante... É verdade. Como fazer? []'s Luís -Mensagem Original- De: Nicolau C. Saldanha [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Enviada em: quinta-feira, 6 de março de 2003 12:06 Assunto: Re: [obm-l] Problemas em aberto IV On Sun, Mar 02, 2003 at 11:12:21AM -0300, A. C. Morgado wrote: O Luís Lopes mandou ha algum tempo: Prove que tan(3*Pi/11) + 4*sin(2*Pi/11) = sqrt(11). Embora eu tenha uma ideia muito clara do que fazer (usar trigonometria do tempo dos gregos, isto eh, construir um conveniente quadrilatero inscrito e aplicar o teorema de Ptolomeu), quando tentei nao consegui. Eu fiz algo bem diferente; usei álgebra e maple: pp := ((z^3 - z^(-3)) + 2*(z^2 - z^(-2\ ))*(z^3 + z^(-3)))^2 + 11*(z^3 + z^(-3))^2; / 31 / 21 \ / 31 \\2 / 31 \2 pp := |z - + 2 |z - | |z + || + 11 |z + | | 3 | 2 | | 3 || | 3 | \ z \ z / \ z // \ z / p1 := expand(pp); 24448 64104 4 p1 := 4 + 4 z + + 4 z + + 4 z + 4 z + + 4 z + + --- 2 46 8 10 z zz z z p2 := expand(z^10 * p1); 10 12 8 14 6 18 16 4 20 p2 := 4 z + 4 z + 4 z + 4 z + 4 z + 4 z + 4 z + 4 z + 4 z 2 + 4 z + 4 factor(p2); 5647398210 4 (z + z + z + z + z + z + z + z + z + z + 1) 1098765432 (z - z + z - z + z - z + z - z + z - z + 1) A idéia é que z = exp(Pi*i/11). Temos tan(3*Pi/11) = -i (z^3 - z^(-3))/(z^3 + z^(-3)), sin(2*Pi/11) = -i/2 * (z^2 - z^(-2)) donde após pequenas simplificações queremos verificar que pp acima vale 0. Expandimos, fatoramos e descobrimos que pp é múltiplo de z^10 - z^9 + z^8 - ... - z + 1. Ora, este polinômio de fator tem exp(Pi*i/11) por raiz. Observe que as contas não são tão pesadas assim, daria para fazer na mão. Claro que o Luís Lopes e o Morgado podem achar que uma solução geométrica seria mais elegante... []s, N. = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em aberto IV
Esse problema e legal pacas!!Mandei uma soluçao pra Eureka totalmente porrada.Elevei ao quadrado e fui simplificando ate virar(depois de uma folha) uma sominha meiga de cossenos. "Nicolau C. Saldanha" [EMAIL PROTECTED] wrote: On Sun, Mar 02, 2003 at 11:12:21AM -0300, A. C. Morgado wrote: O Luís Lopes mandou ha algum tempo: Prove que tan(3*Pi/11) + 4*sin(2*Pi/11) = sqrt(11). Embora eu tenha uma ideia muito clara do que fazer (usar trigonometria do tempo dos gregos, isto eh, construir um conveniente quadrilatero inscrito e aplicar o teorema de Ptolomeu), quando tentei nao consegui. Eu fiz algo bem diferente; usei álgebra e maple: pp := ((z^3 - z^(-3)) + 2*(z^2 - z^(-2\ ))*(z^3 + z^(-3)))^2 + 11*(z^3 + z^(-3))^2;/ 3 1 / 2 1 \ / 3 1 \\2 / 3 1 \2pp := |z - + 2 |z - | |z + || + 11 |z + || 3 | 2 | | 3 || | 3 |\ z \ z / \ z // \ z / p1 := expand(ppp);2 4 4 4 8 6 4 10 4 4p1 := 4 + 4 z + + 4 z + + 4 z + 4 z + + 4 z + + ---2 4 6 8 10z z z z z p2 := expand(z^10 * p1);10 12 8 14 6 18 16 4 20p2 := 4 z + 4 z + 4 z + 4 z + 4 z + 4 z + 4 z + 4 z + 4 z2+ 4 z + 4 factor(p2);5 6 4 7 3 9 8 2 104 (z + z + z + z + z + z + z + z + z + z + 1)10 9 8 7 6 5 4 3 2(z - z + z - z + z - z + z - z + z - z + 1)A idéia é que z = exp(Pi*i/11).Temos tan(3*Pi/11) = -i (z^3 - z^(-3))/(z^3 + z^(-3)),sin(2*Pi/11) = -i/2 * (z^2 - z^(-2)) donde após pequenassimplificações queremos verificar que pp acima vale 0.Expandimos, fatoramos e descobrimos que pp é múltiplo dez^10 - z^9 + z^8 - ... - z + 1. Ora, este polinômio de fatortem exp(Pi*i/11) por raiz.Observe que as contas não são tão pesadas assim,daria para fazer na mão.Claro que o Luís Lopes e o Morgado podem achar que uma soluçãogeométrica seria mais elegante...[]s, N.=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.htmlO administrador desta lista é <[EMAIL PROTECTED]>=Busca Yahoo! O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra.
Re: [obm-l] Problemas em aberto IV
Sauda,c~oes, Oi Morgado, Este problema começou com um email do prof. Sergei Markelov, de Moscou. Seu email a respeito segue (a notação em LaTeX é minha): Here is my solution to this problem. tan(3 Pi/11) + 4 sin(2 Pi/11) = sqrt(11) (1) Solution: The identity below is true for all s. (\tan(3s) + 4\sin(2s))^2 = 11 - \frac{(\tan(8s) + \tan(3s))\cos(8s)}{\sin(s)\cos(3s)} (2) Substituting s = Pi/11 into (2) we prove (1) since it is obvious that \tan(8s) + \tan(3s) = 0 for s = Pi/11, and \tan(3*Pi/11) + 4*\sin(2*Pi/11) 0 By the way, it is not nessasary to use square in prooving formulae. The following is also true for all s: tan(3s) + 4 sin(2s) = sqrt(11) - sin(7 s) + sin(5 s) + sin (3 s) (cot(6 s) + cot(5 s)) --- 2sin(5s) + sin(3s) - 2sin(s) + sqrt(11) cos(3s) It is clear that cot(6 s) + cot(5 s) = 0 for s = Pi/11 Another simular identity: A tan(3s) + 4 sin(2s) - sqrt(11) = (tan(8 s) + tan(3 s)) --- B where A = 2 cos(8 s) B = 2 cos(6 s) - cos(4 s) - 3 cos(2 s) - sqrt(11) sin(4 s) + sqrt(11) sin(2 s) + 2 Also, substituting alpha = 2 Pi/11, 3 Pi/11, 4 Pi/11 and 5 Pi/11 we get 4 additional simular identities for free for total 5: tan(3 Pi/11) + 4 sin(2 Pi/11) = sqrt(11) tan(5 Pi/11) - 4 sin(4 Pi/11) = sqrt(11) tan(2 Pi/11) - 4 sin(5 Pi/11) = -sqrt(11) tan(Pi/11) + 4 sin(3 Pi/11) = sqrt(11) tan(4 Pi/11) + 4 sin(Pi/11) = sqrt(11) Não contente com isso, escrevi em seguida pro prof. Rousseau. Ele me mandou um fonte em LaTeX (com uma outra solução BEM complicada) muito comprido que não vale a pena colocar aqui. Coloco somente o final dele: {\em Note.} This problem was given on a 1895 Tripos Exam, and it is in the book by Bromwich on infinite series (p. 270). O email que o Rousseau me mandou com o fonte em anexo segue: Dear Luis: I found this solution in the book by Bromwich before I left for San Diego, and tried to send you a sketch of it, but there was a computer problem. corte This is a nice problem since it brings into play some unexpected bits of mathematics (in particular, quadratic residues). As you can see, it has been around for a long time. Cheers, Cecil Coincidentemente, o prof. Markelov me mandou durante o carnaval outro email. Aí vai: Dear Luis, I have found several new trig formulas, maybe they will be of your interest. Here are 3: 5 7 10 13 14 1 cos(-- Pi) cos(-- Pi) cos(-- Pi) cos(-- Pi) cos(-- Pi) = -- 33 33 33 33 33 32 Pi 248 16 cos(--) - cos(-- Pi) - cos(-- Pi) - cos(-- Pi) - cos(-- Pi) = 3333 33 33 33 - sqrt(33) - 1 = -- 4 57 10 13 14 cos(-- Pi) + cos(-- Pi) - cos(-- Pi) + cos(-- Pi) - cos(-- Pi) = 33 33 33 33 33 sqrt(33) - 1 = 4 Sergei Markelov technical director Moscow Center for Continuous Mathematical Education www.mccme.ru [EMAIL PROTECTED] +7-095-2410500phone +7-095-2916501fax Ainda nem tive tempo de escrever-lhe para agradecer e confirmar como as identidades devem ser escritas em LaTeX. Deixo para a imaginação de vcs. A 2a. acho que deve ser o seguinte: \cos(\pi/33) - \cos(2\pi/33) - \cos(4\pi/33) - \cos(8\pi/33) - \cos(16\pi/33) = \frac{-\sqrt{33} - 1}{4}. []'s Luís -Mensagem Original- De: A. C. Morgado [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Enviada em: domingo, 2 de março de 2003 11:12 Assunto: [obm-l] Problemas em aberto IV O Luís Lopes mandou ha algum tempo: Prove que tan(3*Pi/11) + 4*sin(2*Pi/11) = sqrt(11). Embora eu tenha uma ideia muito clara do que fazer (usar trigonometria do tempo dos gregos, isto eh, construir um conveniente quadrilatero inscrito e aplicar o teorema de Ptolomeu), quando tentei nao consegui. Eh verdade que nao pude dedicar a esse problema o tempo que ele parece exigir. Morgado = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em Aberto III
Caro Nicolau: No no. 24, eu empaquei exatamente na hora de provar que existem 3 caminhos disjuntos de X até Y. Como eu não conheço teoria dos grafos, maxflow-mincut (seja lá o que isso for) é novidade pra mim. Você poderia recomendar alguma bibliografia a respeito (especialmente na internet)? Obrigado e um abraço, Claudio. - Original Message - From: Nicolau C. Saldanha [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, March 02, 2003 10:04 AM Subject: Re: [obm-l] Problemas em Aberto III On Thu, Feb 27, 2003 at 03:04:48PM -0300, Cláudio (Prática) wrote: 24) Prove que a soma dos comprimentos dos lados de um poliedro convexo qualquer é maior que 3 vezes a maior distancia entre dois vertices do poliedro. Sejam x e y vértices a distância máxima. Queremos construir três caminhos formados por arestas indo de x até y, e estes caminhos devem ser disjuntos (exceto por x, y e possivelmente algum vértice no meio). Ora, por maxflow-mincut estes três caminhos só *não* existem se existir um corte feito por duas arestas, ou seja, se existirem duas arestas que, se removidas, desconectam o grafo formado por vértices e arestas. Mas isso estaria em contradição com o fato de termos um poliedro convexo. 25) Um alienígena move-se na superfície de um planeta com velocidade não superior a U. Uma espaçonave que procura pelo alienígena move-se com velocidade V. Prove que a espaçonave sempre poderá encontrar o alinígena se V 10U. Não entendi nada. Quando é que a nave encontra o alienígena? []s, N. = 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 é [EMAIL PROTECTED] = = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em Aberto III
Caro Paulo: Neste problema: Seja S o conjunto de todas as sequencia FINITAS de INTEIROS POSITIVOS tais que se {Xn}=X1, X2, ...,Xn pertence a S entao para todo P N, X1+X2+...+Xp NAO E congruo a 1 modulo 3. Mostre que existe uma bijecao entre S e o conjunto de todos os impares positivos. eu fiz o seguinte raciocínio: Seja N = conjunto dos inteiros positivos. Então: 1. Existe uma bijeção entre quaisquer dois conjuntos enumeráveis; 2. O conjunto dos ímpares positivos é enumerável; 3. Pelas definições básicas de função (conjunto de pares ordenados com primeiras coordenadas distintas duas a duas) e sequência (função cujo domínio é N) cada sequência de S consiste de um conjunto de pares ordenados { (1,X1), (2,X2), ..., (n,Xn) , ... } onde cada Xi é um inteiro positivo e onde existe um inteiro positivo n, tal que Xk = 0 para k n. Assim, cada sequência de S é um subconjunto de N x (N U {0}), o qual é enumerável. Logo, cada sequência de S é um conjunto enumerável. 3. S é enumerável, por ser uma reunião enumerável de conjuntos enumeráveis. Logo, existe uma bijeção entre S e o conjunto de todos os ímpares positivos. Uma outra alternativa é fazer a correspondência: (X1, ..., Xn) == 0,X1X2...Xn (ou seja, cada sequencia corresponde a um número obtido justapondo-se os Xi's e tratando-os como decimais) Como cada sequencia é finita, as decimais serão finitas e os números obtidos serão todos racionais. Assim, teremos obtido uma bijeção entre S e um subconjunto dos racionais. Logo, S será enumerável. Tá certo o que eu fiz? O estranho é que em nenhum momento eu usei a propriedade aritmética das sequências. Um abraço, Claudio. = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em aberto IV
On Sun, Mar 02, 2003 at 11:12:21AM -0300, A. C. Morgado wrote: O Luís Lopes mandou ha algum tempo: Prove que tan(3*Pi/11) + 4*sin(2*Pi/11) = sqrt(11). Embora eu tenha uma ideia muito clara do que fazer (usar trigonometria do tempo dos gregos, isto eh, construir um conveniente quadrilatero inscrito e aplicar o teorema de Ptolomeu), quando tentei nao consegui. Eu fiz algo bem diferente; usei álgebra e maple: pp := ((z^3 - z^(-3)) + 2*(z^2 - z^(-2\ ))*(z^3 + z^(-3)))^2 + 11*(z^3 + z^(-3))^2; / 31 / 21 \ / 31 \\2 / 31 \2 pp := |z - + 2 |z - | |z + || + 11 |z + | | 3 | 2 | | 3 || | 3 | \ z \ z / \ z // \ z / p1 := expand(pp); 24448 64104 4 p1 := 4 + 4 z + + 4 z + + 4 z + 4 z + + 4 z + + --- 2 46 8 10 z zz z z p2 := expand(z^10 * p1); 10 12 8 14 6 18 16 4 20 p2 := 4 z + 4 z + 4 z + 4 z + 4 z + 4 z + 4 z + 4 z + 4 z 2 + 4 z + 4 factor(p2); 5647398210 4 (z + z + z + z + z + z + z + z + z + z + 1) 1098765432 (z - z + z - z + z - z + z - z + z - z + 1) A idéia é que z = exp(Pi*i/11). Temos tan(3*Pi/11) = -i (z^3 - z^(-3))/(z^3 + z^(-3)), sin(2*Pi/11) = -i/2 * (z^2 - z^(-2)) donde após pequenas simplificações queremos verificar que pp acima vale 0. Expandimos, fatoramos e descobrimos que pp é múltiplo de z^10 - z^9 + z^8 - ... - z + 1. Ora, este polinômio de fator tem exp(Pi*i/11) por raiz. Observe que as contas não são tão pesadas assim, daria para fazer na mão. Claro que o Luís Lopes e o Morgado podem achar que uma solução geométrica seria mais elegante... []s, N. = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em Aberto III
Ola Prof Nicolau e demais colegas desta lista ... OBM-L, Representando por (um ponto) N a nave, traçamos todas as tangentes à esfera que passam por N. Isso define uma calota na esfera. Se o alienígena estiver nesta calota entao entende-se que a Nave o encontrou. A solução deve prescindir da distancia da Nave à superficie do planeta e de eventuais variações nos sentidos e modulos das velocidades envolvidas. A ideia - do Claudio/Pratica/ - de publicar os problemas que foram propostos nesta lista e que permanecem em aberto me parece muito boa Um famoso problema pode se reformulado da seguinte maneira : Seja S o conjunto de todas as sequencia FINITAS de INTEIROS POSITIVOS tais que se {Xn}=X1, X2, ...,Xn pertence a S entao para todo P N, X1+X2+...+Xp NAO E congruo a 1 modulo 3. Mostre que existe uma bijecao entre S e o conjunto de todos os impares positivos. Um Abraço Paulo Santa Rita 3,1900,040303 From: Nicolau C. Saldanha [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] Problemas em Aberto III Date: Sun, 2 Mar 2003 10:04:30 -0300 25) Um alienígena move-se na superfície de um planeta com velocidade não superior a U. Uma espaçonave que procura pelo alienígena move-se com velocidade V. Prove que a espaçonave sempre poderá encontrar o alinígena se V 10U. Não entendi nada. Quando é que a nave encontra o alienígena? []s, N. _ MSN Messenger: converse com os seus amigos online. 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em Aberto III
Oi pessoal ! Parece que falta alguma coisa no enunciado do problema 25, do modo como o problema é apresentado V 10U não garante que a nave vá encontrar o alienígena. Por exemplo, o alienígena e a nave podem ficar andando em trajetórias circulares que não se cruzam. André T. - Original Message - From: Nicolau C. Saldanha [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, March 02, 2003 10:04 AM Subject: Re: [obm-l] Problemas em Aberto III On Thu, Feb 27, 2003 at 03:04:48PM -0300, Cláudio (Prática) wrote: 24) Prove que a soma dos comprimentos dos lados de um poliedro convexo qualquer é maior que 3 vezes a maior distancia entre dois vertices do poliedro. Sejam x e y vértices a distância máxima. Queremos construir três caminhos formados por arestas indo de x até y, e estes caminhos devem ser disjuntos (exceto por x, y e possivelmente algum vértice no meio). Ora, por maxflow-mincut estes três caminhos só *não* existem se existir um corte feito por duas arestas, ou seja, se existirem duas arestas que, se removidas, desconectam o grafo formado por vértices e arestas. Mas isso estaria em contradição com o fato de termos um poliedro convexo. 25) Um alienígena move-se na superfície de um planeta com velocidade não superior a U. Uma espaçonave que procura pelo alienígena move-se com velocidade V. Prove que a espaçonave sempre poderá encontrar o alinígena se V 10U. Não entendi nada. Quando é que a nave encontra o alienígena? []s, N. = 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 é [EMAIL PROTECTED] = = 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 é [EMAIL PROTECTED] =
Re: [obm-l] Problemas em Aberto III
On Thu, Feb 27, 2003 at 03:04:48PM -0300, Cláudio (Prática) wrote: 24) Prove que a soma dos comprimentos dos lados de um poliedro convexo qualquer é maior que 3 vezes a maior distancia entre dois vertices do poliedro. Sejam x e y vértices a distância máxima. Queremos construir três caminhos formados por arestas indo de x até y, e estes caminhos devem ser disjuntos (exceto por x, y e possivelmente algum vértice no meio). Ora, por maxflow-mincut estes três caminhos só *não* existem se existir um corte feito por duas arestas, ou seja, se existirem duas arestas que, se removidas, desconectam o grafo formado por vértices e arestas. Mas isso estaria em contradição com o fato de termos um poliedro convexo. 25) Um alienígena move-se na superfície de um planeta com velocidade não superior a U. Uma espaçonave que procura pelo alienígena move-se com velocidade V. Prove que a espaçonave sempre poderá encontrar o alinígena se V 10U. Não entendi nada. Quando é que a nave encontra o alienígena? []s, N. = 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 é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] Problemas em Aberto
Tu de novo Claudio!!!Esse ultimo e da IMO da Coreia e a soluçao do Fabricio(que fez a prova alias)e muito legal.Tente uma induçao e pense primeiro que asw caixas sao iguais depois faça vezes tres. Vou supor que esta coisa de tres angulos e dita em graus. Talvez saia com SLC:a^2=b^2+c^2-2bc*cos A. A tarefa e achar os t tais que cos t e racional se t e expresso em graus. Talvez saia usando complexos.Me lembro de uma prova de que arccos 3/5 e irracional se dito em graus que usava uns fatos do artigo do Ed na Eureka 6.As Eurekas ce ve na Internet. -- Mensagem original -- HelpCaros colegas da lista: Muitas vezes um problema é proposto na lista, nenhuma solução é dada nos dias seguintes e logo o problema cai no esquecimento. Assim, resolvi fazer uma compilação (temo que incompleta) daqueles problemas da lista que ficaram sem solução. 1. Seja A = | A1 | | A2 | uma matriz m x n com A1 n x n não singular e A2 uma matriz (m-n) x n arbitrária A+ é a pseudo-inversa de A, definida como A+ = (A' * A)^(-1) * A' prove que ||A+|| = ||(A1)^(-1)|| OBS: A norma aqui é induzida: ||A|| = sup ||Ax|| ||x|| = 1 * 2. É possível que um polinômio de coeficientes inteiros P(X) irredutível se fatore em Z/(n) para todo n natural ? * 3. A e B são cantos opostos de um tabuleiro n x n, dividido em n^2 quadradinhos por linhas paralelas a seus lados. Em cada quadradinho é traçada sua diagonal paralela a AB, tal que o tabuleiro fica dividido em 2n^2 triângulinhos. O tabuleiro tem (n + 1)^2 pontos que são vértices dos quadrinhos e um qrande número de segmentos, cada qual medindo 1 ou sqrt2. Uma peça move-se de A até B através dos segmentos. Ela nunca passa duas vezes pelo mesmo segmento e seu caminho inclui exatamente dois lados de cada triângulinho. Para qual n isto é possível? * 4. A) As medidas dos ângulos agudos de um triângulo pitagórico (triângulo retângulo cujos lados têm medida inteira) não são inteiras (quando expressos em graus). B) Se os lados de um triângulo têm medida inteira e um de seus ângulos tem medida inteira, então esse ângulo mede 60, 90 ou 120 graus. C) Se um triângulo tem os três lados e os três ângulos com medida inteira então ele é equilátero. * 5. Nos festejos juninos, 20 casais de dançarinos são colocados em círculo de tal maneira que um homem e uma mulher formando um par estão situados diametralmente opostos. Durante a dança, dois dançarinos adjacentes trocam de lugar enquanto todos os outros permanecem na mesma posição. Essa mudança é repetida com pares adjacentes até que, na posição final, os dois dançarinos de cada par estejam novamente diametralmente opostos, mas na posição contrária da inicial. Então o número mínimo de mudanças, de dois dançarinos adjacentes, para acontecer isso é: (a) 20! (b) 400 (c) 10! (d) 19! (e) 20 * 6. Dê um exemplo de uma sequência (Xn) de números reais tal que: lim ( Xn / n^t ) = 0 para todo t 0 e lim ( [log(n)]^k / Xn ) = 0 para todo k 0 * 7. Um triângulo tem lados com medida inteira e área racional. Prove que uma de suas alturas tem medida inteira e que o pé desta altura está a uma distância inteira dos vértices do triângulo. * 8. Um polígono convexo possui 2n lados. Prove que o polígono contém no mínimo n diagonais que não são paralelas a qualquer de seus lados. * 9. Seja K um inteiro = 2. infinito Seja S = SOMATÓRIO 1 / K^(n^2) = 1/K + 1/K^4 + 1/K^9 + 1/K^16 + ... n = 1 Prove que S é irracional. * 10. Um mágico tem cem cartões numerados de 1 a 100. Coloca-os em três caixas, uma vermelha, uma branca e uma azul, de modo que cada caixa contém pelo menos um cartão. Uma pessoa da platéia escolhe duas das três caixas, seleciona um cartão de cada caixa e anuncia a soma dos números dos dois cartões que escolheu. Ao saber esta soma, o mágico identifica a caixa da qual não se retirou nenhum cartão. Descreva todas as maneiras de se colocar todos os cartões nas caixas de modo de que este truque sempre funcione? (Duas maneiras consideram-se diferentes se pelo menos um cartão é colocado numa caixa diferente). Uma formulação equivalente deste problema é: Determine todas as partições do conjunto: {1, 2, ..., 100} em três subconjuntos V, B e A, de forma que: V+B, V+A e B+A sejam disjuntos (V+B = {x + y tais que x pertence a V e y pertence a B}, idem para os outros dois conjuntos-soma ) Por enquanto só foram encontradas duas soluções: V = {1, 4, 7, ..., 100} = {3k + 1} B = {2, 5, 8, ..., 98} = {3k + 2} A = {3, 6, 9, ..., 99} = {3k} (além das outras 5 permutações de V, B e A} e V = {1} B = {100} A = {2, 3, ..., 99} (também já se provou que esta é a única partição - a menos de permutações dos conjuntos - que tem dois conjuntos unitários) TEA WITH ME THAT I BOOK YOUR FACE -- Use o melhor sistema de busca da Internet Radar UOL -
[obm-l] Re: [obm-l] Problemas em Aberto II
Esse da via ferrea e classico!!Voce pode usar recursao para provar que isto e o n-esimo numero de Catalan. Para tal escolha um trem x e conte de quantos modos voce arruma os trens antes e depois sem violar as regras.Definida a recursao resolva-a.Esse esta num livro do Knuth. Tomei a liberdade de corrigi-lo. -- Mensagem original -- HelpContinuando a compilação de problemas não resolvidos da lista: 11. Dado um corredor com 1 metro de largura, que faz uma curva de 90 graus e continua com a mesma largura, qual a figura plana de maior área possível que pode fazer essa curva? Observe que o formato dessa area pode ser qualquer e, obviamente, ela é suposta rigida. (Acho que este problema ainda está em aberto - e não só aqui na lista. De qualquer forma) ** 12. Dada a sequencia a[n+1]= 2a[1]*a[n] - a[n-1] definida para todo n=1 tal que a[0]=100 e a[100]= 0. a) Mostre que | a[1] |=1. b) Determine a[2003]. ** 13. X, Y e Z são reais positivos e satisfazem o sistema abaixo, X^2 + XY + (Y^2)/3 = 25 (Y^2)/3 + Z^2 = 9 Z^2 + ZX + X^2 = 16 Encontre o valor de ( XY + 2YZ + 3ZX ). SUGESTÃO : Você nao precisa, necessariamente, resolver o sistema ... ** 14. De quantas formas podemos colocar N rainhas em um tabuleiro NxN tal que nenhuma rainha possa enxergar outra? obs: uma rainha enxerga outra se ambas estiverem na mesma coluna, linha ou diagonal. (Este problema também está em aberto. Talvez valha a pena tentar com Torres e Bispos ao invés de Rainhas) *** 15. _ _ _ _ _ _ _ 1 2 ... n _ _|_| |_|_| |_|_|_|_|_|_|_ B \_\ /_/ A \_|_/ |_| |_| |_| C |o| Imagine que o 'desenho' acima é uma linha férrea, aonde o segmento B é extensão do segmento A e o segmento C se conecta com ambos segmentos. Os numeros no segmento A representam n vagões _soltos_ e enumerados. Os vagoes podem se mover de A - B, A - C e C - B, mas nunca de C - A nem B - A nem B - C.. De quantas formas eh possivel reagrupar os vagões no segmento B? (há espaço suficiente para n vagões tanto em A, quanto em B e em C) 16. Seja f uma função contínua em [a,b] e diferenciável em (a,b). A) É possível que, apesar de existir, f' seja descontínua em todo ponto de (a,b). B) Em caso afirmativo, será que a condição f(a) f(b) é suficiente para garantir que exista um sub-intervalo [c,d] (a = c d = b) onde f é crescente? ** 17. a, b, c, d são números reais não-negativos tais que: ab+ac+ad+bc+bd+cd+abc+abd+acd+bcd=2. Mostre que: 3(a+b+c+d)=4(ab+ac+ad+bc+bd+cd). * 18. Numa loteria sao sorteados 7 numeros escolhidos aleatoriamente de {1,2,3,...,48,49}. Cada cartao de apostas deve ser preenchido com exatamente 7 numeros. Uma pessoa pode pode apostar quantos cartoes desejar sem pagar nada, desde que quaisquer dois cartoes de sua aposta tenham, NO MAXIMO, uma dezena em comum. O primeiro premio e dado a pessoa que acertar o maior numero de triplos. A) Exiba uma aposta gratuita que tenha a maxima probabibilidade de ganhar o primeiro premio. B) Qual o valor da probabilidade acima ? *** 19. Suponha que os números da forma 2^x * 3^y (x, y: inteiros não negativos) são colocados em ordem crescente. Prove que existem termos consecutivos - digamos 2^a * 3^b e 2^c * 3^d - tais que |2^a * 3^b - 2^c * 3^d| torna-se arbitrariamente grande.Generalize * 20. Duas de Análise Real: A) Prove que se f:{a, b) - R é contínua em c em (a,b) e lim x- c f'(x) = L, então f'(c) = L. A partir daí, conclua que derivadas jamais apresentam descontinuidades do tipo salto. Conclua também que se f' é monotônica em um intervalo I, então f'é contínua em I. B) Suponhamos que f seja diferenciável em R e seja k0. Mostre que: B.1) se k0, então lim x - infinito f'(x) + k f(x) = L, L em R, implica que lim x- infinito f('x) = 0 e lim x- infinito f(x) = L/k B.2) se k0, então lim x- infinito f'(x) + k f(x) = L, L em R, só é possível se lim x- e^(kx) f(x) = 0, caso em que temos também lim x- infinito f('x) = 0 e lim x- infinito f(x) = L/k sugestão : defina h(x) = e^(kx) f(x) g(x) = e^(kx) . Logo, f(x) = h(x)/g(x). Use L'Hopital. ** TEA WITH ME THAT I BOOK YOUR FACE -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.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 é [EMAIL PROTECTED] =