Re: [obm-l] Casa de Pombos e Desigualdade com Pi
Boa noite Carlos e Claudio.Lembro-me bem que quando esta questão foi postada na lista da OBM, foi pedido para que se resolvesse a demonstração de que raiz(2) + raiz(3) Piutilizando GEOMETRIA.Alguem tem alguma solução?Abraços, Felipe Marinho de Oliveira SardinhaCarlos Yuzo Shine [EMAIL PROTECTED] escreveu: Oi,Primeiro, eu enviei sem querer um email antes doúltimo que mandei. Eu cliquei no botão errado,desculpem-me.Eu descobri que depois de provar para primo, é sófazer com indução sobre a quantidade de fatores primos(não necessariamente distintos) de n.Seja n = pk, p primo. Separe 2k-1 dos 2pk-1 números.Pela hipótese de indução, existem k cuja soma édivisível por k. Tome os outros k-1 e coloque devolta, obtendo
2(p-1)k-1 números. Separe novamente2k-1 desses números e aplique a hipótese de induçãomais uma vez. Na verdade, aplique a hipótese deindução 2p-1 vezes, obtendo 2p-1 conjuntos disjuntosdois a dois de k números, todos eles com somasdivisíveis por k. Cosidere agora as 2p-1 somasobtidas, todas múltiplas de k. Se k tem m fatores p,divida todas as somas por p^m. Aplique agora ahipótese de indução sobre esses 2p-1 números: p dessassomas (divididas por p^m) somam um múltiplo de p. Aíacabou, pois a soma original é múltipla de p^(m+1)(conseguimos colocar mais um fator p) e, portanto, den. E temos p*k = n números.Muito legal esse problema. Tem um outro muito bomtambém, que é o teorema de Cauchy-Davenport:Seja p um número primo e A, B subconjuntos de Z/pZ. SeA + B := {a+b,a em A e b em B} e |X| é a quantidade deelementos do conjunto X, prove que|A + B| = mín(|A| + |B| - 1,
p).[]'sShine--- "claudio.buffara" <[EMAIL PROTECTED]>wrote: Esse tah me enchendo o saco: Prove que toda sequencia de 2n-1 inteiros (nao necessariamente distintos) possui uma subsequencia de n inteiros cuja soma eh divisivel por n. *** Ha alguns meses alguem mandou pra lista o problema de se provar que: raiz(2) + raiz(3) Pi. Foi enviada alguma solucao? []s, Claudio. __Do You Yahoo!?Tired of spam? Yahoo! Mail has the best spam protection around http://mail.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=
Novidade no Yahoo! Mail: receba alertas de novas mensagens no seu celular. Registre seu aparelho agora!
Re: [obm-l] Casa de Pombos e Desigualdade com Pi
Viva as férias (até que enfim) Bom, o seu PCP ainda nao foi, mas pra \pi (estilo NA MARRA): Eleve ao quadrado (todo mundo é positivo): 2 + 2 raiz(6) + 3 Pi^2 = 2 raiz(6) = Pi^2 - 5 E mais uma vez (notar que Pi 3 = Pi^2 9 5): 24 Pi^4 - 10Pi^2 + 25 = 0 Pi^4 - 10 Pi^2 + 1 Agora calcule as raízes de x^4 - 10x^2 + 1 ... x^2 = 5 +/- raiz(25 + 1) = apenas duas raizes, as da raiz positiva do quadrado x^2 = 10 + um pouquinho Agora saiba que Pi = 3.14159265358979... e que raiz(10) = 3.16.. e pronto: as raizes do polinômio sao maiores do que +- Pi, e portanto o valor em Pi é menor do que zero pois o coeficiente de segundo grau é positivo. Uma calculadora dá: sqrt(2) + sqrt(3) - %pi ans = 0.0046717 T+, -- Bernardo Freitas Paulo da Costa On 7/15/06, claudio.buffara [EMAIL PROTECTED] wrote: Esse tah me enchendo o saco: Prove que toda sequencia de 2n-1 inteiros (nao necessariamente distintos) possui uma subsequencia de n inteiros cuja soma eh divisivel por n. *** Ha alguns meses alguem mandou pra lista o problema de se provar que: raiz(2) + raiz(3) Pi. Foi enviada alguma solucao? []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] Casa de Pombos e Desigualdade com Pi
O de casa dos pombos é bem legal, na verdade.
Na verdade, vou provar algo mais forte: considere um
conjunto A de n números inteiros não divisíveis por n
(possivelmente com elementos repetidos). Então existe
um subconjunto de A cuja soma dos elementos é
divisível por n.
Note que isso prova o problema: se há pelo menos n
múltiplos de n, basta tomá-los; se há menos de n, há
pelo menos n não divisíveis e basta utilizar o
resultado acima.
Provemos por indução que um conjunto de k elementos
inteiros não múltiplos de n tem pelo menos k somas
diferentes módulo n, k = n.
Para k = 1 o resultado é óbvio. Agora suponha que o
resultado seja válido para k m = n e provemos o
resultado para k = m. Seja {a_1,a_2,...,a_{m-1},a} o
conjunto então, com a sendo o
--- Bernardo Freitas Paulo da Costa
[EMAIL PROTECTED] wrote:
Viva as férias (até que enfim)
Bom, o seu PCP ainda nao foi, mas pra \pi (estilo
NA MARRA):
Eleve ao quadrado (todo mundo é positivo):
2 + 2 raiz(6) + 3 Pi^2 = 2 raiz(6) = Pi^2 - 5
E mais uma vez (notar que Pi 3 = Pi^2 9 5):
24 Pi^4 - 10Pi^2 + 25 =
0 Pi^4 - 10 Pi^2 + 1
Agora calcule as raízes de x^4 - 10x^2 + 1 ...
x^2 = 5 +/- raiz(25 + 1) = apenas duas raizes, as
da raiz positiva do quadrado
x^2 = 10 + um pouquinho
Agora saiba que Pi = 3.14159265358979... e que
raiz(10) = 3.16.. e pronto:
as raizes do polinômio sao maiores do que +- Pi, e
portanto o valor em
Pi é menor do que zero pois o coeficiente de segundo
grau é positivo.
Uma calculadora dá:
sqrt(2) + sqrt(3) - %pi
ans = 0.0046717
T+,
--
Bernardo Freitas Paulo da Costa
On 7/15/06, claudio.buffara
[EMAIL PROTECTED] wrote:
Esse tah me enchendo o saco:
Prove que toda sequencia de 2n-1 inteiros (nao
necessariamente distintos)
possui uma subsequencia de n inteiros cuja soma eh
divisivel por n.
***
Ha alguns meses alguem mandou pra lista o problema
de se provar que:
raiz(2) + raiz(3) Pi.
Foi enviada alguma solucao?
[]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
=
__
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.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] Casa de Pombos e Desigualdade com Pi
O de casa dos pombos é bem legal, na verdade. Por enquanto eu sei provar para n primo. Por motivos psicológicos, seja n = p :). Considere todas as somas possíveis com p números. Se nenhuma delas é divisível por p então cada soma elevada a p-1 é 1 mód p. Some todas essas somas elevadas a p-1. Vamos abrir essa soma de somas. Vamos ver o caso p = 3 para entender melhor a idéia e depois generalizar. Sendo, então, x,y,z,w,t os números, abrimos, módulo 3, a soma (x+y+z)^2 + (x+y+w)^2 + (x+y+t)^2 + (x+z+w)^2 + (x+z+t)^2 + (x+w+t)^2 + (y+z+w)^2 + (y+z+t)^2 + (y+w+t)^2 + (z+w+t)^2 Se ninguém é divisível por 3, todo mundo é 1 módulo 3 e obtemos 10. Mas x^2, por exemplo, aparece 6 vezes (combinatoriamente: em binom(4,2) caras, pois basta escolher os dois companheiros a e b de x em (x+a+b)^2), e 2xy, em 3 caras (binom(3,1) - você pode conluir por quê?). Então a soma total é 0 módulo 3, absurdo. Logo uma das somas é divisível por 3. Agora, o caso geral (para primo). Na soma, cada x_1^a_1x_2^a_2...x_k^a_k aparece nas somas que contêm x_1,x_2,...,x_k, que são em total de binom(2p-1-k,p-k) = binom(2p-1-k,p-1) (basta escolhermos os demais p-k números entre os 2p-1-k números restantes). Note que 1 = k = p-1, pois a_1 + a_2 + ... + a_k = p-1, já que cada soma está sendo elevada a p-1. Mas binom(2p-1-k,p-1) = produto de p-1 consecutivos/(p-1)! sendo que nesse produto é obrigatório aparecer um múltiplo de p, pois 2p-1-k = p-1-k (mód p) e 0 = p-1-k = p-2. Logo cada termo aparece multiplicado por um múltiplo de p e logo a soma de somas elevadas a p-1 é zero. Se nenhuma das somas é divisível por p, então a soma das somas elevadas a p-1 é igual a binom(2p-1,p) módulo p. Mas acontece que (2p-1)! tem um único fator p, que é cortado pelo p! no binomial. Ou seja, binom(2p-1,p) não é divisível por p, absurdo. Logo uma das somas é múltipla de p. Para n composto ainda não sei fazer, mas eu li que dá para reduzir esse caso para n primo. []'s Shine __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.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] Casa de Pombos e Desigualdade com Pi
Oi,
Primeiro, eu enviei sem querer um email antes do
último que mandei. Eu cliquei no botão errado,
desculpem-me.
Eu descobri que depois de provar para primo, é só
fazer com indução sobre a quantidade de fatores primos
(não necessariamente distintos) de n.
Seja n = pk, p primo. Separe 2k-1 dos 2pk-1 números.
Pela hipótese de indução, existem k cuja soma é
divisível por k. Tome os outros k-1 e coloque de
volta, obtendo 2(p-1)k-1 números. Separe novamente
2k-1 desses números e aplique a hipótese de indução
mais uma vez. Na verdade, aplique a hipótese de
indução 2p-1 vezes, obtendo 2p-1 conjuntos disjuntos
dois a dois de k números, todos eles com somas
divisíveis por k. Cosidere agora as 2p-1 somas
obtidas, todas múltiplas de k. Se k tem m fatores p,
divida todas as somas por p^m. Aplique agora a
hipótese de indução sobre esses 2p-1 números: p dessas
somas (divididas por p^m) somam um múltiplo de p. Aí
acabou, pois a soma original é múltipla de p^(m+1)
(conseguimos colocar mais um fator p) e, portanto, de
n. E temos p*k = n números.
Muito legal esse problema. Tem um outro muito bom
também, que é o teorema de Cauchy-Davenport:
Seja p um número primo e A, B subconjuntos de Z/pZ. Se
A + B := {a+b,a em A e b em B} e |X| é a quantidade de
elementos do conjunto X, prove que
|A + B| = mín(|A| + |B| - 1, p).
[]'s
Shine
--- claudio.buffara [EMAIL PROTECTED]
wrote:
Esse tah me enchendo o saco:
Prove que toda sequencia de 2n-1 inteiros (nao
necessariamente distintos) possui uma subsequencia
de n inteiros cuja soma eh divisivel por n.
***
Ha alguns meses alguem mandou pra lista o problema
de se provar que:
raiz(2) + raiz(3) Pi.
Foi enviada alguma solucao?
[]s,
Claudio.
__
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.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
=
[obm-l] Casa de Pombos e Desigualdade com Pi
Esse tah me enchendo o saco: Prove que toda sequencia de2n-1 inteiros (nao necessariamente distintos) possui uma subsequencia de n inteiros cuja soma eh divisivel por n. *** Ha alguns meses alguem mandou pra lista o problema de se provar que: raiz(2) + raiz(3) Pi. Foienviada alguma solucao? []s, Claudio.
