[obm-l] Por 7!!!(???)
Colegas, nesta lista já foi mostrada uma justificativa para o critério de divisibilidade por 7, como está descrito abaixo? Gostaria de uma ajudinha. i) Um número natural n de 3 ou menos algarismos é divisível por 7 se ocorrer o que segue: Dadon=abc ( a,b e c são os algarismos do número) se, 2*a+3*b+c é divisível por 7, então n é divisível por 7. ii) Um natural n com mais de 3 algarismos é divisível por 7 se, separado em classes de 3 algarismos a partir do último (inclusive), a diferença entre a soma das classes de ordem ímpar e de ordem par for um número divisível por 7, independente do sinal: Dado n=abcdefg Classe1: efg Classe2: bcd Classe3: a S(I)=efg+a ( soma das classes de ordem ímpar) S(P)=bcd (soma das classes de ordem par) Se S(I) S(P) for divisível por 7, então n é divisível por 7. Obrigado Farelo!!! _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = 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] soma de termos
Oi, Brunno. Eu estava respondendo ontem quando acabou a luz, e aí
acabei perdendo a linha. Acho que agora estará tudo certo:
Primeiro, como você falou, está errado no local da soma, mas é C(n+1,
1+1), pois esta é a soma do último.
Agora, vamos para a demonstração da lei das colunas (por indução,
apesar de o Cláudio ter falado mal dela!)
Teorema: SOMA {desde m=1até m=n} C(m, k) = C(n+1, k+1)
Caso Base: n=1 (podia ser n=0)
Temos duas possibilidades: k = 1 e k > 1
Se k = 1, esta igualdade é 1 = C(1, 1) = C(1+1, 1+1) = C(2, 2) = 1, OK!
Se k > 1, é 0 = C(1, k) = C(2, k+1) = 0 pois (k+1) > 2
Agora, só falta o passo de indução:
SOMA {desde m=1até m=(n+1)} C(m, k) = SOMA {desde m=1até m=n} C(m, k)
+ C(n+1, k), separando o último termo da soma,
= C(n+1, k+1) + C(n+1, k) pela hipótese de indução
= C( (n+1) + 1, k + 1), pela fórmula C(a, b+1) + C(a, b) = C(a+1, b+1)
(Demonstre ela: é só expandir!)
Eu acho que vale também para k negativo ou zero, mas isso eu deixo
para você pensar (ah, e também tem o velho problema de definir quanto
vale C(n, -32), mas isso é zero, eu acho) Para k=0, o teorema na
verdade é uma coisa bem "trivial"!
Abraços,
--
Bernardo Freitas Paulo da Costa
On Apr 4, 2005 5:01 PM, Brunno <[EMAIL PROTECTED]> wrote:
> Unico engano é nessa passagem
> Mas então temos SOMA 2*C(m, 2) + C(m,1) = 2*C(n+1, 3) + C(n, 2) (pelo
> C(n, 2)
> deveria ser C(n+1,2+1)
> muito obrigado pela forca
> se puder me ajuda com a demonstracao da soma de colunas
> Um abraco
> Do amigo brunno
>
>
> - Original Message -
> From: "Bernardo Freitas Paulo da Costa" <[EMAIL PROTECTED]>
> To:
> Sent: Monday, April 04, 2005 1:38 PM
> Subject: Re: [obm-l] soma de termos
>
> Isto tem uma resposta muito legal com números binomiais:
>
> Repare que m^2 = m(m-1) +m = 2*C(m, 2) + C(m, 1) (este C(a, b) é o
> número de combinações de a, escolhendo b, que é equivalente a
> a!
>
> b! (a-b)!
>
> Ora, o que você quer é somar tudo, de m=1 até n.
> Mas então temos SOMA 2*C(m, 2) + C(m,1) = 2*C(n+1, 3) + C(n, 2) (pelo
> teorema de soma de colunas! - Demonstre que SOMA C(m,k) = C(n+1, k+1)
> usando a propriedade de que C(a, b) + C(a, b+1) = C(a+1, b+1) ). Agora
> é só expandir.
>
> Abraços,
> --
> Bernardo Freitas Paulo da Costa
>
> On Apr 4, 2005 1:07 PM, Brunno <[EMAIL PROTECTED]> wrote:
> > Boa tarde pessoal da lista
> > dentro de uma exercício, cheguei a soma de
> > soma de = 1^2 + 2^2 + 3^2 ...n^2
> > e vi que tinha uma formula especifica
> > n^3/3 + n^2/2 +n/6
> > mas como se chega a esta formula???
> > Um abraco
>
> =
> 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
> =
>
=
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] dois dificeis de probabilidade
> Dê uma olhada em "Catalan number" na internet. Se não me engano, o Nicolau > uma vez deu um link para um artigo bem completo sobre o assunto. O link é o seguinte: http://www-math.mit.edu/~rstan/ec/ []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] soma de termos
Oi, Bernardo:
Eu falei mal da indução porque acho que ela produz demonstrações feias e sem-graça, apesar de em muitos casos, ser a única forma (conhecida) de se demonstrar algum resultado.
Mas não é o caso da lei das colunas:
C(k,k) + C(k+1,k) + C(k+2,k) + ... + C(n,k) = C(n+1,k+1).
Imagine que você quer formar subconjuntos de {1, 2, 3, ..., n, n+1} com k+1 elementos.
Obviamente isso pode ser feito de C(n+1,k+1) maneiras diferentes.
Mas quantos destes subconjuntos tem o inteiro positivo p
(k+1 <= p <= n+1) como maior elemento?
Bem, uma vez escolhido p, e dado que p é o maior elemento, os demais k elementos só podem ser escolhidos dentre {1, 2, ..., p-1} e de C(p-1,k) maneiras distintas.
Somando de p = k+1 até p = n+1, obtemos o número desejado:
C(k,k) + C(k+1,k) + ... + C(n,k)
Com todo o respeito à sua demonstração, acho esta mais elegante. Além disso, ela dá uma interpretação "concreta" para a lei das colunas.
***
Um exercício que acho interessante é tentar dar uma demonstração do tipo acima para cada propriedade do triângulo de Pascal.
[]s,
Claudio.
De:
[EMAIL PROTECTED]
Para:
obm-l@mat.puc-rio.br
Cópia:
Data:
Wed, 6 Apr 2005 08:21:31 -0300
Assunto:
Re: [obm-l] soma de termos
> Oi, Brunno. Eu estava respondendo ontem quando acabou a luz, e aí
> acabei perdendo a linha. Acho que agora estará tudo certo:
>
> Primeiro, como você falou, está errado no local da soma, mas é C(n+1,
> 1+1), pois esta é a soma do último.
>
> Agora, vamos para a demonstração da lei das colunas (por indução,
> apesar de o Cláudio ter falado mal dela!)
> Teorema: SOMA {desde m=1até m=n} C(m, k) = C(n+1, k+1)
> Caso Base: n=1 (podia ser n=0)
> Temos duas possibilidades: k = 1 e k > 1
> Se k = 1, esta igualdade é 1 = C(1, 1) = C(1+1, 1+1) = C(2, 2) = 1, OK!
> Se k > 1, é 0 = C(1, k) = C(2, k+1) = 0 pois (k+1) > 2
>
> Agora, só falta o passo de indução:
> SOMA {desde m=1até m=(n+1)} C(m, k) = SOMA {desde m=1até m=n} C(m, k)
> + C(n+1, k), separando o último termo da soma,
> = C(n+1, k+1) + C(n+1, k) pela hipótese de indução
> = C( (n+1) + 1, k + 1), pela fórmula C(a, b+1) + C(a, b) = C(a+1, b+1)
> (Demonstre ela: é só expandir!)
>
> Eu acho que vale também para k negativo ou zero, mas isso eu deixo
> para você pensar (ah, e também tem o velho problema de definir quanto
> vale C(n, -32), mas isso é zero, eu acho) Para k=0, o teorema na
> verdade é uma coisa bem "trivial"!
>
> Abraços,
> --
> Bernardo Freitas Paulo da Costa
>
Re: [obm-l] Número Anagramas
A resposta aqui confere. 13080 mesmo! Muito Obrigado. Júnior. -- ___ Check out the latest SMS services @ http://www.linuxmail.org This allows you to send and receive SMS through your mailbox. Powered by Outblaze = 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] Logaritmo
Sabendo:log(y/2) na base 2 = X , ey = 4log(x/2) na base 2 - log(1/y^4) na base 2 Determine o(s) par(es) de x e y que sataisfaça as esquações Grato
Re: RES: [obm-l] 1^2 + 2^2 + ... + n^2
É verdade, viajei...
Vc esta certo.
ValeuGuilherme <[EMAIL PROTECTED]> wrote:
Olá, Bruno!Eu acho que nesta solução deve-se elevar ao cubo, pois da maneira quefoi colocada, os quadrados são simplificados.Um abração, Guilherme Marques.-Mensagem original-De: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Emnome de Bruno LimaEnviada em: terça-feira, 5 de abril de 2005 16:07Para: obm-l@mat.puc-rio.brAssunto: Re: [obm-l] 1^2 + 2^2 + ... + n^2Outra solucao que é bem manjada é 1^2 = (1+0)^2 = 1^2 +2*1*0+0^2(1+1)^2 = 1^2 +2*1*1+1^2... (1+n)^2 = 1^2 +2*1*n+n^2 Dai vc soma todas as equacoes e chega no resultado--- "claudio.buffara" <[EMAIL PROTECTED]>wrote:> Ontem alguém perguntou aqui na lista como se> demonstrava a fórmula da soma dos quadrados dos> primeiros n inteiros positivos.> > Eu
diria que 99% das pessoas usaria indução, o que> além de ser mecânico e sacal, não ilustra o que> realmente ocorre no problema e, o que é pior, se a> fórmula não for conhecida (ou seja, se o problema> for "deduza a fórmula da soma dos quadrados dos n> primeiros inteiros positivos") vai ser difícil> adivinhar qual é ela usando apenas indução.> Naturalmente, uma vez que você tenha "adivinhado"> uma fórmula, possivelmente olhando casos> particulares, você pode usar indução para confirmar> seu palpite.> > Eu sempre sou favorável a uma demonstração> combinatória, onde contamos o número de elementos de> algum conjunto de duas formas distintas.> > No caso, 1^2 + 2^2 + ... + n^2 é o número de> elementos de que conjunto?> > Por exemplo, considere todos os ternos ordenados> (a,b,c) de elementos do conjunto {1,2,...,n,n+1}> tais que a > !
b e a
> c.> > É claro (ou deveria ser pra quem participa dessa> lista) que se a = 1, o número de tais ternos é zero,> se a = 2, o número é 1*1 = 1, se a = 3, o número é> 2*2 = 4. Em geral, se a = k+1, então teremos k> possibilidades para b (b pode ser 1, 2, ... ou k) e> k para c, de modo que teremos k^2 ternos nas> condições do enunciado.> > Assim, fazendo a variar de 1 a n+1, obteremos o> número de ternos nas condições do enunciado: 0^2 +> 1^2 + 2^2 + ... + n^2, ou seja, justamente a soma> desejada.> > Agora, um terno nas condições do enunciado só pode> ser de três tipos:> (a,b,c) com a > b > c;> (a,b,c) com a > c > b;> (a,b,c) com a > b = c.> > O número de ternos de cada um dos dois primeiros> tipos é igual a:> Binom(n+1,3) (por que?)> > O número de ternos do terceiro tipo é Binom(n+1,2) !
>
(por que?).> > Logo, o número total de ternos nas condições do> enunciado é:> 2*Binom(n+1,3) + Binom(n+1,2) => 2*(n+1)*n*(n-1)/6 + (n+1)*n/2 => n*(n+1)*((n-1)/3 + 1/2) => n*(n+1)*(2n+1)/6.> > Ou seja, 1^2 + 2^2 + ... + n^2 = n*(n+1)*(2n+1)/6.> > []s,> Claudio.> Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador agora! http://br.acesso.yahoo.com/=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html==Instruções para entrar na lista, sair da lista e usar a lista
emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=__Converse com seus amigos em tempo real com o Yahoo! Messenger http://br.download.yahoo.com/messenger/
RE: [obm-l] Logaritmo
log(y/2) na base 2 = X , e y = 4log(x/2) na base 2 - log(1/y^4) na base 2 Determine o(s) par(es) de x e y que sataisfaça as esquações y=log(x^4/2^4)-log(1/y^4)=log(x^4*y^4)/2^4y=log(x^4)*(2^4x) 2^y=x^4*2^4x x=2^t y=4t+4x From: "Fernando" <[EMAIL PROTECTED]> Reply-To: obm-l@mat.puc-rio.br To: "obm-l" Subject: [obm-l] Logaritmo Date: Wed, 6 Apr 2005 09:30:26 -0300 Sabendo: log(y/2) na base 2 = X , e y = 4log(x/2) na base 2 - log(1/y^4) na base 2 Determine o(s) par(es) de x e y que sataisfaça as esquações Grato _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = 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] soma de termos
Sauda,c~oes,
Essas demonstrações combinatórias do Claudio são
realmente interessantes e elegantes.
Entretanto, as mais mecânicas e rápidas são (seriam)
aquelas usando antidiferenças.
Assim, seja a soma S_n(m) = \sum_{k=m}^n Binom(k,m) (m>=0).
Então Binom(k,m+1) é uma antidiferença de Binom(k,m) e
S_n(m)=Binom(n+1,m+1) - Binom(m,m+1) = Binom(n+1,m+1)
Fazendo m=k o resultado segue.
Um exercício que acho interessante é tentar dar uma demonstração do tipo
acima para cada propriedade do triângulo de Pascal.
Concordo. Mas isso (dar interpretações combinatórias) muitas vezes é
muito difícil. Como exemplo, considere a soma
S_N(n) := \sum_{k>=n} Binom(N,2k) Binom(k,n) (n,N inteiros, n>=0, N>=1, N
>=2n).
As soluções combinatórias aparecem em The Mathematical Gazette 79 (484,
486),
1995.
Eu iria por métodos mais gerais, se bem que nesse caso também não
é muito fácil. Com algumas manipulações chegamos a
S_N(n) = \sum_{k>=0} Binom(N,N-2n-2k) Binom(n+k,n).
Isso é uma soma hipergeométrica e usando as técnicas mostradas
no livro (resultado de Gauss) Matemática Concreta obtemos
S_N(n) = [N / (N-n)] Binom(N-n,n) 2^(N-2n-1).
[]'s
Luís
From: "claudio.buffara" <[EMAIL PROTECTED]>
Reply-To: obm-l@mat.puc-rio.br
To: "obm-l"
Subject: Re: [obm-l] soma de termos
Date: Wed, 6 Apr 2005 09:01:29 -0300
Oi, Bernardo:
Eu falei mal da indução porque acho que ela produz demonstrações feias e
sem-graça, apesar de em muitos casos, ser a única forma (conhecida) de se
demonstrar algum resultado.
Mas não é o caso da lei das colunas:
C(k,k) + C(k+1,k) + C(k+2,k) + ... + C(n,k) = C(n+1,k+1).
Imagine que você quer formar subconjuntos de {1, 2, 3, ..., n, n+1} com k+1
elementos.
Obviamente isso pode ser feito de C(n+1,k+1) maneiras diferentes.
Mas quantos destes subconjuntos tem o inteiro positivo p
(k+1 <= p <= n+1) como maior elemento?
Bem, uma vez escolhido p, e dado que p é o maior elemento, os demais k
elementos só podem ser escolhidos dentre {1, 2, ..., p-1} e de C(p-1,k)
maneiras distintas.
Somando de p = k+1 até p = n+1, obtemos o número desejado:
C(k,k) + C(k+1,k) + ... + C(n,k)
Com todo o respeito à sua demonstração, acho esta mais elegante. Além
disso, ela dá uma interpretação "concreta" para a lei das colunas.
***
Um exercício que acho interessante é tentar dar uma demonstração do tipo
acima para cada propriedade do triângulo de Pascal.
[]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] Logaritmo
> log(y/2) na base 2 = X , e > >y = 4log(x/2) na base 2 - log(1/y^4) na base 2 > >Determine o(s) par(es) de x e y que sataisfaça as esquações > > > y=log(x^4/2^4)-log(1/y^4)=log(x^4*y^4)/2^4y=log(x^4)*(2^4x) > 2^y=x^4*2^4x > x=2^t > y=4t+4x > Mas não é para qualquer valor de T :/, colocando -se t = 1, já não se é verificado a igualdade = 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] Ex. de fisica!
1)Um corpo está suspenso numa balança de mola num navio que viaja ao longo do equador com velocidade v. Mostre que a leitura da balança será muito proxima de Wo(1+- 2wv/g), onde w é a velocidade angular da Terra e Wo é a leitura da balança, quando o navio está em repouso. explique o sinal de +-. 2)O diametro angular aparente do sol visto da Terra(angulo subentendido pelo disco solar) é de 0,55º.Utilizando apenas esses dados, a cte gravitacional e o periodo da terra em torno do sol, calcule a densidade do sol. Abraços Vinícius Meireles Aleixo
[obm-l] [x^n] == n (mod 2)
Aqui vai um bonitinho: Ache um número real x tal que, para todo n inteiro e positivo, [x^n] tem a mesma paridade que n. [a] = maior inteiro que é menor ou igual a a. Se não me engano, há algum tempo, o Shine exibiu um y tal que [y^n] é sempre ímpar. []s, Claudio.
Re: [obm-l] soma de termos
Oi, Luís:
A impressão que eu tenho é que, depois do "Generatingfunctionology", todos estes problemas podem ser resolvidos pela aplicação de algum algoritmo geral.
Mesmo, assim, acho que é um bom treino tentar achar demonstrações combinatórias pra recorrências e identidades envolvendo números binomiais.
Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81.
SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1).
Agora, quero ver alguém provar isso algebricamente...
[]s,
Claudio.
De:
[EMAIL PROTECTED]
Para:
obm-l@mat.puc-rio.br
Cópia:
Data:
Wed, 06 Apr 2005 14:48:26 +
Assunto:
Re: [obm-l] soma de termos
> Sauda,c~oes,
>
>
> >Um exercício que acho interessante é tentar dar uma demonstração do tipo
> >acima para cada propriedade do triângulo de Pascal.
>
> Concordo. Mas isso (dar interpretações combinatórias) muitas vezes é
> muito difícil. Como exemplo, considere a soma
>
> S_N(n) := \sum_{k>=n} Binom(N,2k) Binom(k,n) (n,N inteiros, n>=0, N>=1, N
> >=2n).
>
> As soluções combinatórias aparecem em The Mathematical Gazette 79 (484,
> 486),
> 1995.
>
> Eu iria por métodos mais gerais, se bem que nesse caso também não
> é muito fácil. Com algumas manipulações chegamos a
>
> S_N(n) = \sum_{k>=0} Binom(N,N-2n-2k) Binom(n+k,n).
>
> Isso é uma soma hipergeométrica e usando as técnicas mostradas
> no livro (resultado de Gauss) Matemática Concreta obtemos
> S_N(n) = [N / (N-n)] Binom(N-n,n) 2^(N-2n-1).
>
> []'s
> Luís
>
>
> >From: "claudio.buffara" <[EMAIL PROTECTED]>
> >Reply-To: obm-l@mat.puc-rio.br
> >To: "obm-l"
> >Subject: Re: [obm-l] soma de termos
> >Date: Wed, 6 Apr 2005 09:01:29 -0300
> >
> >Oi, Bernardo:
> >
> >Eu falei mal da indução porque acho que ela produz demonstrações feias e
> >sem-graça, apesar de em muitos casos, ser a única forma (conhecida) de se
> >demonstrar algum resultado.
> >
> >Mas não é o caso da lei das colunas:
> >C(k,k) + C(k+1,k) + C(k+2,k) + ... + C(n,k) = C(n+1,k+1).
> >
> >Imagine que você quer formar subconjuntos de {1, 2, 3, ..., n, n+1} com k+1
> >elementos.
> >
> >Obviamente isso pode ser feito de C(n+1,k+1) maneiras diferentes.
> >
> >Mas quantos destes subconjuntos tem o inteiro positivo p
> >(k+1 <= p <= n+1) como maior elemento?
> >Bem, uma vez escolhido p, e dado que p é o maior elemento, os demais k
> >elementos só podem ser escolhidos dentre {1, 2, ..., p-1} e de C(p-1,k)
> >maneiras distintas.
> >Somando de p = k+1 até p = n+1, obtemos o número desejado:
> >C(k,k) + C(k+1,k) + ... + C(n,k)
> >
> >Com todo o respeito à sua demonstração, acho esta mais elegante. Além
> >disso, ela dá uma interpretação "concreta" para a lei das colunas.
> >
> >***
> >
> >Um exercício que acho interessante é tentar dar uma demonstração do tipo
> >acima para cada propriedade do triângulo de Pascal.
> >
> >
> >[]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] 1^2 + 2^2 + ... + n^2
Essa já deve ter por aí na lista, mas só para constar... Lembremos que (n + 1)^3 = n^3 + 3.n^2 + 3.n + 1 Para n = 0, 1, 2, ...,n , temos n = 0, (0+1)^3 = 1^3 = 0^3 + 3.0^2 + 3.0 + 1 n = 1, (1+1)^3 = 2^3 = 1^3 + 3.1^2 + 3.1 + 1 n = 2, (2+1)^3 = 3^3 = 2^3 + 3.2^2 + 3.2 + 1 n = 3, (3+1)^3 = 4^3 = 3^3 + 3.3^2 + 3.3 + 1 n = 4, (4+1)^3 = 5^3 = 4^3 + 3.4^2 + 3.4 + 1 n = n, (n+1)^3 = (n+1)^3 = n^3 + 3.n^2 + 3.n + 1 Somando membro a membro as (n + 1) igualdades acima, fica: 1^3 + 2^3 + 3^3 + ... + n^3 + (n+1)^3 = 1^3 + 2^3 + 3^3 + ... + n^3 + 3(1^2+2^2+3^2+...+n^2) + 3(1+2+3+...+n) + (n+1).1 arrumando, vem: (n + 1)^3 = 3(1^2+2^2+3^2+...+n^2) + 3(1+2+3+...+n) + (n+1). Chamemos de S a soma 1^2 + 2^2 + 3^2 + ... +n^2 . Admitindo conhecido que 1 + 2 + 3 + 4 + ... + n = n(n+1)/2 e fazendo as substituições: (n + 1)^3 = 3.S + 3.n(n+1)/2 + n+1. Isolando o termo S, etcetera e tal , obtemos a soma procurada S=n*(n+1)*(2n+1)/6. ( ^_ ^) _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = 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] Quadrados mágicos
Eu tenho a impressão de que a dimensão do espaço dos quadrados mágicos é n^2 - 2n + 1, pois, segundo o exercício 3.33 do Elon, os funcionais lineares de F^(2n) -> F: L_1, L_2, ..., L_n, C_1, C_2, ..., C_(n-1), T e S onde: L_i = soma dos elementos da i-ésima linha; C_j = soma dos elementos da j-ésima coluna; T = traço; S = soma dos elementos da diagonal secundária são L.I. de modo que você perde apenas 2n-1 graus de liberdade. Naturalmente, L_1 + L_2 + ... + L_n = C_1 + C_2 + ... + C_n = soma dos coeficientes da matriz, de modo que C_n é linearmente dependente dos demais. Ainda estou pensando em como demonstrar a independência linear de T e S em relação aos L_i e aos C_j. Também não consigo ver o que pode dar errado se F for finito. Só tome cuidado com uma coisa: por exemplo, em (Z_3)^2, temos: 1*(1,2) + 1*(2,1) = (0,0), ou seja, (1,2) e (2,1) são L.D., o que parece ser uma contradição até você se lembrar que em, (Z_3)^2, 2*(1,2) = (2,1) []s, Claudio. De: [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Wed, 06 Apr 2005 00:35:30 + Assunto: [obm-l] Quadrados mágicos > Olá! > > Uma matriz n x n chama-se um quadrado mágico quando a soma dos elementos de > cada uma de suas linhas, de cada coluna da diagonal principal e da outra > diagonal (ao todo 2n + 2 somas) são iguais. Prove que, se n >= 3, o conjunto > Q_n dos quadrados mágicos n x n é um subespaço vetorial de dimensão n^2 - 2n > do espaço das matrizes n x n sobre o corpo dos reais, ou, se preferir, dos > racionais (não sei se funciona para corpo finito). > > Na verdade, esse é um exercício essencialmente copiado do livro do Elon de > Álgebra Linear, e eu resolvi postar aqui para curar as saudades que o > pessoal sente da época em que foi apresentado ao quadrado "efetivamente" > mágico 4 x 4 onde todas as casas são inteiros distintos variando de 1 a 16! > > []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 > = >
[obm-l] somas binomiais [era: soma de termos]
Sauda,c~oes,
Oi Claudio,
O que você disse é verdade, inclusive no CRUX teve alguém
fazendo o mesmo comentário. Só que a referência é o livro
A=B do Doron Zeilberger e outros, publicado por A K Peters.
Há um programa que resolve tais problemas, inclusive pedi e
fui atendido pelo Doron na busca (de algumas) pela recorrência
que estas somas satisfazem.
O problema que você menciona é realmente difícil. Ele é o
problema 52 no livro que vou lançar lá pelo dia 15/05, envolvendo
121 somas combinatórias. O das colunas é o 12.
Resolvo algebricamente (combinação de resultados)
SOMA(k=0...n) Binom(p+k,m)*Binom(n-k,m) = Binom(n+p+1,2m+1)
(m>=p>=0).
Imagino que no IME a solução apresentada foi combinatória. Estas
soluções combinatórias não fazem parte do livro. Já começo a pensar
numa próxima edição com elas. Indo a SP como já lhe disse, poderemos
falar a respeito.
A soma parecida SOMA(k>=0) Binom(m,k)*Binom(n+k,m) foi tirada
do Winning Solutions do Rousseau. Não tem forma fechada conhecida
mas mostra-se algebricamente (é o problema 88) que vale
SOMA(k>=0) Binom(m,k)*Binom(n,k) 2^k (m,n>=0).
O prof. Doron me mandou a recorrência satisfeita pela soma S_n(m):
(n+2)S_{n+2}(m) - (2m+1)S_{n+1}(m) - (n+1)S_n(m)=0.
Logo, S_0(m)=1, S_1(m)=2m+1 e com a recorrência,
S_2(m)=2m^2+2m+1, S_3(m)=(2m+1)(2m^2+2m+3)/3 ...
[]'s
Luís
From: "claudio.buffara" <[EMAIL PROTECTED]>
Reply-To: obm-l@mat.puc-rio.br
To: "obm-l"
Subject: Re: [obm-l] soma de termos
Date: Wed, 6 Apr 2005 15:58:30 -0300
Oi, Luís:
A impressão que eu tenho é que, depois do "Generatingfunctionology", todos
estes problemas podem ser resolvidos pela aplicação de algum algoritmo
geral.
Mesmo, assim, acho que é um bom treino tentar achar demonstrações
combinatórias pra recorrências e identidades envolvendo números binomiais.
Por exemplo, é possível dar uma demonstração combinatória da identidade
abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81.
SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1).
Agora, quero ver alguém provar isso algebricamente...
[]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
=
[obm-l] cálculo no R^n
Gostaria de uma ajuda nos dois problemas abaixo:
1) Mostre que g(x,y) = (int_{0 ... x-y} f(t) dt, int_{0 ... xx - yy} f(t) dt) é um difeomorfismo do aberto A = {(x,y) em R^2 ; 0 < x < y} sobre um aberto de R^2, sabendo que a função f: [0,+infinit) --> (0, +infinito) é contínua.
Notação: int_{b ... c} f(t) dt = integral de f(t), com t variando de b a c.
2) Seja f: R^n --> R^n dada por f(x) = .x. Mostre que f é de classe C infinito e que leva a bola unitária B(0;1) sobre si mesma injetivamente. Mostre que, entretanto, a aplicação inversa não é diferenciável na origem.
Notação: <,> = produto interno
Grato desde já, Francisco Medeiros.
Yahoo! Acesso Grátis: Internet rápida e grátis. Instale o discador agora!
[obm-l] cálculo no R^n
Gostaria de uma ajuda nos dois problemas abaixo:
1) Mostre que g(x,y) = (int_{0 ... x-y} f(t) dt, int_{0 ... xx - yy} f(t) dt) é um difeomorfismo do aberto A = {(x,y) em R^2 ; 0 < x < y} sobre um aberto de R^2, sabendo que a função f: [0,+infinit) --> (0, +infinito) é contínua.
Notação: int_{b ... c} f(t) dt = integral de f(t), com t variando de b a c.
2) Seja f: R^n --> R^n dada por f(x) = .x. Mostre que f é de classe C infinito e que leva a bola unitária B(0;1) sobre si mesma injetivamente. Mostre que, entretanto, a aplicação inversa não é diferenciável na origem.
Notação: <,> = produto interno
Grato desde já, éder.
Yahoo! Acesso Grátis: Internet rápida e grátis. Instale o discador agora!
Re: [obm-l] soma de termos
Oi Cláudio.. Realmente é muito mais legal uma demonstração combinatória: Considere o conjunto dos números 0,1,2,3,...,n. Você quer escolher um sequencia a1 < a2 < ... < a(2m+1) de 2m+1 elementos, o que pode ser feito de "lado direito modos". Por outro lado, para cada k=0...n, voce pode escolher o elemento k como sendo o termo do meio dessa sequencia, e então precisa escolher binomial(k,m) termos menores e binomial(n-k,m) termos maiores que k. Somando em k, vemos que a resposta é o lado esquerdo e está provado. Mas não é tão feio fazer algebricamente..Vamos generalizar e provar que Soma(k=0..n) Binomial(k,a)*Binomial(n-k,b) = Binomial (n+1,a+b+1) Por inducao em n. Para n=0 eh facil. Supondo valido para n fixo e a,b quaisquer, temos: Soma(k=0..n+1) Binomial(k,a)*binomial (n+1-k,b) = Soma(k=0..n) Binomial(k,a)*[Binomial(n-k,b)+Binomial(n-k,b-1)] + Binom(n+1,a)*Binom(0,b) Usando a hipotese indutiva, isso da: Binomial(n+1,a+b+1) + Binomial(n+1, a+b) = Binomial (n+2, a+b+1) Em particular, fazendo a=b=m voce tem a solucao do problema pedido ;) (tá, confesso que tentei fazer a indução direto antes e não consegui :) E demorei bem menos pra dar a solução combinatória do que por indução.. mas não resisti ao "quero ver alguém ..." :) Abraços, Marcio - Original Message - From: claudio.buffara To: obm-l Sent: Wednesday, April 06, 2005 3:58 PM Subject: Re: [obm-l] soma de termos Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). Agora, quero ver alguém provar isso algebricamente...
[obm-l] Quadrado Mágico
Acho que sei como demonstrar que L_i (1<=i<=n), C_j (1<=j<=n-1), T e S são funcionais lineares L.I. Suponhamos que existam escalres a_i (1<=i<=n), b_j (1<=j<=n), c e d tais que o funcional linear: F = SOMA(1...n) a_i*L_i + SOMA(1...n-1) b_j*C_j + c*T + d*S seja identicamente nulo. Seja A(i,j) a matriz cujo coeficiente (i,j) é 1 e todos os demais são 0. F(A(1,n)) = 0 ==> a_1 + d = 0 F(A(n,n)) = 0 ==> a_n + c = 0 F(A(k,n)) = 0 para 2 <= k <= n-1 ==> a_k = 0. Ou seja, já podemos escrever: F = -d*L_1 - c*L_n + SOMA(1..n-1) b_j*C_j + c*T + d*S. F(A(1,1)) = 0 ==> -d + b_1 + c = 0 F(A(2,1)) = 0 ==> b_1 = 0 ==> c = d F(A(k+1,k)) = 0 para 2 <= k <= n-2 ==> b_k = 0 F(A(n,n-1)) = 0 ==> -c + b_(n-1) = 0 Assim: F = c*(-L_1 - L_n + C_(n-1) + T + S). Finalmente, F(A(2,2)) = 0 ==> c = 0. Logo, a_i = b_j = c = d = 0 e, portanto, os 2n+1 funcionais acima são L.I. e, portanto, o espaço dos quadrados mágicos nxn tem dimensão n^2 - (2n+1) = n^2 - 2n - 1. []s, Claudio.
Re: [obm-l] Logaritmo
Oi Fernando Não vejo porque não? Se t=1 y=4x+4 que substituido em 2^y = x^4*2^(4x) confirma a igualdade, com x=2 e y=12... []'s Wilner --- Fernando <[EMAIL PROTECTED]> wrote: > > log(y/2) na base 2 = X , e > > >y = 4log(x/2) na base 2 - log(1/y^4) na base 2 > > >Determine o(s) par(es) de x e y que sataisfaça as > esquações > > > > > > y=log(x^4/2^4)-log(1/y^4)=log(x^4*y^4)/2^4y=log(x^4)*(2^4x) > > 2^y=x^4*2^4x > > x=2^t > > y=4t+4x > > > Mas não é para qualquer valor de T :/, colocando -se > t = 1, já não se é > verificado a igualdade > > > = > 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 > = > Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador agora! http://br.acesso.yahoo.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] Logaritmo
> > log(y/2) na base 2 = X , e> > >y = 4log(x/2) na base 2 - log(1/y^4) na base 2 Mas se vc colocar x=2, e y=2 iremos ter log(y/2) na base 2 = X log(y/2) na base 2 = 2 (y/2) = 2^2 y = 8, e não igual a 12 como supoe a resolução De: [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Wed, 6 Apr 2005 18:43:01 -0300 (ART) Assunto: Re: [obm-l] Logaritmo > Oi Fernando > > Não vejo porque não? > > Se t=1 y=4x+4 que substituido em 2^y = > x^4*2^(4x) > confirma a igualdade, com x=2 e y=12... > > []'s > Wilner > > > > --- Fernando <[EMAIL PROTECTED]>wrote: > > > log(y/2) na base 2 = X , e > > > >y = 4log(x/2) na base 2 - log(1/y^4) na base 2 > > > >Determine o(s) par(es) de x e y que sataisfaça as > > esquações > > > > > > > > > > y=log(x^4/2^4)-log(1/y^4)=log(x^4*y^4)/2^4y=log(x^4)*(2^4x) > > > 2^y=x^4*2^4x > > > x=2^t > > > y=4t+4x > > > > > Mas não é para qualquer valor de T :/, colocando -se > > t = 1, já não se é > > verificado a igualdade > > > > > > > = > > 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 > > > = > > > > > > > > Yahoo! Acesso Grátis - Internet rápida e grátis. > Instale o discador agora! http://br.acesso.yahoo.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 > = > > E-mail classificado pelo Identificador de Spam Inteligente Terra. > Para alterar a categoria classificada, visite > http://mail.terra.com.br/protected_email/imail/imail.cgi?+_u=luizinho_cb&_l=1,1112825448.70599.6812.cabue.terra.com.br,3094,Des15,Des15 > > Esta mensagem foi verificada pelo E-mail Protegido Terra. > Scan engine: McAfee VirusScan / Atualizado em 06/04/2005 / Versão: 4.4.00 - Dat 4463 > Proteja o seu e-mail Terra: http://mail.terra.com.br/
RE: [obm-l] 1^2 + 2^2 + ... + n^2
Ola Rhilbert e demais colegas desta lista ... OBM-L, Tambem só para constar, segue a solucao que um Matematico deu, quando ainda era crianca : Seja Sn=1+2+...+N. Podemos imaginar a soma dos quadrados (Sq) colocados assim 1+2+3+4+...+N *+2+3+4+...+N *+*+3+4+...+N *+*+*+4+...+N ... *+*+*+*+...+N Substituindo ( de cima para baixo ) cada * pelo numero acima, termos um quadradinho cuja soma dos termos e claramente igual a N*Sn. IMAGINE retirada a diagonal principal desse quadrinho ( que faz parte de Sq ). E facil perceber agora que cada coluna da parte de cima (acima da diagonal principal que foi imaginariamente retirada ) e o dobro de cada linha da parte de baixo ( abaixo da diagonal principal ). Isto e : Sq - Sn =2*(N*Sn - Sq) => Sq=[(2*N+1)*Sn]/3 Preenchendo um cubinho e supondo conhecidos Sn e Sq e possivel rapidamente e claramente achar 1^3 + 2^3 + ...+N^3. Como ? Um Abraco a todos ! Paulo Santa Rita 4,2117,060405 From: "Rhilbert Rivera" <[EMAIL PROTECTED]> Reply-To: obm-l@mat.puc-rio.br To: obm-l@mat.puc-rio.br Subject: RE: [obm-l] 1^2 + 2^2 + ... + n^2 Date: Wed, 06 Apr 2005 19:23:47 + Essa já deve ter por aí na lista, mas só para constar... Lembremos que (n + 1)^3 = n^3 + 3.n^2 + 3.n + 1 Para n = 0, 1, 2, ...,n , temos n = 0, (0+1)^3 = 1^3 = 0^3 + 3.0^2 + 3.0 + 1 n = 1, (1+1)^3 = 2^3 = 1^3 + 3.1^2 + 3.1 + 1 n = 2, (2+1)^3 = 3^3 = 2^3 + 3.2^2 + 3.2 + 1 n = 3, (3+1)^3 = 4^3 = 3^3 + 3.3^2 + 3.3 + 1 n = 4, (4+1)^3 = 5^3 = 4^3 + 3.4^2 + 3.4 + 1 n = n, (n+1)^3 = (n+1)^3 = n^3 + 3.n^2 + 3.n + 1 Somando membro a membro as (n + 1) igualdades acima, fica: 1^3 + 2^3 + 3^3 + ... + n^3 + (n+1)^3 = 1^3 + 2^3 + 3^3 + ... + n^3 + 3(1^2+2^2+3^2+...+n^2) + 3(1+2+3+...+n) + (n+1).1 arrumando, vem: (n + 1)^3 = 3(1^2+2^2+3^2+...+n^2) + 3(1+2+3+...+n) + (n+1). Chamemos de S a soma 1^2 + 2^2 + 3^2 + ... +n^2 . Admitindo conhecido que 1 + 2 + 3 + 4 + ... + n = n(n+1)/2 e fazendo as substituições: (n + 1)^3 = 3.S + 3.n(n+1)/2 + n+1. Isolando o termo S, etcetera e tal , obtemos a soma procurada S=n*(n+1)*(2n+1)/6. ( ^_ ^) _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = 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 = _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = 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] Quadrado Mágico
Oi, Cláudio '>'-- Mensagem Original -- '>'Date: Wed, 6 Apr 2005 17:46:51 -0300 '>'Subject: [obm-l] Quadrado Mágico '>'From: "claudio.buffara" <[EMAIL PROTECTED]> '>'To: "obm-l" '>'Reply-To: obm-l@mat.puc-rio.br '>' '>' '>'Acho que sei como demonstrar que L_i (1<=i<=n), C_j (1<=j<=n-1), T e S são '>'funcionais lineares L.I. '>' '>'Suponhamos que existam escalres a_i (1<=i<=n), b_j (1<=j<=n), c e d tais '>'que o funcional linear: '>'F = SOMA(1...n) a_i*L_i + SOMA(1...n-1) b_j*C_j + c*T + d*S '>'seja identicamente nulo. '>' '>'Seja A(i,j) a matriz cujo coeficiente (i,j) é 1 e todos os demais são 0. '>' '>'F(A(1,n)) = 0 ==> a_1 + d = 0 '>'F(A(n,n)) = 0 ==> a_n + c = 0 '>'F(A(k,n)) = 0 para 2 <= k <= n-1 ==> a_k = 0. '>' '>'Ou seja, já podemos escrever: '>'F = -d*L_1 - c*L_n + SOMA(1..n-1) b_j*C_j + c*T + d*S. '>' '>'F(A(1,1)) = 0 ==> -d + b_1 + c = 0 '>'F(A(2,1)) = 0 ==> b_1 = 0 ==> c = d '>'F(A(k+1,k)) = 0 para 2 <= k <= n-2 ==> b_k = 0 '>'F(A(n,n-1)) = 0 ==> -c + b_(n-1) = 0 '>' '>'Assim: '>'F = c*(-L_1 - L_n + C_(n-1) + T + S). '>' '>'Finalmente, F(A(2,2)) = 0 ==> c = 0. '>' '>'Logo, a_i = b_j = c = d = 0 e, portanto, os 2n+1 funcionais acima são L.I. '>'e, portanto, o espaço dos quadrados mágicos nxn tem dimensão n^2 - (2n+1) '>'= n^2 - 2n - 1. '>' '>'[]s, '>'Claudio. A demonstração da independência dos funcionais está ok, mas isso mostra que se Z é o conjunto das matrizes n x n tais que todos esses funcionais se anulam, então Z (na verdade um subespaço de M(nxn)) é tal que dim Z = dim M(nxn) - dim(F), onde por F é o subespaço gerado pelos 2n + 2 funcionais em questão no dual de M(nxn), isto é, dim Z = n^2 - (2n + 1) = n^2 - 2n - 1. Este resultado é mais geral: Se Z é o espaço dos zeros dos funcionais f_1, ..., f_k, que estão no dual de V, então dim Z = dim V - dim (f_1, ..., f_k). Mas claramente a matriz A com todas as coordenadas 1 satisfaz L_1(A) = ... = L_n(A) = C_1(A) = ... = C_n(A) = T(A) = S(A) = n <> 0, assim dim Q >= dim Z + 1 (Q = conjunto das matrizes A que satisfazem L_1(A) = ... = L_n(A) = C_1(A) = ... = C_n(A) = T(A) = S(A), ou seja, dos quadrados mágicos, um subespaço vetorial). Dá para provar que dim Q <= dim Z + 1 (naturalmente um resultado mais geral válido para quaisquer funcionais), logo dim Q = dim Z + 1 = n^2 - 2n. []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] Logaritmo
Oi gente. Deu bobeira geral (incluo-me)???!!! Estamos diante de um sistema de duas equações à duas incógnitas!!! O parâmetro t não pode assumir qualquer valor. Só exitem dois pares (x,y): um é (1,4) e o outro tem x algures entre 2 e 4 que pode ser pesquizado gráficamente ou por métodos de aproximação. []'s Wilner --- luizinho_cb <[EMAIL PROTECTED]> wrote: > > > log(y/2) na base 2 = X , e > > > >y = 4log(x/2) na base 2 - log(1/y^4) na base 2 > > Mas se vc colocar x=2, e y=2 > iremos ter > log(y/2) na base 2 = X > log(y/2) na base 2 = 2 > (y/2) = 2^2 > y = 8, e não igual a 12 como supoe a resolução > > > De:[EMAIL PROTECTED] > > Para:obm-l@mat.puc-rio.br > > Cópia: > > Data:Wed, 6 Apr 2005 18:43:01 -0300 (ART) > > Assunto:Re: [obm-l] Logaritmo > > > Oi Fernando > > > > Não vejo porque não? > > > > Se t=1 y=4x+4 que substituido em 2^y = > > x^4*2^(4x) > > confirma a igualdade, com x=2 e y=12... > > > > []'s > > Wilner > > > > > > > > --- Fernando wrote: > > > > log(y/2) na base 2 = X , e > > > > >y = 4log(x/2) na base 2 - log(1/y^4) na base > 2 > > > > >Determine o(s) par(es) de x e y que > sataisfaça as > > > esquações > > > > > > > > > > > > > > > y=log(x^4/2^4)-log(1/y^4)=log(x^4*y^4)/2^4y=log(x^4)*(2^4x) > > > > 2^y=x^4*2^4x > > > > x=2^t > > > > y=4t+4x > > > > > > > Mas não é para qualquer valor de T :/, colocando > -se > > > t = 1, já não se é > > > verificado a igualdade > > > > > > > > > > > > = > > > 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 > > > > > > = > > > > > > > > > > > > > > > Yahoo! Acesso Grátis - Internet rápida e grátis. > > Instale o discador agora! > http://br.acesso.yahoo.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 > > > = > > > > E-mail classificado pelo Identificador de Spam > Inteligente Terra. > > Para alterar a categoria classificada, visite > > > http://mail.terra.com.br/protected_email/imail/imail.cgi?+_u=luizinho_cb&_l=1,1112825448.70599.6812.cabue.terra.com.br,3094,Des15,Des15 > > > > Esta mensagem foi verificada pelo E-mail Protegido > Terra. > > Scan engine: McAfee VirusScan / Atualizado em > 06/04/2005 / Versão: 4.4.00 - Dat 4463 > > Proteja o seu e-mail Terra: > http://mail.terra.com.br/ > __ Converse com seus amigos em tempo real com o Yahoo! Messenger http://br.download.yahoo.com/messenger/ = 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] Quadrado Mágico
on 06.04.05 22:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote: > Oi, Cláudio > > '>'-- Mensagem Original -- > '>'Date: Wed, 6 Apr 2005 17:46:51 -0300 > '>'Subject: [obm-l] Quadrado Mágico > '>'From: "claudio.buffara" <[EMAIL PROTECTED]> > '>'To: "obm-l" > '>'Reply-To: obm-l@mat.puc-rio.br > '>' > '>' > '>'Acho que sei como demonstrar que L_i (1<=i<=n), C_j (1<=j<=n-1), T e > S são > '>'funcionais lineares L.I. > '>' > '>'Suponhamos que existam escalres a_i (1<=i<=n), b_j (1<=j<=n), c e d > tais > '>'que o funcional linear: > '>'F = SOMA(1...n) a_i*L_i + SOMA(1...n-1) b_j*C_j + c*T + d*S > '>'seja identicamente nulo. > '>' > '>'Seja A(i,j) a matriz cujo coeficiente (i,j) é 1 e todos os demais são > 0. > '>' > '>'F(A(1,n)) = 0 ==> a_1 + d = 0 > '>'F(A(n,n)) = 0 ==> a_n + c = 0 > '>'F(A(k,n)) = 0 para 2 <= k <= n-1 ==> a_k = 0. > '>' > '>'Ou seja, já podemos escrever: > '>'F = -d*L_1 - c*L_n + SOMA(1..n-1) b_j*C_j + c*T + d*S. > '>' > '>'F(A(1,1)) = 0 ==> -d + b_1 + c = 0 > '>'F(A(2,1)) = 0 ==> b_1 = 0 ==> c = d > '>'F(A(k+1,k)) = 0 para 2 <= k <= n-2 ==> b_k = 0 > '>'F(A(n,n-1)) = 0 ==> -c + b_(n-1) = 0 > '>' > '>'Assim: > '>'F = c*(-L_1 - L_n + C_(n-1) + T + S). > '>' > '>'Finalmente, F(A(2,2)) = 0 ==> c = 0. > '>' > '>'Logo, a_i = b_j = c = d = 0 e, portanto, os 2n+1 funcionais acima são > L.I. > '>'e, portanto, o espaço dos quadrados mágicos nxn tem dimensão n^2 - (2n+1) > '>'= n^2 - 2n - 1. > '>' > '>'[]s, > '>'Claudio. > > A demonstração da independência dos funcionais está ok, mas isso mostra > que se Z é o conjunto das matrizes n x n tais que todos esses funcionais > se anulam, então Z (na verdade um subespaço de M(nxn)) é tal que dim Z = > dim M(nxn) - dim(F), onde por F é o subespaço gerado pelos 2n + 2 funcionais > em questão no dual de M(nxn), isto é, dim Z = n^2 - (2n + 1) = n^2 - 2n > - 1. Este resultado é mais geral: Se Z é o espaço dos zeros dos funcionais > f_1, ..., f_k, que estão no dual de V, então dim Z = dim V - dim (f_1, ..., > f_k). > > Mas claramente a matriz A com todas as coordenadas 1 satisfaz L_1(A) = ... > = L_n(A) = C_1(A) = ... = C_n(A) = T(A) = S(A) = n <> 0, assim dim Q >= > dim Z + 1 (Q = conjunto das matrizes A que satisfazem L_1(A) = ... = L_n(A) > = C_1(A) = ... = C_n(A) = T(A) = S(A), ou seja, dos quadrados mágicos, um > subespaço vetorial). Dá para provar que dim Q <= dim Z + 1 (naturalmente > um resultado mais geral válido para quaisquer funcionais), logo dim Q = > dim Z + 1 = n^2 - 2n. > > []s, > Daniel > Claro! Eu esqueci justamente de levar em conta a condicao de quadrado magico... Uma forma mais elementar de ver isso eh observar que o espaco dos quadrados magicos eh justamente o espaco-solucao do seguinte sistema de 2n equacoes lineares homogeneas (e linearmente independentes, como demonstrado acima) em n^2 incognitas: L_1 - T = 0 L_2 - T = 0 ... L_n - T = 0 C_1 - T = 0 C_2 - T = 0 ... C_(n-1) - T = 0 S - T = 0 Logo, o espaco solucao do sistema (igual a Q) tem dimensao n^2 - 2n. []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] soma de termos
Title: Re: [obm-l] soma de termos Oi, Marcio: O que eu tinha em mente, quando falei em solucao algebrica, era abrir os numeros binomais e tentar simplificar o emaranhado de fatoriais resultante. Mas como nao fui totalmente explicito, tenho que aceitar esta solucao indutiva. Talvez seja a vinganca da inducao pelo que eu andei falando a respeito dela :-) []s, Claudio. on 06.04.05 18:29, Marcio Cohen at [EMAIL PROTECTED] wrote: Oi Cláudio.. Realmente é muito mais legal uma demonstração combinatória: Considere o conjunto dos números 0,1,2,3,...,n. Você quer escolher um sequencia a1 < a2 < ... < a(2m+1) de 2m+1 elementos, o que pode ser feito de "lado direito modos". Por outro lado, para cada k=0...n, voce pode escolher o elemento k como sendo o termo do meio dessa sequencia, e então precisa escolher binomial(k,m) termos menores e binomial(n-k,m) termos maiores que k. Somando em k, vemos que a resposta é o lado esquerdo e está provado. Mas não é tão feio fazer algebricamente..Vamos generalizar e provar que Soma(k=0..n) Binomial(k,a)*Binomial(n-k,b) = Binomial (n+1,a+b+1) Por inducao em n. Para n=0 eh facil. Supondo valido para n fixo e a,b quaisquer, temos: Soma(k=0..n+1) Binomial(k,a)*binomial (n+1-k,b) = Soma(k=0..n) Binomial(k,a)*[Binomial(n-k,b)+Binomial(n-k,b-1)] + Binom(n+1,a)*Binom(0,b) Usando a hipotese indutiva, isso da: Binomial(n+1,a+b+1) + Binomial(n+1, a+b) = Binomial (n+2, a+b+1) Em particular, fazendo a=b=m voce tem a solucao do problema pedido ;) (tá, confesso que tentei fazer a indução direto antes e não consegui :) E demorei bem menos pra dar a solução combinatória do que por indução.. mas não resisti ao "quero ver alguém ..." :) Abraços, Marcio - Original Message - From: claudio.buffara To: obm-l Sent: Wednesday, April 06, 2005 3:58 PM Subject: Re: [obm-l] soma de termos Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). Agora, quero ver alguém provar isso algebricamente...
Re: [obm-l] soma de termos
claudio.buffara wrote: Oi, Luís: A impressão que eu tenho é que, depois do "Generatingfunctionology", todos estes problemas podem ser resolvidos pela aplicação de algum algoritmo geral. Mesmo, assim, acho que é um bom treino tentar achar demonstrações combinatórias pra recorrências e identidades envolvendo números binomiais. Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). O algoritmo WZ consegue provar identidades entre termos hipergeométricos (como é o caso deste) sem problema algum, mas ele não obtém a expressão pra você, ela deve vir de alguma conjectura, por exemplo. O Wilf apresenta no livro dele o Snake Oil Method para resolução de algumas somas, mas não é um método que tem garantia de funcionar, ele simplesmente funciona razoavelmente bem. Alguém sabe dizer qual é o estado da arte em relação ao maquinário computacional que *determina* fórmulas fechadas para somatórios envolvendo termos hipergeométricos? [ ]'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] [x^n] == n (mod 2)
claudio.buffara wrote: Aqui vai um bonitinho: Ache um número real x tal que, para todo n inteiro e positivo, [x^n] tem a mesma paridade que n. [a] = maior inteiro que é menor ou igual a a. Se não me engano, há algum tempo, o Shine exibiu um y tal que [y^n] é sempre ímpar. []s, Claudio. Você quer um x irracional, Cláudio? [ ]'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] [x^n] == n (mod 2)
Title: Re: [obm-l] [x^n] == n (mod 2) Me enganei (mais uma vez...) O problema abaixo eh valido, mas eh trivial (eu me dei conta disso no caminho pra casa). Mais interessante eh o seguinte: ache x real tal que [x^n] tem paridade oposta a de n. E o que o Shine exibiu foi um numero NAO-INTEIRO x tal que [x^n] eh sempre impar. (se x puder ser inteiro, basta tomar x = 1 ou x = impar qualquer). Tambem eh trivial exibir um nao-inteiro x tal que [x^n] eh sempre par. Alias, eh curioso que [x^n] sempre par ou [x^n] de mesma paridade que n sao problemas bem mais faceis do que [x^n] sempre impar ou [x^n] de paridade oposta a de n. No mais, prove ou de um contra-exemplo: 1) dado um racional positivo qualquer x, sempre vai existir um inteiro positivo n tal que: [x^n] e [x^(n+1)] tem a mesma paridade. 2) existe um numero real x tal que [x^n] eh primo para todo inteiro positivo n. []s, Claudio. on 06.04.05 17:01, claudio.buffara at [EMAIL PROTECTED] wrote: Aqui vai um bonitinho: Ache um número real x tal que, para todo n inteiro e positivo, [x^n] tem a mesma paridade que n. [a] = maior inteiro que é menor ou igual a a. Se não me engano, há algum tempo, o Shine exibiu um y tal que [y^n] é sempre ímpar. []s, Claudio.
Re: [obm-l] [x^n] == n (mod 2)
on 06.04.05 23:13, Domingos Jr. at [EMAIL PROTECTED] wrote: > claudio.buffara wrote: > >> Aqui vai um bonitinho: >> >> Ache um número real x tal que, para todo n inteiro e positivo, [x^n] >> tem a mesma paridade que n. >> >> [a] = maior inteiro que é menor ou igual a a. >> >> Se não me engano, há algum tempo, o Shine exibiu um y tal que [y^n] é >> sempre ímpar. >> >> []s, >> Claudio. >> > > > Você quer um x irracional, Cláudio? > > [ ]'s > Me mostre tres valores de x: um racional, um irracional algebrico e um transcendente. = 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] Quadrado Mágico
on 06.04.05 22:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote: > A demonstração da independência dos funcionais está ok, mas isso mostra > que se Z é o conjunto das matrizes n x n tais que todos esses funcionais > se anulam, então Z (na verdade um subespaço de M(nxn)) é tal que dim Z = > dim M(nxn) - dim(F), onde por F é o subespaço gerado pelos 2n + 2 funcionais > em questão no dual de M(nxn), isto é, dim Z = n^2 - (2n + 1) = n^2 - 2n > - 1. Este resultado é mais geral: Se Z é o espaço dos zeros dos funcionais > f_1, ..., f_k, que estão no dual de V, então dim Z = dim V - dim (f_1, ..., > f_k). > > Mas claramente a matriz A com todas as coordenadas 1 satisfaz L_1(A) = ... > = L_n(A) = C_1(A) = ... = C_n(A) = T(A) = S(A) = n <> 0, assim dim Q >= > dim Z + 1 (Q = conjunto das matrizes A que satisfazem L_1(A) = ... = L_n(A) > = C_1(A) = ... = C_n(A) = T(A) = S(A), ou seja, dos quadrados mágicos, um > subespaço vetorial). Dá para provar que dim Q <= dim Z + 1 (naturalmente > um resultado mais geral válido para quaisquer funcionais), logo dim Q = > dim Z + 1 = n^2 - 2n. > > []s, > Daniel > Claro! Eu esqueci da condicao de que as matrizes sao quadrados magicos... Uma forma mais elementar de ver isso eh observar que o espaco dos quadrados magicos eh justamente o espaco-solucao de um sistema linear homogeneo de 2n equacoes em n^2 incognitas. As equacoes sao: L_1 - T = 0 ... L_n - T = 0 C_1 - T = 0 ... C_(n-1) - T = 0 S - T = 0 Como jah vimos, estas equacoes sao L.I. jah que os funcionais lineares correspondentes sao L.I. Logo, a dimensao do espaco solucao eh n^2 - 2n = dim(Q). []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 =
[obm-l] Re: [obm-l] cálculo no R^n
Oi pessoal, estou de volta. Vou tentar
resolver (realmente
quando se trata de demonstrações eu sou mesmo
um
mau técnico):
-
1) Mostre que g(x,y) = (int_{0 ... x-y} f(t) dt, int_{0 ... xx - yy} f(t)
dt) é um difeomorfismo do aberto A = {(x,y) em R^2 ; 0 < x <
y} sobre um aberto de R^2, sabendo que a função f: [0,+infinit) --> (0,
+infinito) é contínua.
Neste caso, consideremos que o aberto de R^2
resultante
seja a imagem
da aplicação de g sobre A.
Inicialmente mostramos que a aplicação
g(x,y) é injetiva
sobre a imagem pois no caso que abordamos
ela é sobrejetiva (não demonstrado aqui). Com isso
provamos que (x,y) -->
g(x,y) é um
homeomorfismo. Para provar que a
aplicação é um
difeomorfismo basta considerar a derivada de g(x,y)
em
relação a t. Fazemos isso aplicando a
regra de Leibnitz
(diferenciação sobre o sinal de integração).
Como por
hipótese a função f(t) é contínua sobre o intervalo
considerado teremos pela fórmula de Leibnitz
e pela
composição de funções contínuas (que é contínua)
temos
portanto um difeomorfismo.
Faltam
detalhes é claro, mas acho que esta é a idéia
básica.
- Orig
inal Message -
From:
Lista
OBM
To: Lista OBM
Sent: Wednesday, April 06, 2005 5:17
PM
Subject: [obm-l] cálculo no R^n
Gostaria de uma ajuda nos dois problemas abaixo:
1) Mostre que g(x,y) = (int_{0 ... x-y} f(t) dt, int_{0 ... xx - yy} f(t)
dt) é um difeomorfismo do aberto A = {(x,y) em R^2 ; 0 < x <
y} sobre um aberto de R^2, sabendo que a função f: [0,+infinit) -->
(0, +infinito) é contínua.
Notação: int_{b ... c} f(t) dt = integral de f(t), com
t variando de b a c.
2) Seja f: R^n --> R^n dada por f(x) = .x. Mostre que
f é de classe C infinito e que leva a bola unitária B(0;1) sobre si mesma
injetivamente. Mostre que, entretanto, a aplicação inversa não é diferenciável
na origem.
Notação: <,> = produto interno
Grato desde já, Francisco Medeiros.
Yahoo!
Acesso Grátis: Internet rápida e grátis. Instale o discador
agora!
[obm-l] Re: [obm-l] cálculo no R^n
-
2) Seja f: R^n
--> R^n dada por f(x) = .x. Mostre que f é de classe C infinito e
que leva a bola unitária B(0;1) sobre si mesma injetivamente. Mostre que,
entretanto, a aplicação inversa não é diferenciável na origem.
Neste caso se x \in B(0;1) então = ||x||
e
0<||x|| < 1. Logo a aplicação é uma contração de x.
A contração é diferenciável e de classe
C^{\infty}.
É mais ou menos intuitivo que neste caso a apliação seja
injetiva. Por exemplo: Vetores próximos da fronteira
tem norma 1 e portanto serão "pouco contraídos".
Assim a demonstração de injetividade usa esse
fato,
isto é, se tomarmos um ponto x próximo próximo da
fronteira, podemos sempre escolher um f^{-1}(x) tal
que f composto com f^{-1}(x) = x e vice versa.
Como ||x|| é sempre menor
que 1
esses pontos tem que ser diferentes.
Para entender por que a aplicação não
é diferenciável
na origem basta notar que "quanto mais perto o vetor
estiver da origem mais contraído será" na aplicação direta.
(reciprocamente na aplicação inversa mais expandido
será). A origem é uma espécie
de "buraco
negro ao contrário" logo não pode ter derivada
lá. Argumentos do teorema de função implícita podem
ajudar.
Novamente sem rigor... apenas com idéias.
[]s Ronaldo L. Alonso
