Re: [obm-l] (2m)!(2n)!/(m!n!(m+n)!)

[Domingos Jr.]

claudio.buffara wrote:


Alguém conhece algum problema de combinatória cuja resposta seja:
(2m)!(2n)!/(m!n!(m+n)!) ?
 
Eu estou tentando provar que este número é inteiro, quaisquer que 
sejam m e n naturais mediante um argumento combinatório, mas até agora 
não consegui.
 
[]s,

Claudio.
 


Oi!

Isso é o mesmo que
Binom(2m, m)*Binom(2n, n) / Binom(m + n, m)
isso ajuda alguma interpretação?

PS: sumi por um bom tempo, mas estou vivo!


=
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: RES: [obm-l] Links com Argumentos contra Cantor e Godel

[Domingos Jr.]

Eu quase não tenho mais tempo para acessar a lista, mas quando vi essa 
pérola, não resisti a dar uma olhada na página do cara (autor dos 
argumentos contra Cantor e Göedel).


Este trecho, em particular, é fantástico:
"I am a generalist. My works at my Download Page reflect my skills as a 
thinker, writer, philosopher, scientist, inventor, computer expert and 
and composer. In addition my skills as a painter, chef, gardener, car 
enthusiast, sailor and hiker are known to my personal friends. And of 
course, my skills as a parent and spouse are known to my family."


O cara é muito bom! Temos que criar uma comunidade no orkut pra ele :-p

Abraços


=
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] Conjunto dos reais

[Domingos Jr.]

isso não é uma demonstração... aliás, não faz muito sentido o que você 
disse.
essas coisas 'óbvias' devem ser provadas diretamente a partir dos 
axiomas de construção dos reais, o que costuma ser bem chato.



A unica maneira de x+y nao ser real e se x e y forem complexos o que
cai numa contradiçao, os outros conjuntos, inteiros, naturais,
racionais estao dentro do conjunto dos numeros reais.

On 8/2/05, cfgauss77 <[EMAIL PROTECTED]> wrote:
 


 Gostaria de uma demonstração para a seguinte proposição:

"O conjunto dos reais é fechado para a adição, ou seja, sejam x e y reais,
então, x+y também é real".

  Desde já agradeço!!!
   



=
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] Re: [obm-l] dúvida conceitual

[Domingos Jr.]

Carlos Gomes wrote:

Claro que não, pois os vetores de uma base do R^2 tem duas coordenadas 
enquanto que os vetores do r^3 tem 3 coordenadas!



Podemos pensar um pouquinho fora da caixa...
Dois vetores LI no R^3 determinam um (hiper-)plano que é isomorfo ao R^2.
Acho que esse tipo de resposta é mais informativa do que um 'claro que não'.


=
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] Re: [obm-l] OFF TOPIC: programa de caraceteres matemáticos

[Domingos Jr.]

marcio aparecido wrote:


onde eu consigo esse LaTeX
 



achei que eu já tinha respondido isso.
windows: miktex
linux: tetex

procure no www.google.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
=

[obm-l] Re: [obm-l] OFF TOPIC: programa de caraceteres matemáticos

[Domingos Jr.]

[EMAIL PROTECTED] wrote:

Meus caros amigos, algum de vocês conhece algum programa ou editor de 
texto pelo qual eu consiga inserir caraceteres matemáticos( como 
potencias, frações..) e símbolos( pi, somatório..) no pc?

Gostaria de fazer um resumo das minhas matérias no pc.
Se alguém puder me ajudar..
abços
Junior


Uma opção mais profissional é o LaTeX.
Para o windows, baixe o miktek. No linux você pode pegar o tetex.
Na internet há diversas apostilas que ensinam a usar latex, apesar de 
ser mais demorado de aprender, os resultados não se comparam com as 
alternativas MathType e similares.


Abraços.



=
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] Prova da IMO - Primeiro dia

[Domingos Jr.]

2. Seja a_1,a_2,... uma seqüência de inteiros com
infinitos termos positivos e negativos. Suponha que
para todo n inteiro positivo os números
a_1,a_2,...,a_n deixam n restos diferentes na divisão
por n.

Prove que todo inteiro aparece exatamente uma vez na
seqüência a_1,a_2,...

 

Achei este legal, note que o enunciado é levemente ambíguo, pois devemos 
dizer que há infinitos termos positivos e infinitos termos negativos, 
caso contrário, a sequüência dos números naturais positivos ordenados 
claramente satisfaz a propriedade e não contém nenhum negativo.


--- x ---

Por conveniência, chame de P a propriedade do enunciado
Seja S = {s_1, s_2, ...} uma seqüência que satisfaz P. Sem perda de 
generalidade, podemos supor que 0 está em S. Basta observar que S + a = 
{s_1 + a, s_2 + a, ...} também satisfaz P.


Vamos mostrar que, para todo n >= 0, existe N tal que todos os valores 
{-n, 1-n, ..., -1, 0, 1, ..., n} aparecem em {s_1, ..., s_N}.
Por hipótese, o caso n = 0 está ok. Vamos provar que se vale para n-1 
então vale para n.
Existe N' tal que {1-n, ..., 0, ..., n-1} aparecem em {s_1, ..., s_N'}. 
Tome N > N' > 2n e considere o único s_i em {s_1, ..., s_N} tal que s_i 
~ n (mod N), se s_i = n, paramos por aqui. Senão
   - caso s_i = A + n com N|A e A >= N temos, claramente que {s_1, ..., 
s_{A+n}} contém dois valores que são 0 mod A + n, a saber, 0 e s_i = A + 
n, o que não pode ocorrer.
   - caso s_i = n - A, com N|A e A > N, então |s_i| = A - n >= N e 
novamente {s_1, ..., s_{A-n}} contém dois 0 mod (A-n).
   - caso s_i = n - N: neste caso não temos como fazer a mesma 
asserção, mas note que N pode ser qualquer valor > N' e se cairmos 
sempre neste caso para qualquer escolha de N vamos exibir uma 
contradição* em S.

Para s_i ~ -n (mod N) o argumento é análogo ao acima.

* Suponha que para todo N > N' tenhamos n - N pertence a {s_1, ..., 
s_N}, um simples argumento de contagem mostra que há infinitos números 
negativos em S, mas não podemos ter infinitos números *positivos* em S.


Abraços.




=
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] Probabilidade - Ducks and hunters

[Domingos Jr.]

Tente usar esperança condicional.
Mais especificamente, condicione no número de patos, digamos Y.



Não tenho nem idéia de como começar, só entendi que o número de ducks 
num flock é Poisson(6). Alguém arrisca?



"Ten hunters are waiting for ducks to fly by. When a flock of ducks 
flies overhead, the hunters fire at the same time, but each chooses 
his target at random, independently of the others. If each hunter 
independently hits his target with probability 0.6, compute the 
expected number of ducks that are hit. Assume that the number of ducks 
in a flock is a Poisson random variable with mean 6." (A First Course 
in Probability)



Agradeço desde já.
[]s, Claudio Freitas
=
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] 25o Colóquio Brasileiro de Ma temática

[Domingos Jr.]

Rafael Castilho wrote:
  Ja mendei um email pra la. Um aluno de graduação que não seja
matemática será que aguenta bem?
 

Eu me formei em Computação... pra mim é difícil entender alguma coisa de 
sistemas dinâmicos, por exemplo, mas se você estudar um pouco de análise 
real, por exemplo, vai conseguir entender uma parte razoável do 
evento... dica: *não* assista tudo que tiver marcado no evento, seja 
seletivo.

[ ]'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] problema do caminhao

[Domingos Jr.]

Se você estudou teoria dos grafos, pode notar que o
problema pede para provar a existência de um caminho
(ciclo) hamiltoniano nesse grafo que é cúbico. Se não
me engano (pode ser que eu esteja enganado), todo
grafo conexo cúbico (todo vértice tem grau 3) admite
um ciclo hamiltoniano.
 

Isso é falso... até mesmo se nos restringirmos a grafos cúbicos 
bipartidos 3-conexos, veja
http://mathworld.wolfram.com/BicubicGraph.html

Há a seguinte conjectura em aberto
http://mathworld.wolfram.com/BarnettesConjecture.html
[ ]'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] 25o Colóquio Brasileiro de Matemática

[Domingos Jr.]

Rafael Castilho wrote:
   Alguém vai/pretende ir ao colóquio em julho? Preciso de algumas informações.
 

Eu vou... talvez seja melhor você procurar o pessoal do IMPA para tirar 
suas dúvidas.
=
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] Mais Isomorfismos

[Domingos Jr.]

Nicolau C. Saldanha wrote:
On Fri, May 06, 2005 at 04:12:43PM -0300, Claudio Buffara wrote:
 

Uma duvida: o grupo aditivo dos reais eh isomorfo ao grupo aditivo dos
complexos?
   

Sim, ambos são Q-espaços vetoriais de mesma dimensão (card(R)).
 

Deixa eu ver se eu advinho: não há nenhum isomorfismo explícito, apenas 
axioma da escolha :-(

[ ]'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
=

[obm-l] Um de combinatória.

[Domingos Jr.]

Seja ct : {0,1}^(2n) -> [n] definida como segue.
Para todo x != y em {0,1}^n temos ct(x, x) = n e ct(x, y) = min{j | x_j 
!= y_j}.

Prove que para todo A contido em {0,1}^n temos |ct(A, A)| >= lg |A|,
onde lg é o logaritmo na base 2.
Abraços.
=
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] A torre de hanói

[Domingos Jr.]

Fernando wrote:
São dados três suportes /A, B /e /C. /No suporte /A /estão encaixados /n/
discos cujos diâmetros, de baixo para cima, estão em ordem 
estritamente decrescente.

Mostre que é possível, com 2^n/ /– 1 movimentos, transferir todos os 
discos para o suporte

//
/B/, usando o suporte /C /como auxiliar, de modo que jamais, durante a 
operação, um disco

maior fique sobre um disco menor.
Desde jah grato, []'s

indução finita resolve o seu problema... pense um pouco, é fácil.
=
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)

[Domingos Jr.]

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] soma de termos

[Domingos Jr.]

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] RES: [obm-l] Prática: PG alternante?

[Domingos Jr.]

Guilherme wrote:
Ninguém sabe alguma aplicação prática ou situação onde seja útil uma PG
alternante? Será que só a definimos para tornar a definição de PG mais
geral?
Um abraço, 

Guilherme.
 

Nem sempre essas coisas tem uma aplicação imediata, às vezes são usadas 
como subproduto... essa preocupação com aplicações imediatas de teoria 
matemática realmente não faz muito sentido.
=
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] Probleminha bobo

[Domingos Jr.]

Alan Pellejero wrote:
*
é assim...duas máquinas fazem x parafusos em 2h40min, apenas uma, faz 
o mesmo serviço em 4 horas...calcule o tempo que a outra gasta para 
fazer tal serviço

*

<%20http://us.rd.yahoo.com/mail/br/taglines/*http://mail.yahoo.com.br/>

Por que você não fala como você tentou resolver o problem ou mostra 
alguma dúvida em particular? Os probleminhas bobos não deveriam encher a 
caixa postal dos outros se a lista é olímpica, não é mesmo?

Novamente, vamos direto para a mágica desses problemas! Alan, preste 
atenção... Dê NOMES às coisas... neste caso, temos 2 máquinas, por que 
não chamá-las de M1 e M2?
Vamos dizer que M1 faz o trabalho (x parafusos) em 4hs. Então M1 faz x/4 
parafusos por hora. Se M2 faz y parafusos/hora então
8/3 (x/4 + y) = x => y = x/8.
Se M2 faz x/8 parafusos/hora, ela leva 8 horas para fazer x parafusos. 
Viu como as coisas funcionam se você dá nome a elas?
=
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] Deprimente? O Apharteid Matemático

[Domingos Jr.]

Exagerada a sua idéia, não é mesmo? A lista é olímpica e mesmo assim 
problemas triviais tem sido postados a todo momento e isso tem sido 
tolerado com freqüência. A questão não é impedir que um infeliz que não 
tem nem carteira pra sentar (opa, como será que esse mesmo cara vai 
acessar a internet?) exponha suas dúvidas matemáticas. O fato é que este 
NÃO é o canal para esse tipo de dúvida; esta é uma lista de uma 
panelinha que está interessada em problemas matemáticos com um certo 
nível de dificuldade maior do que os enunciados nos tão bons livros 
didáticos usados pelas nossas tão boas escolas.

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] QuestÃo de potencia

[Domingos Jr.]

Robÿe9rio Alves wrote:
Qual o resultado da expressão 1^99 + 2^99 + 3^99 + 4^99 + 5^99 e prove 
que o resultado termina com um número divisível por 5.


<%20http://us.rd.yahoo.com/mail/br/taglines/*http://mail.yahoo.com.br/>

O pequeno teorema de Fermat nos diz que a^(p-1) ~ 1 (mod p) para todo p 
primo. Outro resultado interessante é que Z_p, os inteiros módulo p, 
formam um corpo e, portanto, cada elemento não-nulo de Z_p admite um 
inverso (único). Se a soma for a_1^99 + ... + a_k^99 (com nenhum a_j = 
0) podemos transformá-la em a_1^(100) * a_1^(-1) + ... + a_k^(100) * 
a_k^(-1).
Como para todo j temos a_j^4 = 1 pelo pequeno teorema de Fermat, a soma 
corresponde a a_1^(-1) + ... + a_k^(-1).

A expressão 1^99 + 2^99 + 3^99 + 4^99 + 5^99 em Z_5 é equivalente a 1^99 
+ 2^99 + 3^99 + 4^99 que é equivalente a 1^(-1) + 2^(-1)+ 3^(-1) + 
4^(-1). Como cada elemento tem um inverso único (poderia dizer 
explicitamente que eles são, em ordem, 1, 3, 2, 4), é claro que tal soma 
é 1 + 2 + 3 + 4 = 0.

Abraços.
=
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] 3 Problemas de Teoria dos Números [EM INGLÊS]

[Domingos Jr.]

Ok, novamente, com 4 reais positivos  

1)Sets of 4 positive numbers are made out of each other according
to the following rule: (a, b, c, d)  (ab, bc, cd, da).
Prove that in this (infinite) sequence (a, b, c, d) will
never appear again, except when a = b = c = d = 1.

Primeiramente, observe que se há um ciclo, o produto dos termos dessas 
quádruplas deve ser = 1.
Isso porque se f(.) é a função que calcula o produto das quádruplas e 
g(a, b, c, d) = (ab, bc, cd, da), então

f(a, b, c, d) = abcd
f(g(a, b, c, d)) = (abcd)^2
f(g^2(a, b, c, d)) = (abcd)^4
...
Com isso, só pode haver um ciclo se abcd = 1.
Observe também que se há um ciclo (a, b, c, d) -> (ab, bc, cd, da) -> 
... -> (a, b, c, d) então há um ciclo
(ab, bc, cd, da) -> ... -> (ab, bc, cd, da).

Como o produto abcd = 1, fazendo ab = x e bc = y, temos
(x, y, 1/x, 1/y) -> ... -> (x, y, 1/x, 1/y).
Observe que a transformação g sempre preserva a propriedade de que o 
terceiro elemento é o inverso do primeiro e o quarto é o inverso do 
segundo. Logo, para representar a quádrupla, basta olhar para as duas 
coordenadas e para a transformação

(x, y) -> (xy, y/x) -> (y^2, 1/x^2)
se iterarmos a transformação, obtemos
(1/x^4, 1/y^4) -> ... -> (1/y^8, x^8) -> ... -> (x^16, y^16)
Na seqüência infinita de transformação, obtemos todos os pares da forma 
(x^(16^k), y^(16^k)) para k >= 0.
Se (x, y) != (1, 1) então esses pares são todos distintos e, portanto, 
há infinitos pares distintos nas iterações da transformação, mas isso 
implica que a transformação não pode ser cíclica!

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] 3 Problemas de Teoria dos Números [EM INGLÊS]

[Domingos Jr.]

[EMAIL PROTECTED] wrote:
Domingos Jr. ([EMAIL PROTECTED]) escreveu:
 

Daniel S. Braz wrote:
   

1)Sets of 4 positive numbers are made out of each other according
to the following rule: (a, b, c, d)  (ab, bc, cd, da).
Prove that in this (infinite) sequence (a, b, c, d) will
never appear again, except when a = b = c = d = 1.
 

suponha, sem perda de generalidade, que b > 1.
temos que ab > a e bc > b, agora observe que uma coordenada nunca pode
diminuir, pois ela é sempre multiplicada por um termo >= 1, então (a, b,
c, d) nunca mais pode aparecer na seqüência.
   

Oi, Domingos
O enunciado fala em números positivos, não em inteiros positivos...
 

É verdade, considerando os elementos como reais o problema tem mais 
graça... mas isso deveria ser explícito.
Depois eu penso numa resposta!

[ ]'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] 3 Problemas de Teoria dos Números [EM INGLÊS]

[Domingos Jr.]

Daniel S. Braz wrote:
Pessoal,
Alguém poderia me dar uma dica na resolução desses aqui?
1)Sets of 4 positive numbers are made out of each other according
to the following rule: (a, b, c, d)  (ab, bc, cd, da).
Prove that in this (infinite) sequence (a, b, c, d) will
never appear again, except when a = b = c = d = 1. 
 

suponha, sem perda de generalidade, que b > 1.
temos que ab > a e bc > b, agora observe que uma coordenada nunca pode 
diminuir, pois ela é sempre multiplicada por um termo >= 1, então (a, b, 
c, d) nunca mais pode aparecer na seqüência.

2)Take a series of the numbers 1 and (-1) with a length
of 2k (k is natural). The next set is made by multiplying 
each number by the next one; the last is multiplied by the
first. Prove that eventually the set will contain only ones.
 

Tenho uma solução legal pra este...
Considere Z_2 = Z / (2Z), ou seja os inteiros módulo 2. Observe que {1, 
-1} com a operação de multiplicação é basicamente igual a {0, 1} com a 
operação de soma (tecnicamente falando, temos um isomorfismo levando 1 
-> 0 e -1 -> 1). Observe:
1*1 = 1  [0 + 0 = 0]
1*(-1) = -1 [0 + 1 = 1]
(-1)*(-1) = 0 [1 + 1 = 0]

Ok, agora a parte interessante. Seja m = 2^k e considere o anel
 R = Z_2[x] / 
A aritmetica desse anel é bem favorável ao que pretendemos fazer, basta 
observar que dado um polinômio p em R
p(x) = a_0 + a_1 x + ... + a_{m-1} x^{m-1}, a multiplicação de p por x 
resulta em
x p(x) = a_0 x + ... + a_{m-2} x^{m-1} + a_{m-1} (x^m + 1) + a_{m-1}, 
mas como x^m + 1 = 0 neste anel, temos
x p(x) = a_{m-1} + a_0x + ... + a_{m-2} x^{m-1}

Então, (x + 1)p(x) = (a_0 + a_{m-1}) + (a_1 + a_2)x + ... + (a_{m-2} + 
a_{m-1})x^{m-1}

Note que esses coeficientes são definidos de forma isomorfa ao enunciado 
do problema! Então, nesse nosso anel, queremos mostrar que repetindo o 
processo, chegaremos no polinômio identicamente nulo! Isso quer dizer 
que (x+1)^r p(x) = 0 para algum r...

Como os coeficientes estão em Z_2, (x+1)^2 = x^2 + 2x + 1 = x^2 + 1, 
sendo assim,
(x+1)^4 = [(x+1)^2]^2 = [x^2 + 1]^2 = x^4 + 2x^2 + 1 = x^4 + 1 e, por 
indução, segue
(x+1)^{2^s} = x^{2^s} + 1 para todo s >= 0, em particular,

(x+1)^m p(x) = (x^m + 1) p(x) = 0 p(x) = 0.
[ ]'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] Equação/combinatória

[Domingos Jr.]

fgb1 wrote:
Será alguem pode ajudar.
O número de maneiras diferentes de se escolher três números diferentes 
no conjunto{1,2,3,,,100} de modo que a soma desses três números seja 
igual a 100.

Existe uma fórmula bem manjada para o número de soluções não negativas 
para x_1 + ...  + x_k = n.
O seu caso segue disso, veja:
  - não podemos ter três números iguais somando 100
  - as soluções que incluem dois caras iguais são do tipo x + x + y = 
2x + y = 100, no entanto, como 100 é par, y = 2z e
   x + z = 50, então basta contar o número de soluções não-negativas de 
x + z = 50

Não se esqueça de que as fórmulas encontradas nos livros geralmente 
consideram como diferentes permutações da solução, ou seja 1 + 2 + 97 e 
1 + 97 + 2 são contados como diferentes...

[ ]'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] Equação

[Domingos Jr.]

x^4 + 2x^3 - 2x^2 - 6x - 2 = 0 ==>
Se você não errou no polinômio então as soluções são feias mesmo... eu 
olhei no Mathematica...
=
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] Parece fácil...mas não consegui...

[Domingos Jr.]

Alan Pellejero wrote:
Um trecho rodoviário deve ser dividido em lotes
iguais, quanto à quilometragem, a certo número de
empreiteiros  que se candidatarão para executar a
terraplanagem. Se há cinco empreiteiros a mais, cada
lote diminui de 20 km e se há seis empreiteiros a
menos, cada lote aumenta 57 km. Qual a extensão do
trecho em questão, em km?
 

o grande segredo desses problemas: seja X o tamanho (linear) de cada 
lote e seja K o número de empreiteiros
X*K = tamanho do trecho da rodovia
(X-20)*(K+5) = X*K ... (1)
(X+57)*(K-6) = X*K ... (2)

de (1) segue 5X - 20K = 100
de (2) segue -6X + 57K = 6*57
logo, 165K = 2310 => K = 14, X = 76
X*K = 14*76 = 1064
flw
=
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] Combinatória.

[Domingos Jr.]

f(n, p) = (p-2) f(n-1, p) + (p-1) f(n-2, p) para n >= 4.

Ok, agora só faltava matar o problema definitivamente com uma fórmula 
fechada. Estava relendo sobre o maquinário de funções geradoras e vi que 
dá pra atacar este problema com funções geradoras exponenciais. A minha 
referência é o livro do Herbert Wilf, generatingfunctionology (pode 
baixá-lo gratuitamente na internet).

Não vou introduzir os conceitos teóricos, mas a idéia é fixar o 
parâmetro p e olhar para a função geradora exp.
   F = soma_{n >= 0} f(n+4, p) x^n / n!

Uma simples regra mostra a partir da recorrência determinada, ie, f(n+2, 
p) = (p-2) f(n+1, p) + (p-1) f(n, p), temos
   F'' = (p-2) F' + (p-1) F.

Resolvendo a eq. diferencial acima, obtemos F = c_1 exp{-x} + c_2 
exp{(p-1)x}, onde c_1 e c_2 são constantes que não dependem de n (mas 
podem depender de p).
Tomando a série que representa o lado direito, vemos que
   F = soma_{n >= 0} [c_1 (-1)^n + c_2 (p-1)^n] x^n / n!
donde segue que
   f(n+4, p) = c_1 (-1)^n + c_2 (p-1)^n.

Verifiquei empiricamente que
   f(n, p) = (p-1)(-1)^n + (p-1)^n. (para n >= 2)
Para completar uma demonstração formal, basta verificar que para n = 2, 
temos
   f(2, p) = p(p-1) = (p-1)(-1)^2 + (p-1)^2 e que para n = 3
   f(3, p) = p(p-1)(p-2) = (p-1)(-1)^3 + (p-1)^3
e o resultado segue por indução pois o lado direito satisfaz a eq. de 
recorrência para n > 3.

Simplesmente lindo, não é?
Abraços.
=
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] Combinatória.

[Domingos Jr.]

Seja f(n, p) o número de maneiras de pintar Z_n (inteiros módulo n) com 
p cores de forma que i e i+1 não recebem a mesma cor.

Se o n é pequeno, faça as contas na mão mesmo...
Para n >= 4 já podemos usar uma recorrência:
Imagine que queremos colorir Z_{n+1} com p cores da maneira enunciada. 
Essa coloração vai induzir uma p-coloração de Z_n (basta considerar as 
cores dadas aos elementos 0, ..., n-1). Há duas possibilidades:
- a coloração induzida é da maneira enunciada [sabemos que há f(n, p) 
colorações dessa forma]
- a coloração induzida é tal que n-1 e 0 tem a mesma cor, porém cor(0) 
!= cor(1) != cor(2) != ... != cor(n-2) != cor(n-1) = cor(0), mas então a 
coloração induzida em 0, ..., n-2 é  da maneira enunciada para Z_{n-2}, 
mas há f(n-1, p) tais colorações.

No primeiro caso, a cor de n pode ser uma das p-2 cores diferentes de 
cor(0), cor(n-1). No segundo caso, temos de evitar apenas cor(0) e 
portanto há p-1 cores possíveis.

f(n, p) = (p-2) f(n-1, p) + (p-1) f(n-2, p) para n >= 4.
Abraços,
Domingos.
Olá a todos.
Como sou novo na lista, não sei se o problema que apresentarei já foi
publicado aqui, mas se alguém puder ajudar ficarei muito grato..
"N casas idênticas estão dispostas ao longo de uma praça circular. Um
pintor dispôe de p cores diferentes para pintar as casas. De quantos
modos isso pode ser feito se casas adjacentes não podem ter a mesma
cor?"
Abraços
Paulo Cesar
=
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] En: [obm-l] Tangência...

[Domingos Jr.]

Vinícius Meireles Aleixo wrote:
Eu gostaria de saber qual é o conceito rigoroso de reta tangente a uma
   

curva
 

qualquer (circunferência, elipse, hipérbole, parábola, etc...)
   

A tangente é a linha ou superfície que toca outra linha ou superfície em um
só ponto.
Cara, acho essa definição bem esclarecedora e concisa.Caso alguém tenha + a
dizer...
 

Pense na sua curva como uma rodovia e um carro fazendo a curva... se 
você simplesmente trocar um pedaço da rodovia por gelo, o carro vai 
passar reto pela curva e sair pela tangente.
A definição formal da tangente num ponto envolve o conceito de derivada. 
Leia qualquer livro de cálculo.

[ ]'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] 3 problemas em aberto

[Domingos Jr.]

3) Dado um tabuleiro quadriculado de 4 x 4, com cada casa pintada de uma cor
distinta, deseja-se cortá-lo em dois pedaços de igual área mediante um só
corte, que siga os lados das casas do tabuleiro. De quantas maneiras se pode
fazer isto?
 

não sei se isso é equivalente ao número de soluções de
x_1 + ... + x_4 = 8
sujeito a  0 <= x_i <= 4
onde x_i seria o número de quadrados abaixo do corte na i-ésima coluna.
a minha dúvida é em relação ao "um só corte"... ie, x_1 > 0 e x_2 = 0 é 
um corte só? na minha opinião, não deveria ser, mas x_1 = 0 e 1 < x_i < 
x_4 para i > 1 sim.

Obs. Os pedaços em que se divide o tabuleiro devem ser peças inteiras; não
devem ser desconectados pelo corte.
Resp: 70 maneiras
 

=
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] Idades

[Domingos Jr.]

Com a tecnologia de hj, o pai pode estar morto!
Esta eh apenas uma das solucoes possiveis (talvez a mais conservadora).
Segundo o Kama Sutra (do qual nao achei nehum exemplar na biblioteca 
do IMPA), existem centenas de solucoes diferentes para a localizacao 
do pai...

=
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] Um problema de Probabilidade

[Domingos Jr.]

Este problema é do The Probabilistic Method - N. Alon e J. Spencer. Eu 
passei pra uma galera e nem eu nem a galera conseguiu resolver...
O máximo que eu consegui foi provar o resultado para uma constante um 
pouco maior que 1 usando algumas cotas exponenciais.

[ ]'s
Olá!
Tentem fazer este daqui:
Sejam n >= 1 e a_1, ..., a_n reais tais que a_1^2 + ... + a_n^2 = 1.
Sejam e_1, ..., e_n elementos de {-1, 1} escolhidos aleatoriamente de 
forma uniforme e indendente.
Mostre que Pr[|e_1*a_1 + ... + e_n*a_n| <= 1] >= c para uma constante 
absoluta c > 0.

Obs: note que c não depende de n e a escolha dos a_i's é arbitrária.
Eu consigo provar que Pr[|e_1*a_1 + ... + e_n*a_n| <= 1] > 0 para todo 
n >= 1 e toda escolha de a_i's, mas a asserção é mais forte que isso.

[ ]'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] Traco Zero

[Domingos Jr.]

Claudio Buffara wrote:
Mais um problema em aberto na lista obm-l. Eh uma especie de reciproca do
famoso problema do IME de se provar que AB - BA = I eh impossivel (A, B e I:
matrizes quadradas).
Prove que se M eh uma matriz quadrada entao:
traco(M) = 0 <==> existem matrizes quadradas A e B tais que M = AB - BA.
 

Oi!
É comum na literatura o termo "commutator" (comutador seria a minha 
tradução) para
[A, B] := AB - BA

Eu vi como se prova o seguinte resultado
S = {M | M é n x n, tr(M) = 0} = span{[A, B] | A, B são n x n}
Defina E_{ij} como a matriz cuja coordenada (i, j) é 1 e todas as demais 
são 0.
Observe que para i != j, E_{ij} = [E_{ik}, E_{kj}] para qualquer 1 <= k 
<= n.
Também vemos que E_{ii} - E_{jj} = [E_{ij}, E_{ji}].

Qualquer matriz de S pode ser expressa como combinação linear das 
matrizes E_{ij} (i != j) e das matrizes E_{ii} - E_{jj}.
Isso é simples de se verificar. Se M está em S então para i != j podemos 
tomar M(i, j) E_{ij} na combinação linear. Para as coordenadas da 
diagonal, temos de usar o fato da matriz ter traço 0. Seja i o índice 
tal que |M(i, i)| > 0 seja mínimo e seja j tal que sinal(M(j, j)) = 
-sinal(M(i, i)). Adicione M(i, i) (E_{ii} - E_{jj}) à combinação linear. 
Repita o procedimento até que obter M.

O teorema que se pede é mais forte que isso... eu não consegui 
argumentar que essa combinação linear obtida pode fornecer diretamente 
um único commutator que representa a matriz M.

[ ]'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] probabilidade - inspecao de um lote

[Domingos Jr.]

Sandra wrote:
Oi
Eu estou tentando resolver o seguinte problema, mas nao consigo chegar na resposta que 
foi dada como certa. Estou chegando a expressoes complicadas e nao consigo 
"fechar" uma formula final. Gostaria de alguma dica.
Em um lote de n pecas, sabe-se que m sao defeituosas. Se o lote for inspecionado 
aleatoriamente, qual a probabilidade de que a peca inspecionada em k_gesimo lugar 
(k>=m) seja a ultima peca defeituosa do lote? (estou, eh claro, assumindo que 
nao hah reposicao de pecas).
A resposta que me foi dada como correta eh p(k) = Binomial(m-1, 
k-1)/Binomial(n,k)
Sandra
 

A idéia é assim: você tem Binomial(m-1, k-1) maneiras de escolher k-1 
peças defeituosas nas m - 1 primeiras escolhas. Na k-ésima escolha você 
só pode escolher 1 única peça defeituosa, então, como o total de 
maneiras de escolher k dentre n é Binomial(n,k), a resposta segue.
=
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] Questão de conjuntos

[Domingos Jr.]

Thiago wrote:
Infelizmente não posso resolver usando analise combinatoria pois é para uma
turma de 8ª série.
 

Minha sugestão seria demonstrar da seguinte maneira:
*** Receita de Bolo ***
De quantas maneiras podemos p elementos de um n-conjuntos?
Disponha n caixas numeradas e permute os n elementos nas caixas de todas 
as maneiras possíveis (mostre que isso pode ser feito de n! maneiras).
Escolha sempre o conteúdo das caixas 1, 2, ..., p.
Agora vamos contar quantas vezes o mesmo conjunto de p elementos foi 
contado. Para cada permutação de um p-conjunto fixado S nas caixas de 1 
a p, contamos uma vez S. Agora resta saber quantas vezes aparece cada 
permutação de S nas caixas de 1 a p. Há p! maneiras de uma permutação 
aparecer nas caixas, nas caixas p+1, ..., n temos (n-p)! possibilidades. 
Sendo assim, S foi contado p! (n-p)! vezes. Como o total contado foi n!, 
temos a fórmula

n! / [p!(n-p)!]
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] Probabilidade

[Domingos Jr.]

Ok, vamos fazer continhas...
A função de densidade das variáveis exponenciais em questão é
f(x) = a e^{-a x}, onde f : [0, oo) -> IR^+
Então, temos Pr[X >= 2y] = 1 - Pr[X <= 2y]. Por definição
Pr[X <= 2y] = Integral_{0, 2y} f(x) dx = 1 - e^{-a (2y)}, logo
Pr[X >= 2y] = e^{-a (2y)}
Substituindo na nossa integral
Pr[A] = Integral_{0, oo} Pr[X >= 2y] f(y) dy =
   Integral_{0, oo}  e^{-a (2y)} a e^{-a y} dy =
   Integral_{0, oo} a e^{-3ay} dy
Ok, agora basta calcular a integral acima... Você pode tentar fazer isso 
na unha ou usar um truque... Como f é função de densidade, sabemos que
Integral_{0, oo} c e^{-cy} dy = 1 para toda constante c > 0. Então, 
chame c = 3a e observe que

Pr[A] = 1/3 Integral_{0, oo} c e^{-cy} dy = (1/3) * 1  = 1/3.
Abraços,
Domingos.
O meu problema tem sido exatamente calcular P(X >= 2y). De qualquer forma,
consigo a resposta a/3 (assumi que os parâmetros sao iguais pras duas
distribuições, já que o problema deixa isso meio implícito). Mas a resposta
certa é 1/3.
O que poso fazer?
Grato,
Henrique.

 

=
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] Probabilidade

[Domingos Jr.]

Henrique Patrício Sant'Anna Branco wrote:
Alguém pode ajudar nesses dois?
O número dois até consigo resolver a primeira parte (achar a distribuição de
X, geométrica), mas não consigo montar a segunda parte.
1. Suponha que os tempos que dois estudantes levam para resolver um problema
sao independentes e se distribuem exponencialmente com parâmetro a.
Determine a probabilidade de que o primeiro estudante necessite pelo menos
do dobro do tempo gasto pelo segundo estudante para resolver o problema.
 

Acho que esse é só uma questão de expressar a probabilidade em termos de 
probab. condicional...

Condicione no tempo que o segundo estudante leva para resolver o problema.
Seja A o evento desejado (estudante 1 leva pelo menos o dobro do tempo 
do estudante 2).
Seja X a variável aleatória exponencial de param. a correspondente ao 1º 
estudande e Y a do segundo.
Seja f a função densidade de uma var. exp. de parâmetro a
Pr[A] = Integral_{0, +oo} Pr[X >= 2y | Y = y]*f(y) dy = Integral_{0, 
+oo} Pr[X >= 2y]*f(y) dy já que X e Y são independentes.

Abraços.
=
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] polinômio divisor de zero

[Domingos Jr.]

[EMAIL PROTECTED] wrote:
Alguém pode ajudar?
Seja R um anel comutativo. Se f(X) = a_0 + a_1*X + ... + a_m*X^m em R[X] é
um divisor de zero, demonstrar que existe um elemento b <> 0 em R tal que
b*a_i = 0 para i = 0, 1, ..., m.
 

Consegui um resultado que talvez nos leve a resposta, mas estou sem 
tempo pra tentar fechar (...sempre assim!).

Sejam p(x) e q(x) em R[x] tais que pq = 0. Chame d(f) = grau(f). Suponha que
d(p), d(q) > 0 e que para todos p', q' não-nulos em R[x] com d(p') < 
d(p) e d(q') < d(q) tenhamos
p' q !=0 e p q' != 0.

Seja p(x) = a_0 + ... + a_n x^n e q(x) = b_0 + ... + b_m x^m
Pelo raciocínio que eu empreguei na outra mensagem, verificamos que a_i 
b_0^{i+1} = 0 para todo i.
Se b_0^k != 0 para todo k então b_0^{n+1} p = 0, o que contraria a hipótese.
Seja k o maior inteiro tal que b_0^k != 0. Se b_0^k q = 0 então também 
caímos em contradição, mas
b_0^k q = b_0^{k+1} + b_0^k b_1 x + ... + b_0^k b_m x^m = x[b_0^k b_1 + 
... + b_0^k b_m x^{m-1}].

Chame r(x) = b_0^k b_1 + ... + b_0^k b_m x^{m-1}, então
p q = 0 => p (b_0^k q) = 0 => p (x r) = 0 => x (p r) = 0 => p r = 0 => 
absurdo pois d(r) < d(q)!

Isso mostra que a suposição original nunca pode ser verdadeira. Boa sorte!
[ ]'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] polinômio divisor de zero

[Domingos Jr.]

[EMAIL PROTECTED] wrote:
O problema é que podemos ter b_i^k = 0, não?
 

tem razão... ainda não sei resolver o problema
=
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] polinômio divisor de zero

[Domingos Jr.]

[EMAIL PROTECTED] wrote:
Alguém pode ajudar?
Seja R um anel comutativo. Se f(X) = a_0 + a_1*X + ... + a_m*X^m em R[X] é
um divisor de zero, demonstrar que existe um elemento b <> 0 em R tal que
b*a_i = 0 para i = 0, 1, ..., m.
 

seja b_0 + ... + b_n X^n tal que
(1)... (a_0 + a_1*X + ... + a_m*X^m)(b_0 + ... + b_n X^n) = 0
então a_0*b_0 = 0
a_0 b_1 + a_1 b_0 = 0, mas
a_0 b_0 b_1 + a_1 b_0^2 = a_1 b_0^2 = 0
a_0 b_2 + a_1 b_1 + a_2 b_0 = 0, mas
a_0 b_0^2 b_2 + a_1 b_0^2 b_1 + a_2 b_0^3 = 0 => a_2 b_0^3 = 0
temos que b_0^3 multiplicado por a_0, a_1 e a_2 resulta em 0.
...
E por aí vai, entendeu? A idéia é trabalhar com os polinômios nos a_i's e b_i's 
respectivos a cada coeficiente do produto (1), multiplicando esses polinômios por uma 
potência adequada de b_0 cancelamos todos exceto o termo que inclue um "novo" 
a_i. Claro que uma prova formal exige o uso de indução finita, mas isso eu deixo com você.
[ ]'s 

PS: tem uma pequena falha de argumentação, tente advinhar qual é... vou 
dar um espaço pra você corrigir minha prova...








notou que b_0 pode ser 0?
bem, nesse caso tome o primeiro b_i não nulo e aplique a mesma idéia.
=
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

[Domingos Jr.]

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

[Domingos Jr.]

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

[Domingos Jr.]

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] 2 teor nº

[Domingos Jr.]

Kellem :-) 100% SeJ wrote:
oi gente!
Alguém me ajuda?
1) a^b - 1 é primo ==> a=2 e b é primo
 

se b = 2k com k > 1 então
a^b - 1 = (a^k - 1)(a^k + 1) com a^k - 1, a^k + 1 > 1, logo a^b - 1 não 
é primo.
a^b - 1 = (a-1)(a^{b-1} + a^{b-2} + ... + a + 1). Então, se a > 2, a^b - 
1 não é primo, o que prova que a = 2.

Se 2^b - 1 é primo e b = j*k com j, k > 1 então
2^b - 1 = (2^j -1)(2^{j (k-1)} + 2^{j (k-2)} + ... + 2^j + 1) e 2^b - 1 
não é primo.

concluímos que "a^b - 1 é primo => a=2 e b é primo"
[ ]'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] Cardinalidade

[Domingos Jr.]

Artur Costa Steiner wrote:
Boa tarde,
Eu ainda nao consegui demonstrar o seguinte, talvez alguem tenha uma sacada.
Seja A um conjunto infinito e f uma injecao de A sobre B. Se o conjunto B -
f(A) for, no maximo, enumeravel, entao A e B sao equivalentes.
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
=
 

Você quer mostrar que card(A) = card(B), certo?
Esse tipo de problema passa longe do que eu costumo fazer, mas vou tentar...
Defina A' como uma cópia de A.
card(A) = card(A união A') já que A é infinito
Sabemos que card(A) <= card(B) pois existe uma injeção de A em B.
Defina g: B -> A união A' da forma a seguir.
Para todo f(x) em f(A), g(f(x)) = x e
como card(B - f(A)) <= card(A), existe uma injeção de B - f(A) em A.
Seja h tal injeção, defina g(y) = h(y)' (onde h(y)' é a cópia de h(y) em A')
para todo y em B - f(A). É simples ver que g é uma injeção e, portanto
card(A) <= card(B) <= card(A união A') = card(A)
[ ]'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] série de inversos curiosa

[Domingos Jr.]

[EMAIL PROTECTED] wrote:
Um probleminha para começar o ano:
Considere todos os números naturais cuja representação decimal não possua
nenhum dígito 9. Prove que a soma dos inversos desses números converge.
 

Oi,
Suponha que n_1, ..., n_r são todos os números com exatamente k dígitos 
e sem dígito 9.
Defina T_k = 1/n_1 + ... + 1/n_r. É evidente que a soma que estamos 
considerando é S = T_1 + T_2 + ...
Sendo assim, vamos nos preocupar com a razão T_{k+1}/T_k.

Observe que todo número com k+1 dígitos sem que nenhum deles é 9 é 
composto de k dígitos iniciais que formam um número de k dígitos sem 9 e 
um dígito final que pode ser 0~8. Isso nos diz que T_{k+1} = [1/10n_1 + 
... + 1/10n_r] + [1/(10n_1 + 1) + ... + 1/(10n_r + 1)] + ... + [1/(10n_1 
+ 8) + ... + 1/(10n_r + 8)] < 9 [1/10n_1 + ... + 1/10n_r] = 9/10 T_k.

Observe que S < T_1 [1 + 9/10 + (9/10)^2 + ... ] = 10 T_1.
Isso mostra que a série é limitada superiormente. Como a série é 
crescente, sabemos que o valor da soma converge.

[ ]'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] Determinante

[Domingos Jr.]

Claudio Buffara wrote:
Alguem tem uma solucao "esperta" pra esse aqui?
A matriz A = (a_ij) 2005x2005 eh tal que a_ij = 0 se i+j eh par e a_ij = 1
se i+j eh impar. 
I_2005 eh a matriz identidade de ordem 2005.
Calcule det(A + I_2005).

[]s,
Claudio.
talvez!
Seja a o vetor com 2005 coordenadas da forma a = (0, 1, 0, 1, ..., 0) e 
b também com 2005 coordenadas da forma b = (1, 0, 1, 0, ..., 1).
Note que a matriz A é formada pelas colunas a, b na seqüência [a b a b 
... a].

Sabemos que det(A - I) é o produto dos auto-valores de A + I. Mas se d é 
auto-valor de A + I então d - 1 é auto-valor de A, então, se soubermos 
todos os auto-valores de A então sabemos cacular o determinante pedido.

Observe que para qualquer vetor x, Ax é uma combinação linear de a e b. 
Suponha
Ax = d x, devem existir r e s tais que
x = r a + s b, ou seja, todo auto-vetor x é combinação linear de a e b.

Ademais, observe que
Aa = 1002 b e
Ab = 1003 a, logo se
A(r a + s b) = d(r a + s b) então
d(r a + s b) = 1002r b + 1003s a
Normalmente não podemos fazer o que vamos fazer, mas como a e b tem 
coordenadas não-nulas complementares, temos
d*r = 1003s
d*s = 1002r.
Manipulando um pouco, obtemos 1002 r^2 = 1003 s^2, como 1002 e 1003 são 
primos entre si só pode haver as seguintes soluções:
r = +/- raiz(1003)
s = +/- raiz(1002).
Temos que d pode ser raiz(1003*1002) ou -raiz(1003*1002). Esses são os 
dois únicos auto-valores não nulos de A. Pelo que constatamos logo no 
começo, os auto-valores de A + I são 1 + raiz(1003*1002), 1 - 
raiz(1003*1002) e 1 com multiplicidade 2003.

Agora é só calcular o produto... Aqui eu vou generalizar o resultado e 
falar de uma matriz de tamanho 2m + 1. Neste caso, o determinante é
[1 + raiz(m*(m+1))] [1 - raiz(m*(m+1))] = 1 - m*(m+1) = 1 - m - m^2.

[ ]'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] lim x->+oo sinx/x

[Domingos Jr.]

note que |sen x| <= 1 para todo x.
se x -> +oo, qual você acha que deve ser o limite?
lim x->+oo sinx/x
 
quando eh esse limite.
quando x tende a zero é um, mas e esse?
 
 

__
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: En: [obm-l] polinomio...completa!!!

[Domingos Jr.]

vinicius wrote:
- Mensagem Original 
De: [EMAIL PROTECTED]
Para: "[EMAIL PROTECTED]" <[EMAIL PROTECTED]>
Assunto: [obm-l] polinomio...
Data: 09/12/04 02:24
Alguem, pode por favor, me ajudar a resolver:
Para quais valores de "a" de "n" o polinomio:
x^n - ax^(n-1) + ax - 1
   

é divisivel por (x-1)^2
 

ok, seu polinômio tem que ter 1 como raiz dupla, mas isso significa que 
o polinômio e a sua derivada tem 1 como raiz.
a prova disso é bem simples g(x) = (x - r)^2 h(x) => g'(x) = 2(x- r) 
h(x) + (x - r)^2 h'(x) => g(r) = g'(r) = 0.

[ ]'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] numero primo?

[Domingos Jr.]

não tem uma regra geral que vai funcionar para qualquer exemplo que você 
der, mas dá para fazer uns chutes...

vamos tentar divisibilidade pelo próximo primo que poderia dividir esse 
número, ou seja, 19
se você trocar 17 por 19-2, então bastaria verificar a divisibilidade de

2x3x5x7x11x13x(-2) + 1
fazendo a mesma coisa para 13 e 11, basta testar
2x3x5x7x(-8)x(-6)x(-2) + 1
esse número é mais fácil de calcular, dá -20160 + 1 = -20159
e 20159 é múltiplo de 19.
existem vários métodos para determinar se um número é primo ou não que 
não dependem da fatoração do mesmo (aliás, se você tentar fatorar 
números grandes para ver se eles são primos, você não conseguirá chegar 
a uma resposta antes do universo congelar).

[ ]'s
gostaria de saber se esse numero é primo, se nao, gostaria de saber
alguma fatoracao pra achar ele
2x3x5x7x11x13x17 + 1

   Grato, Renato Lira.
=
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] Sequencia densa em f(I)

[Domingos Jr.]

claudio.buffara wrote:
Um esclarecimento: apesar de eu ter participado das discussões sobre 
esse problema e ser, de fato, um participante ativo dessa lista, não 
sou profundo conhecedor de coisa alguma. De matemática, então, não sou 
nem um conhecedor raso. Pra você ter uma idéia, não consegui nem ser 
aceito no mestrado do IME-USP. Mas admito que matemática é um 
passatempo fascinante (se você achou essa opinião esdrúxula é porque 
está na lista de discussão errada) e dos mais baratos, diga-se de 
passagem.
 
Quem mandou não querer entrar no mestrado em computação?! hehehe... você 
não vai voltar a assistir matérias como ouvinte? Acho que no semestre 
que vem vai ter umas matérias interessantes, se você tiver interessado.

[ ]'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
=

[obm-l] Re: [obm-l] OBM2004 - NIVEL U - Problema 2 - Uma variação

[Domingos Jr.]

Quase todo conjunto que aparece em aplicações é Lebesgue mensurável.
Por outro lado, o conjunto dos borelianos tem cardinalidade c (a de R)
e o conjunto de todos os subconjuntos de R tem cardinalidade 2^c
então em um sentido mais abstrato quase todo conjunto é não mensurável.
 

hoje eu imagino que esse tipo de fato não cause espanto, mas é curioso 
que conjuntos que são difíceis de se imaginar sejam tão abundantes.

 

e quanto ao problema 5 da OBM? eu acho que consegui demonstrar que o 
limite ficava entre duas constantes para qualquer valor de m... talvez 
eu tenha errado um pouco na minha estimativa por que o limite ficou 
entre 2 e 4 e eu acho que na verdade 2 é o máximo que o limite assume 
(será que 2 é sempre o limite?!), mas isso deve ter sido algum erro de 
conta mesmo.
   

O do Arnalde e Bernaldo? O limite sempre existe mas o valor depende de m.
A resposta é 2 se m for par, senão o valor é outro, próximo de 2,
tendendo a 2 quando m tende a infinito mas diferente de 2.
 

legal, nessa talvez eu ganhe uns pontos... eu basicamente provei um lema 
que afirmava que para m fixado, para todo N_0 positivo, se ambos os 
jogadores estivessem utilizando uma estratégia ótima, então o vencedor é 
determinado por N_0 (o primeiro ou o segundo a jogar).

a partir daí deu pra estabelecer a relação entre os elementos de um 
conjunto e de outro, mas não insisti muito em fazer uma análise fina do 
limite |A_n|/|B_n| e fiquei apenas com cotas.

a propósito, o problema 3 admite algo mais geral: as matrizes não 
precisam ser não-singulares, basta terem posto 2 (essa condição é bem 
mínima já que o segundo valor singular da matriz deve ser não-nulo para 
que a dilatação esteja bem definida).

[ ]'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
=

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] OBM2004 - NIVEL U - Problema 2 - Uma variação

[Domingos Jr.]

Nicolau C. Saldanha wrote:
On Wed, Oct 20, 2004 at 06:46:41PM -0300, Domingos Jr. wrote:
 

 

Não entendi. Se f é uma função bem comportada no IR^2, porque 
ela não seria integrável? Pelo pouco que eu li, qualquer 
função contínua nos reais (usando a medida de Lebesgue) é 
integravel.
 

   

Em que sentido f seria bem comportada? Ela certamente não é contínua.
 

Depois de falar com um professor meu do IME eu acho que entendi no que 
eu errei. Já vou avisando para ter paciência já que meus conhecimentos 
sobre integral de Lebesgue tem medida nula...

Inicialmente eu pensei em definir f(x, y) para todo R^2. Algo como f(x, 
y) = exp{-x^2 - y^2} que é positiva para todo x, y e tem volume finito 
(por sinal, o volume sobre todo R^2 é PI!). Sem dúvida f é bem 
comportada. A idéia então era integrar uma função bem comportada num 
conjunto muito mal comportado! Eu achava que com integrais de Lebesgue 
isso seria sempre possível, mas talvez meu argumento falhe pois só 
depois que esse meu professor falou que eu percebi que é necessario que 
o conjunto seja mensurável para que eu aplique a minha idéia. Parece 
então que se A é mensurável então A não pode satisfazer as 
características enunciadas e isso pode ser demonstrado pelo meu 
argumento da integral, certo?
   

Correto: o seu argumento prova que não existe
um conjunto A Lebesgue-mensurável satisfazendo
as condições do problema.
 

para concluir, então... existem mais conjuntos Lebesgue-mensuráveis do 
que conjuntos não-Lebesgue-mensuráveis?

e quanto ao problema 5 da OBM? eu acho que consegui demonstrar que o 
limite ficava entre duas constantes para qualquer valor de m... talvez 
eu tenha errado um pouco na minha estimativa por que o limite ficou 
entre 2 e 4 e eu acho que na verdade 2 é o máximo que o limite assume 
(será que 2 é sempre o limite?!), mas isso deve ter sido algum erro de 
conta mesmo.

Exatamente: não faz sentido integrar *nenhuma* função sobre um domínio
que não seja mensurável.
[]s, N.
ok!
[ ]'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
=

[obm-l] Re: [obm-l] Re: [obm-l] OBM2004 - NIVEL U - Problema 2 - Uma variação

[Domingos Jr.]

Não entendi. Se f é uma função bem comportada no IR^2, porque 
ela não seria integrável? Pelo pouco que eu li, qualquer 
função contínua nos reais (usando a medida de Lebesgue) é 
integravel.
   

Em que sentido f seria bem comportada? Ela certamente não é contínua.
 

Depois de falar com um professor meu do IME eu acho que entendi no que 
eu errei. Já vou avisando para ter paciência já que meus conhecimentos 
sobre integral de Lebesgue tem medida nula...

Inicialmente eu pensei em definir f(x, y) para todo R^2. Algo como f(x, 
y) = exp{-x^2 - y^2} que é positiva para todo x, y e tem volume finito 
(por sinal, o volume sobre todo R^2 é PI!). Sem dúvida f é bem 
comportada. A idéia então era integrar uma função bem comportada num 
conjunto muito mal comportado! Eu achava que com integrais de Lebesgue 
isso seria sempre possível, mas talvez meu argumento falhe pois só 
depois que esse meu professor falou que eu percebi que é necessario que 
o conjunto seja mensurável para que eu aplique a minha idéia. Parece 
então que se A é mensurável então A não pode satisfazer as 
características enunciadas e isso pode ser demonstrado pelo meu 
argumento da integral, certo?


Vou ser mais específico na minha fonte de leitura... eu li a 
descrição do teorema de Tonelli em
http://planetmath.org/encyclopedia/TonellisTheorem.html
   

Nas hipóteses do teorema (no site que você indicou) aparece
que a função deve estar em L^+(X x Y). Esta hipótese não vale
em geral para a função que você construiu.
 

O problema é que não podemos afirmar que A é mensurável e portanto f 
pode ser bem comportada no R^2 mas não integrável em A, certo?

Abraços.
=
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] OBM2004 - NIVEL U - Problema 2 - Uma variação

[Domingos Jr.]

Nicolau, gostaria de seus comentários (essa foi minha sol. na prova).
Seja f(x, y) uma função com f(x, y) > 0 para todo x,y e tal que
Integral_{IR^2} f(x, y) dx dy = Z, 0 < Z < +oo, ou seja, o volume 
formado por f e o plano xy é Z.

Vamos calcular a integral (Lebesgue) Integral_{A} f(x, y) dx dy.
Podemos aplicar a regra de Fubini nessa integral (pelo menos é o que eu 
li). Ou seja, se integrarmos primeiro na direção do eixo x e depois na 
do eixo y ou vice-versa, o resultado deve ser o mesmo.
Mas isso nos garante uma contradição, já que se considerarmos um x 
qualquer fixado, a integral em todo y real deve dar zero já que ele é um 
conjunto com medida nula (enumerável na sua modificação e finito no 
enunciado original), ou seja, a integral deve ser 0. Por outro lado, 
fixando y, temos apenas um conjunto de pontos com medida nula o qual não 
devemos considerar na integração, mas isso garante que essa integral é 
positiva (já que f(x, y) > 0), mas então, olhando por esse lado, a 
integral é estritamente positiva (de fato, seu valor é Z).

Acertei?
[ ]'s
Gostaria de convidar a lista a considerar a seguinte variação
do problema 2 do nível U da prova de sábado.
Determine se existe um subconjunto A de R^2 tal que:
(i) para todo x em R, {y em R | (x,y) pertence a A} é enumerável;
(ii) para todo y em R, {x em R | (x,y) não pertence a A} é enumerável.
[]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
=
 

=
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] 2 pares de luvas e 3 pacientes

[Domingos Jr.]

hahaha, a resposta que eu tenho NÃO é uma prática recomendável ao 
problema original!

coloque uma err... luva na primeira cirurgia
tire a luva e coloque a segunda na segunda cirurgia.
não retire a luva e coloque por cima a primeira luva usada do avesso (o 
lado de dentro estava nas mãos do cirurgião, que, por hip. não deve 
estar contaminado, certo?).

[ ]'s
Um cirurgiao dispoe de apenas 2 pares de luvas cirurgicas mas precisa operar
3 pacientes. Como ele deve fazer para que ninguem, nem mesmo ele, seja
contaminado.
OBS: O problema original era com 2 camisinhas, mas eu resolvi mudar porque
alguem poderia se ofender...
[]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] postos de gasolina

[Domingos Jr.]

No lugar do trecho e dos dois postos de gasolina, colocamos um único 
posto, cuja quantidade de gasolina é x_k + x_{k-1} - d_k > 0. 

opa! é x_k + x_{k+1} - d_k
falha minha!
=
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] postos de gasolina

[Domingos Jr.]

Gostei! Muito interessante o problema.
Em vez de contar a quantidade de litros que cada posto tem, vamos contar 
a distância que o total de gasolina do posto permite o carro andar.
Sejam {1, ..., n} (mod n) os postos e x_i > 0 é a "quantidade" de 
gasolina (no sentido acima) no posto i.

Sabemos por hipótese que x_1 + ... + x_n = C, onde C é o comprimento do 
circuito.

Seja d_i a distância do posto i ao posto i+1 (mod n, ou seja d_n é a 
dist. de x_n a x_1), claramente
d_1 + ... + d_k = C.
Seja k o posto com maior valor de x_k/d_k.
Claramente x_k/d_k >= 1, caso contrário, x_i < d_i para todo i e isso é 
uma contradição.

Agora a prova segue por indução!
Forme um novo circuito sem o trecho entre os postos k e k + 1.
No lugar do trecho e dos dois postos de gasolina, colocamos um único 
posto, cuja quantidade de gasolina é x_k + x_{k-1} - d_k > 0.
Note que o novo circuito formado tem tamanho C - d_k, a capacidade dos 
postos é C - d_k e a soma das distâncias entre postos consecutivos é C - 
d_k. Aplique a hip. indutiva e veja que se é possível percorrer o 
circuito formado então o circuito original também pode ser percorrido.

O caso base é n = 1, que é trivial!
Olá pessoal !
Em uma pista circular há postos de gasolina, e o total de 
gasolinaquehá nos postos é exatamente o suficiente para um carro dar 
uma volta.Prove que existe um posto de onde um carro com o tanque 
inicialmente vazio pode partir e conseguir dar uma volta completa na 
pista (parando para reabastecer nos postos).




=
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] Nao-quadrados perfeitos

[Domingos Jr.]

3^(2r) = (x - 2^r)(x + 2^r)
como 3 é primo, devemos ter, para algum inteiro s
x - 2^r = 3^s   (1)
x + 2^r = 3^(2r - s)  (2)
(1) + (2) : 2x = 3^s + 3^(2r - s)
note que s < 2r - s e, 
   


Até aqui eu saquei, tem como explicar essa parte entre 
aspas abaixo melhor ?

"portanto, 3^s divide x
 

3^s divide 3^s + 3^(2r - s), pois s < 2r - s, então, como divide o lado 
direito, divide o lado esquerdo (que é 2x), mas 3 é primo e então 3^s 
divide x.
=
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: RES: [obm-l] Inversa de uma Matriz

[Domingos Jr.]

Márcio Barbado Jr. wrote:
O problema a seguir eh trivial?
Sejam A e B matrizes quadradas tais que AB = I. Prove que BA = I.
(I = matriz identidade)

INDAGAÇÃO: Não estariam faltando informações? Pois nesse caso, provar que 
BA = I significa provar que B eh a inversa de A e a HIPOTESE para uma matriz
ser invertível eh AB = BA = I (com A e B de mesma ordem), 

-> daí TESE: B eh a inversa de A.
E o problema sugerido fica soh na HIPOTESE.

_
isso é um resultado mais geral de teoria dos grupos.
seja G um grupo e g um elemento de G.
suponha h é a inversa de g, ou seja, gh = e (e é a identidade)
h = h*e = h*g*h = (hg)*h
mas como a identidade é o único elemento com a propriedade e*s = s*e = 
s, devemos ter hg = e.
para provar a propriedade da identidade, assuma que e' também satisfaz 
e'*s = s*e' = s para todo s em G, então e'*e = e' (pela propriedade de e),
por outro lado e'*e = e (pela propriedade de e'), donde e'*e = e = e' = 
e'*e.

[ ]'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] Nao-quadrados perfeitos

[Domingos Jr.]

Claudio Buffara wrote:
Prove que 2^n + 3^n nao eh quadrado perfeito para nenhum inteiro positivo n.
 

2^n + 3^n é ímpar, logo se x^2 = 2^n + 3^n então x^2 ~ 1 (mod 4).
para n >= 2, temos que x^2 ~ 3^n (mod 4), logo n é par.
seja n = 2r.
2^(2r) + 3^(3r) = x^2
3^(2r) = (x - 2^r)(x + 2^r)
como 3 é primo, devemos ter, para algum inteiro s
x - 2^r = 3^s   (1)
x + 2^r = 3^(2r - s)  (2)
(1) + (2) : 2x = 3^s + 3^(2r - s)
note que s < 2r - s e, portanto, 3^s divide x
mas se s > 0 então 2^n = x^2 - 3^n e 3 divide o lado direito, o que é 
absurdo.
se s = 0, então x - 2^r = 1 => x = 2^r + 1
x + 2^r = 2^(r + 1) + 1 < 3^(2r), absurdo.

[ ]'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] Sequencia de numeros compostos

[Domingos Jr.]

Claudio Buffara wrote:
Aqui vai uma versao mais facil de um problema que eu mandei ha algum tempo:
Prove que existe uma infinidade de inteiros k tais que o numero k*14^n + 1
eh composto para n = 1, 2, 3, ...
No problema original, tinhamos 2 ao inves de 14.
[]s,
Claudio.
seja a_n = k * 14^n + 1
a_{n+1} = 14(a_n - 1) + 1
note que se a_n = 0 (mod 13) então
a_{n+1} = -13 = 0 (mod 13)
basta que a_1 = 14k + 1 = 0 (mod 13) para que toda a seq. seja múltipla 
de 13.
note que se k' é solução da congruência acima, k' + 13 também é.
é trivial notar que k' = -1 é solução e, portanto 12 também é solução 
(14*12 + 1 = 13*13)

para k = 12, 25, 38, ... (infinitos valores) o número a_n é múltiplo de 
13 para todo n >= 1.

[ ]'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] sutileza

[Domingos Jr.]

Osvaldo Mello Sponquiado wrote:
Sobre o problema "pq o numero de tartarugas que 
 

acasalam um numero impar de vezes eh par."
   

eu ainda nao vi soluçao mais axo que deve ter alguma 
sacada pelo T. de Ransey (ou Ramsey, nao sei a grafia 
correta)

Alguem ai tem alguns problemas em que se usa Ramsey 
para problemas de grafos nao hamiltonianos para 
discutir ...

 

É Ramsey.
Não precisa usar teoria de Ramsey não, isso é um dos primeiros teoremas 
na teoria dos grafos, se não me engano foi o próprio Euler que provou.
A idéia é simples, construa um grafo onde os vértices são tartarugas e 
as arestas unem tartarugas que já acasalaram. Some os graus (nrs. de 
arestas saindo de um vértice) de cada vértice, é evidente que essa soma 
dá um número par pois cada aresta tem dois extremos e deve ter sido 
contada duas vezes. Sendo assim, o número de vértices com grau ímpar tem 
que ser par, pegou?
=
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] Duvidas- Combinatória

[Domingos Jr.]

aryqueirozq wrote:

Sejam Im =( 1 , 2, m ) e In = ( 1 ,2 ,3 ,...n ), 
com m menor ou igual a n . Quantas são as funções f: Im 
em In estritamente crescente?

 Agradeço desde de já.
Se m > n, claramente esse número é 0 pois não dá para termos f crescente.
Senão, escolha m elementos dentre [n] := {1, ..., n}, ordene-os de forma 
crescente e defina f a partir dessa ordenação. Fica claro que há uma 
bijeção entre as funções crescentes e as escolhas de m elementos dentre 
[n], logo temos Binomial(n, m) maneiras de obter tal função, se 
adotarmos a convenção de que Binomial(n, m) = 0 se m > n, então isso 
vale para todo par m, n.

[ ]'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] Combinatória

[Domingos Jr.]

A idéia de funções geradoras é legal, mas é muito mais legal ter uma 
fórmula fechada! Será que existe? E se formos menos ambiciosos e 
fixarmos um parâmetro (digamos os valores são dígitos e k e n são livres)?

[ ]'s
Qual o coeficiente de t^27 no desenvolvimento de:
(1 + t + t^2 + t^3 + t^4 + t^5 + t^6 + t^7 + t^8 + t^9)^4 ?
Resposta (usando PARI-GP): 220.
Minha pergunta pra voce: Por que isso tah certo?

=
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] Bienal SBM

[Domingos Jr.]

Quem aqui vai na Bienal da SBM?
=
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] Pequeno teorema de Fermat

[Domingos Jr.]

Eu gosto particularmente do teorema de Lagrange (se G <= H são grupos 
finitos, |G| divide |H|) para derivar o teorema de Euler/Fermat.
=
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 Dígitos

[Domingos Jr.]

seja r um número inteiro.
como 9 + 1 = 10, se a representação de r em base 10 é r = d_k d_{k-1} 
... d_0, temos,
r = d_0 + (9 + 1) d_1 + (9 + 1)^2 d_2 +  + (9 + 1)^k d_k.
ou seja, 9 | r se e somente se 9 | d_0 + d_1 + ... + d_k.

vamos dividir os números com a propriedade do enunciado em duas categorias:
1- os números só possuem dígitos 0 ou 1, por exemplo, se n = 4, 0999, 
9099, 9909, 9990 tem soma dos dígitos 9(4 - 1), analogamente, temos
0099, 0909, 0990, 9009, 9090, 9900 com soma dos dígitos 9(4 - 2).
é simples argumentar que há mais números desse tipo com soma dos dígitos 
9(n-2).

2- se r é um número que não tem apenas dígitos 0's e 9's e a soma de 
seus dígitos é 9(n-1), então todo dígito de r deve ser não nulo.
se n >= 9, podemos reduzir em um os 9 primeiros dígitos de r, isso nos 
dá um número r', que tem soma dos dígitos 9(n-2).
mostre que isto é, de fato, um mapa injetivo, e que nenhum elemento é 
mapeado a um número de categoria 1 (isso é simples), isso mostra que a 
quantidade de números de categoria 2 com soma dos dígitos igual a 9(n-1) 
não pode ser maior do que a quantidade de números de categoria 2 com 
soma dos dígitos igual a 9(n-2).

ah, esse argumento só vale pra n >= 9, tente adaptá-lo para n menor.
espero que não tenha sido confuso demais!
[ ]'s
Olá pessoal,
O problema abaixo já passou pela lista, mas a solução envolvia 
derivadas. Vocês poderiam resolvê-lo sem utilizar conceitos de nível 
superior ?

1) Seja n um número natural, n >3.
Demonstrar que entre os múltiplos de 9 menores que 10^n há mais 
números com a soma de seus dígitos igual a 9(n-2) que números com a 
soma de seus dígitos igual a 9(n-1).



=
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] 8ª Cone Sul - tabuleiro

[Domingos Jr.]

[EMAIL PROTECTED] wrote:
Valeu Domingos,
A única passagem que não entendi de sua solução foi:
(... suponha que tenhamos 0 <= x <= 3 elementos {0, 1} dentre os 
elementos da
linha anterior sem incluir o elemento selecionado e há 3 - x elementos 2
dentre esses mesmos caras ...)

a linha anterior (a inicial, por exemplo) tem 4 elementos, sendo que um 
deles será mantido na linha seguinte.
desconsiderando esse cara que está fixo, sobram 3 elementos: sendo que x 
deles são entradas 0 ou 1 e os outros 3 - x são entradas 2.
acho que agora fica claro por que a soma da linha seguinte é S' = S + x 
- 2(3 - x), certo?

sinceramente, eu acho que 27 é um número grandinho, eu não teria saco 
para 'escrever' a solução de um problema desses.

[ ]'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] 8ª Cone Sul - tabuleiro

[Domingos Jr.]

ok, pensando um pouco eu achei algo que deve levar a resposta:
considere a soma dos elementos de uma linha módulo 3, chame tal soma de S.
o procedimento para obter a próxima linha é manter o valor de um 
elemento da linha anterior e alterar os demais.
suponha que tenhamos 0 <= x <= 3 elementos {0, 1} dentre os elementos da 
linha anterior sem incluir o elemento selecionado e há 3 - x elementos 2 
dentre esses mesmos caras.
fica claro que a soma da próxima linha é S' = S + x - 2(3 - x) = S - 6 + 
3x = S (mod 3).

como a primeira linha tem soma 0, provamos que todas as linhas desse seu 
tabuleiro tem soma múltipla de 3.

agora veja que as somas possíveis são 0, 3 e 6, sendo que 0 só pode ser 
obtido de uma maneira e é a primeira linha do tabuleiro.
3 pode ser obtido como um 0 e três 1's (há 4 maneiras de dispô-los), ou 
como um 1, um 2 e dois 0's (2*binomial(4, 2) = 12 maneiras).
6 pode ser obtido como um 0 e três 2's (4 maneiras), ou como dois 1's e 
dois 2's (binomial(4, 2) = 6 maneiras).

eu imagino que seja possível conseguir todas essas possibilidades e aí 
vc teria uma demonstração de que não é possível construir nada maior, 
mas é só um palpite.

[ ]'s
É uma questão do Cone Sul também ... Ninguém quer tentar ?

Em uma mensagem de 12/9/2004 18:26:33 Hora padrão leste da Am. Sul, 
[EMAIL PROTECTED] escreveu:


Olá pessoal,
Considere um tabuleiro de /n/ linhas e 4 colunas.
Na 1a linha são escritos 4 zeros (um em cada casa). A seguir, cada 
linha é obtida a partir da linha anterior realizando a seguinte 
operação: uma das casas, a escolher, é mantida como na linha 
anterior; as outras três são trocadas: se na linha anterior havia um 
0 se coloca 1, se havia 1 se coloca 2 e se havia 2 se coloca 0.
Construa o maior tabuleiro possível com todas as suas linhas 
distintas e demonstre que é impossível construir um maior.


=
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] Contando caminhos em reticulados

[Domingos Jr.]

Olá!
Eu proponho o seguinte problema combinatório que me parece bem difícil:
Seja k > 1 e seja R um reticulado retangular m x n (linhas x colunas). 
Vamos considerar caminhos de (0, 0) a (n, m) em R.
Se P e Q são caminhos de (0, 0) a (n, m) em R, podemos dizer que P <= Q 
sse para todo j, 0 <= j <= m, temos max{i : (i, j) está em P} <= max{k : 
(k, j) está em Q}.
Traçando um gráfico com caminhos P <= Q, vemos que os traços de P nunca 
invadem a área delimitada por Q (por baixo).
De quantas maneiras podemos traçar k caminhos, P_1 <=  ... <= P_k, em R?

Este é um problema que apareceu quando eu tentei resolver uma questão 
proposta pelo Cláudio ou pelo Nicolau (não sei direito!) onde 
perguntava-se quantas maneiras podemos preencher uma matriz A, m x n, 
com elementos de {1, ..., p} tal que A(i, j) > A(i + 1, j) e A(i, j) > 
A(i, j + 1) para todo (i, j). É simples mostrar uma bijeção com um 
problema similar, onde trocamos '>' por '>=' e o conjunto de valores 
para as entradas da matriz é menor. Quando olhamos para este segundo 
problema, podemos pensar na matriz como um reticulado m x n e as 
fronteiras que agrupam números iguais seriam caminhos de (0, 0) a (n, 
m). Se contarmos o número de caminhos possíveis, teremos determinado 
todas as matrizes satisfazendo o segundo problema e, pela bijeção 
montada, teremos resolvido o problema original.

Talvez a idéia não seja o melhor caminho para chegar na resposta. De 
qualquer forma, o problema que eu propus parece ser interessante por si 
só. Eu lembro que o Nicolau havia comentado algo sobre o paper dele em 
Matemática Quântica. Bem, eu li o primeiro capítulo (por cima) mas ainda 
não tive idéias para resolver o problema. Socorro, Nicolau! ;-)

[ ]'s e boa sorte pra quem tentar o desafio.
=
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-2004]

[Domingos Jr.]

Este sistema parece um tanto braçal, mas cortando apropriadamente as 
coisas, ficamos com um sistema simples com equações simétricas. Bom, 
eu achei números "horrorosos" como resposta para a solução do sistema 
e ainda tinha que substitui-los na equação linear (que dá pra ver que 
não é muito agradável, pq tem que elevar a quarta 
potencia...) (hehehe)...não sei se errei em alguma conta, mas parece 
estar certa a forma de resolver, pq fiz no Maple e mandei ele reduzir 
tudo como fraçoes...e a resposta deu, -8/9 e -4/27 que é a resposta 
certa...
é isso...
[]'s, Marcelo
confesso que eu sabia resolver essa questão mas desencanei de fazer as 
contas horrorosas por falta de paciência mesmo...
outra que eu não quis fazer contas chatas foi a parte (b) da 5 (preferi 
dedicar meu tempo pra tentar outros problemas)

achei que a prova tinha muitos "calcule", gostei mais da prova do ano 
passado...

[ ]'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] Re: [obm-l] Questão 4

[Domingos Jr.]

pedro.victor wrote:
m=1 n=0 nao seria tb uma solucao?
-- Cabeçalho inicial  ---
hmmm, depende se sua definição é N = {1, 2, ...} ou N = {0, 1, ...}, 
isso não é algo muito universal, infelizmente,
=
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] Questão 4

[Domingos Jr.]

n.2^(n-1) = (m - 1)(m + 1)
suponha n > 3 (ou não temos sol.)
note que mdc(m - 1, m + 1) = 2 e, se
m - 1 = a*2^b
m + 1 = c*2^d
com b + d = n - 1, então ou b = 1 ou d = 1 (pois 4 não pode dividir ambos) e
a*c = n
suponha b = n - 2, d = 1, então
a*2^{n-2} + 2 = 2*c <=>
a*2^{n-3} + 1 = c. Logo,
a*c = a(a*2^{n-3} + 1) = n
como a >= 1, temos n >= 2^{n-3} + 1, mas então n <= 5.
agora suponha b = 1, d = n - 2, então
a*2 + 2  = c*2^{n-2} <=>
a  = c*2^{n-3} - 1. Logo,
a*c = c(c*2^{n-3} - 1) = n, como c >= 1, temos n >= 2^{n-3} - 1 e, 
novamente, n <= 5

a única sol. é n = 5, m = 9
5 * 2^{5-1} + 1 = 81 = 9^2

Façam essa pra mim ae ...
Questão 4 - OBM - nivel 3 - Determine todas as soluções da equação 
n*(2)^(n-1) + 1 = m^2, com m e n naturais.

[]`s
Daniel Regufe
_
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
=
=
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] Questão 5 - OBM

[Domingos Jr.]

na "definição" de decomposição em primos não incluímos potências com 
expoente 0, pois isso acabaria com a unicidade da decomposição.
=
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] Infinitas soluções - equaçã o

[Domingos Jr.]

[EMAIL PROTECTED] wrote:
Domingos,
Veja o que encontrei:
http://www.math.sfu.ca/History_of_Math/India/12thCenturyAD/Chakravala.html 

Deve ser o intervalo de inteiros [-4;4] mesmo.
Em uma mensagem de 12/9/2004 13:18:44 Hora padrão leste da Am. Sul, 
[EMAIL PROTECTED] escreveu:

há métodos pra achar a solução dessas equações quando elas existem, no 
entanto, me parece que o único caso em que há garantia de infinitas 
soluções é
x^2 + Dy^2 = 1, com D > 0, natural, não-quadrado.

veja
http://mathworld.wolfram.com/PellEquation.html
[ ]'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] Infinitas soluções - equação

[Domingos Jr.]

[EMAIL PROTECTED] wrote:
Valeu Domingos,
O segredo deve ser esse mesmo, ou seja, achar um terno, substituir um 
dos valores deste terno na equação e a mesma ficará com 2 incógnitas. 
Depois é só modelar a mesma para assumir a forma de uma equação de 
Pell (x^2 - b*y^2 = 1) que possui infinitas soluções.

Em relação às equações de Pell, uma dúvida conceitual:
x^2 - b*y^2 = a ...
Quais os valores que "a" pode assumir ? Eu ouvi dizer que é 1 ou -1. 
Outra referência dizia o intervalo de inteiros [-4;4].

x^2 + b*y^2 = 1
se b não é quadrado perfeito há infinitos pares (x, y) de inteiros que 
são solução da eq.
se tivermos -1 no lado direito isso pode não é sempre verdade.
isso é o que eu conheço a respeito disso, talvez alguém saiba mais a 
respeito.

[ ]'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] Infinitas soluções - equação

[Domingos Jr.]

[EMAIL PROTECTED] wrote:
Para Domingos ou qualquer outro participante da lista,
1- Por que 5|B e 3|C pois 3 e 5 sÃo primos ?
2- Esse à um problema olÃmpico, logo deve haver uma resoluÃÃo que nÃo 
envolva criaÃÃo de programa de computador para resolvÃ-lo. Logo como 
alguÃm poderia resolvÃ-lo em um vestibular, concurso, olimpÃada e 
processos seletivos em geral ?

Em uma mensagem de 9/9/2004 05:57:05 Hora padrÃo leste da Am. Sul, 
[EMAIL PROTECTED] escreveu:


1- na verdade à 5|b e 3|c, falha minha...
à bem simples, 3b^2 = 5c2 + 75
5 divide o lado direito, entÃo 5|3b^2, sabemos entÃo que 5|b^2 e, 
portanto 5|b... a outra asserÃÃo à anÃloga.

vocà nÃo precisa de um programa de computador... mas vai ter que 
inspecionar alguns valores na mÃo... eu sou preguiÃoso, uso o pc.

[ ]'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] Algebra Linear - Operadores Lineares

[Domingos Jr.]

positiva quer dizer que para todo vetor x != 0, temos x* T x > 0?
seja v um auto-vetor de T, se Tv = dv, então
 =  = d^2  = d^2 ||v||^2
mas  = (Tv)*(Tv) = v*T*Tv = v* I v = ||v||^2
d^2 = 1
como ela é positiva, d = 1.
tr(T) = traço(T) = soma dos auto-valores (contando multiplicidades), logo
tr(T) = n
Mas cada entrada da matriz T tem valor absoluto não superior a 1, pois T 
é unitária. Logo tr(T) <= n, com igualdade se e somente se cada elemento 
da diagonal é 1. Isso mostra que T = I.

[ ]'s
Pessoal,
Alguém pode me dar uma ajuda a provar isto aqui
Let T be a linear operator on the finite-dimensional inner product space V,
and suppose T is both positive and unitary. Prove T = I.
Obrigado.
[]s
Daniel S. Braz
 

=
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] Algebra Linear - Operadores Lineares

[Domingos Jr.]

positiva quer dizer que para todo vetor x != 0, temos x* T x > 0?
seja v um auto-vetor de T, se Tv = dv, então
 =  = d2  = d2 ||v||^2
mas  = (Tv)*(Tv) = v*T*Tv = v* I v = ||v||^2
d2 = 1
como ela é positiva, d = 1.
tr(T) = traço(T) = soma dos auto-valores (contando multiplicidades), logo
tr(T) = n
Mas cada entrada da matriz T tem valor absoluto não superior a 1, pois T 
é unitária. Logo tr(T) <= n, com igualdade se e somente se cada elemento 
da diagonal é 1. Isso mostra que T = I.

[ ]'s
Pessoal,
Alguém pode me dar uma ajuda a provar isto aqui
Let T be a linear operator on the finite-dimensional inner product 
space V,
and suppose T is both positive and unitary. Prove T = I.

Obrigado.
[]s
Daniel S. Braz
 

=
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] Infinitas soluções - equação

[Domingos Jr.]

Olà pessoal,
Demonstrar que existem infinitos ternos (a, b, c), com a, b, c nÃmeros 
naturais, que satisfazem a relaÃÃo: 2a^2+ 3b^2 â 5c^2 = 1997.

estou sentindo Deja-vu... jà resolvi esse aqui na lista, dà uma olhada.
 mensagem de 22/07/2004 
Com um programa de computador (bem simples, feito em VB) eu encontrei a 
soluÃÃo
a = 31, b = 20, c = 15.
Na verdade, eu encontrei vÃrias, mas essa pareceu particularmente 
promissora pois quando a = 31, 2a2 = 1922, que à perto de 1997.

EntÃo, vamos mostrar que existem infinitas soluÃÃes naturais com a = 31:
2*312 + 3b2 - 5^c2 = 1997
3b2 - 5c2 = 75
dà pra ver que 5|B e 3|C pois 3 e 5 sÃo primos, sendo assim, sejam
b = 5B
c = 3C
75B2 - 45C2 = 75
5B2 - 3C2 = 5
agora temos que 5|C, seja entÃo
C = 5D
5B2 - 75D2 = 5
B2 - 15D2 = 1
essa aqui à uma instÃncia da famosa eq. de Pell, que admite uma 
infinidade de soluÃÃes inteiras (podemos assumir que as sol. sÃo 
naturais pois se (B, C) Ã soluÃÃo da eq. acima, entÃo (|B|, |C|) tambÃm Ã).

=
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] Matriz por triangularização

[Domingos Jr.]

Trocar uma linha/coluna da matriz por uma combinação linear das 
linhas/colunas da matriz não afeta o determinante, então por exemplo, 
você pode
trocar a primeira coluna pela soma desta com a segunda coluna e assim 
introduzir um zero em (3, 1). Repita o processo de forma a introduzir 
quantos zeros forem possíveis, isso vai te facilitar a vida.

Olá pessoal boa noite.
Recebi uma questão  e depois de muito tentar, sem conseguir resolvê-la, decidi pedir 
ajuda na lista. Tenho que resolver a matriz 3x3, que se seugue por triangularização, 
calculando o seu determinante. Eis a matriz:
t+3   -1 1
5  t-31
6  -6t+4 

Pede-se ainda determinar t para que a matriz dada seja inversível.
Bem se alguém puder me dar uma mãozinha, agradeço bastante,
Um abraço, Marcelo.
---
iBestMail, agora com POP3/SMTP e 120MB de espaço!
Experimente: http://www.ibestmail.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] Um problema de Probabilidade

[Domingos Jr.]

Olá!
Tentem fazer este daqui:
Sejam n >= 1 e a_1, ..., a_n reais tais que a_1^2 + ... + a_n^2 = 1.
Sejam e_1, ..., e_n elementos de {-1, 1} escolhidos aleatoriamente de 
forma uniforme e indendente.
Mostre que Pr[|e_1*a_1 + ... + e_n*a_n| <= 1] >= c para uma constante 
absoluta c > 0.

Obs: note que c não depende de n e a escolha dos a_i's é arbitrária.
Eu consigo provar que Pr[|e_1*a_1 + ... + e_n*a_n| <= 1] > 0 para todo n 
>= 1 e toda escolha de a_i's, mas a asserção é mais forte que isso.

[ ]'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] Problema das Oito Rainhas...

[Domingos Jr.]

Que tal deixar de ser preguiçoso e pesquisar algum livro de IA como o 
AIMA (artifficial intelligence - a modern approach).

Alguem poderia me ajudar com a solução desse problema Estou 
realmente precisando...  Obrigrado... se for possivel me mandar a 
solução para esse e-mail ou [EMAIL PROTECTED] 
 ficaria muito grato!
 
*Problema - colocar oito rainhas no tabuleiro de xadrez modo que 
nenhuma delas ataque as outras. As rainhas podem se mover em linhas, 
em colunas ou em diagonais, qualquer número de casas e sentido.  
identificando as colunas de A a H e as linhas de 1 a 8. . Marque no 
tabuleiro a posição de cada rainha (R1,...,R8) e as casas atacadas por 
pelo menos uma das rainhas com 'X'. Identifique o fim do processo e 
número de rainhas posicionadas em cada tentativa. Pense numa 
heurística para chegar às 8 rainhas a partir de qualquer posição inicial*


Yahoo! Acesso Grátis 
 - 
navegue de graça com conexão de qualidade! 

=
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] Pra lembrar os velhos tempos... Um pouco de PCP

[Domingos Jr.]

Seja n>4 um inteiro.
Prove que para quaisquer numeros a(i), 1<=i<=n, satisfazendo 
 
1<=a(1)
 
existem i e j, i
É um fato conhecido que se tivermos n+1 elementos de um conjunto A 
contido em {1, ..., 2n} então há dois números a, b tais que a divide b. 
Neste caso é evidente que o mmc(a, b) = b <= 2n.

A demonstração disso é bem bonitinha:
Todo elemento a de A pode ser escrito como a = 2^k * m onde m é ímpar (m 
está em {1, 3, ..., 2n-1}). Como há n+1 elementos em A, dois deles tem 
mesma parte ímpar, e isso mostra que um divide o outro.
No caso de n elementos, se não podemos repetir nenhum elemento ímpar, 
então todos os ímpares possíveis devem ser usados, ou seja, devemos ter
A = {2^k_1, 2^k_2 * 3, 2^k_3 * 5, ..., 2^k_n * (2n-1)}

Claramente os elementos a = 2^k * m, para os quais n < m < 2n, tem 
expoente k = 0, ou seja, {2n - 1, 2n - 3, ..., r} estão em A, onde n < r 
< n + 3.
Tome m como o menor múltiplo de 3, ímpar, maior que 3n/2 (note que m 
está em A).
Pela nossa escolha m/3 é um inteiro ímpar e 4m/3 > 2n. Sendo assim, o 
elemento 2^k * (m/3) que está em A é tal que 0 <= k < 2.

Veja que mmc(2^k * m/3, m) = 2^k * m <= 2m.
Dá pra ver que 2m = 3n + O(1). Agora tem que ver como trocar esse O(1) 
pela constante do enunciado, mas isso fica pra quem tiver paciência.

[ ]'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] Auto-valores de grafos

[Domingos Jr.]

Agora parece ok!
=
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] Auto-valores de grafos

[Domingos Jr.]

A coordenada (i, j) de B^k representa o número de passeios no grafo 
(onde podemos repetir arestas) do vértice i até o vértice j.
Como o grafo é conexo, para algum k, B^k tem todas as entradas positivas. 
faltou dizer que é o número de passeios no grafo com <= k arestas.
=
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] Auto-valores de grafos

[Domingos Jr.]

Vamos mostrar o caso em que o grafo é conexo.
Considere a matriz B = A + I. Note que B é simétrica e real também.
A coordenada (i, j) de B^k representa o número de passeios no grafo 
(onde podemos repetir arestas) do vértice i até o vértice j.
Como o grafo é conexo, para algum k, B^k tem todas as entradas positivas.
Agora note que se x não é múltiplo de (1, ..., 1) e Ax = dx, então Bx = 
(d+1)x e, portanto x é auto-vetor de B.
Seja m tal que x_m é mínimo. Defina y = x - x_m*(1, ..., 1). Veja que y 
é auto-vetor de B (com auto-valor correspondente d+1), cuja menor 
coordenada é 0 e todas as demais são não-negativas.
B^k y = (d+1)^k y, mas isso é absurdo pois y_m = 0 e, portanto, [(d+1)^k 
y]_m = 0, enquanto
[B^k y]_m > 0, pois este valor é a soma de valores não negativos (onde 
pelo menos um valor é estritamente positivo).

Se o grafo tem r componentes conexas, podemos formar explicitamente uma 
base de auto-vetores para a matriz de adjacência. Se há r componentes 
conexas, digamos C_1, ..., C_r, então os vetores {v_i} que possuem 0 nas 
coordenadas correspondentes a C_j com j != i e 1 nas coordenadas 
correspondentes a C_i formam uma base de auto-vetores da matriz de 
adjacência.

[ ]'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] algumas de combinatória

[Domingos Jr.]

Andre Silveira Ramos wrote:
Aí pessoal, estou com alguns problemas de combinatória que não estou 
conseguindo sair do lugar.
Preciso de algumas dicas
 
 (i) Considere um conjunto P de 30 pontos do espaço e P1 um 
subconjunto de 12 pontos coplanares de P. Sabe-se que sempre que 4 
pontos de P são coplanares, então eles são pontos de P1. Quantos são 
os planos que contém pelo menos 3 pontos de P?
Tome x pertencente a P \ P1.
Note que x não pode ser coplanar com os pontos de P1 pois se fosse 
qualquer escolha de 3 elementos de P1 e o elemento x formariam um 
conjunto de 4 pontos coplanares que não está contido em P1.
Para cada par de elementos distintos {y, z} de P1 o conjunto {x, y, z} 
determina um plano. Como x não pertence ao plano de P1 não pode haver um 
outro ponto de P no plano determinado por {x, y, z}. Como isso vale para 
cada x escolhido e para cada par {y, z}, o total de planos é dado pelo 
nr. de opções para x vezes o nr. de pares de pontos de P1 + o nr. de 
planos formados por 3 pontos fora de P1 (cada tripla deve determinar um 
plano diferente) +  1 (o próprio plano dos pontos de P1), ou seja
18 * Binomial(12, 2) + Binomial(18, 3) + 1

  <>(iv) Calcular a soma de todos os números de 5 algarismos distintos 
formados com os algarismos 1, 3, 5, 7 e 9.
 
esses números são todas as permutações de 13579, podemos quebrar a soma 
desses números em somas das unidades, das dezenas, centenas...
quantos números tem 1 como unidade? claramente, temos 4! maneiras de 
escolher os demais algarismos... e isso também vale para as outros 
valores das unidades e também para as posições mais significativas dos 
números, então temos
4! (1 + 10 + 100 + 1000 + 1) (1 + 3 + 5 + 7 + 9) = .
=
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] Auto-valores de grafos

[Domingos Jr.]

hmmm, lendo melhor o que vc escreveu, tem uma falha:
"Seja u_j a componente de maior valor absoluto de u.
Entao a j-esima componente de Au serah igual a uma soma de d componentes u_i
e tambem serah igual a d*u_j (pois u eh autovetor de A associado a d).
Dada a escolha de u_j, isso soh poderah ocorrer se todos os u_i's forem
iguais..."
acontece que você descobriu que esses "d" u_i's são iguais, mas isso não 
prova imediatamente que todos os u_i's são iguais...
eu tenho uma demonstração interessante, mas vou deixar você pensar um 
pouco mais.

[ ]'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
=

[obm-l] + um com AntiSPAM do UOL

[Domingos Jr.]

Oi!
Nicolau, agora é o [EMAIL PROTECTED] que está usando o brilhante 
anti-spam do UOL...

[ ]'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] Re:_[obm-l]_Questão

[Domingos Jr.]

vou dar a resposta "idiota" pra essa...
supondo que o problema proposto não tenha erros, você obteve o maior 
valor de "e" possível dentre as opções, logo...

se eu fosse resolver, acho que usaria Lagrange.
Quem garante que a=b=c=d e mesmo a soluçao minima?
=
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] AB vs BA e Formula para Nos. Compostos

[Domingos Jr.]

oi!
tem uma idéia, mas acho q vai precisar de contas chatas que eu não tenho 
a menor disposição pra fazer.

se f(n) = k*2^n + 1
é simples de verificar que f(n + a) = 2^k * f(n) - (2^a - 1)
por Euler, 2^phi(m) = 1 (mod m) quando mdc(m, 2) = 1 (ou seja, m é ímpar).
se m|f(n) fica claro que m|f(n + c*phi(m)) para todo c >= 0.
No segundo, eu acho que eh preciso encontrar primos p1, p2, ..., pr tais que
pelo menos um deles divide k*2^n + 1, para cada n. Estou convencido de que o
teorema chines dos restos deve ser usado em algum lugar, mas nao consegui
nada de muito substancial.
Qualquer ajuda serah bem-vinda.
[]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] Auto-valores de grafos

[Domingos Jr.]

Chicao Valadares wrote:
eu gostaria que vc enviasse para mim.Estou estudando
metodos probabilisticos e seria de grande utilidade.
ok, eu ainda vou complementar mais a parte probabilística dessa 
monografia... a ênfase até o momento foi na parte construtiva.

http://www.linux.ime.usp.br/~domingos/lb-ramsey.pdf
opiniões são bem vindas.
[ ]'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] Auto-valores de grafos

[Domingos Jr.]

perfeito!
tem vários outros fatos interessantes que eu aprendi recentemente na 
minha iniciação científica.
estou escrevendo uma monografia pra participar da jornada de IC no IMPA.
se você (ou mais alguém) tiver interesse em ver, eu coloco na web.

[ ]'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
=

[obm-l] Auto-valores de grafos

[Domingos Jr.]

Este aqui é bonitinho:
Se G é um grafo d-regular com r componentes conexas e A é sua matriz de 
adjacência então A tem d como auto-valor de multiplicidade r.

[ ]'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] BEBIDA GRÁTIS!

[Domingos Jr.]

essa situação não pode existir.
se você modelar um grafo dirigido onde os vértices são moedas e o peso 
dos arcos são a taxa de conversão de uma para a outra, então não pode 
haver um ciclo em que o produto dos pesos dos arcos do ciclo seja > 1.

[ ]'s
no princípio, com um dólar. Quem pagou a cerveja?
 

=
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] gavetas

[Domingos Jr.]

eu já resolvi esse faz um tempo...
vc tem que quebrar o conjunto a partir do PCP obtendo um conjunto com k 
elementos x_1 < x_2 < ... < x_k, com k >= 330
aí vc olha pra x_2 - x_1, ..., x_k - x_1 que são k-1 >= 329 valores 
diferentes que estão entre 1 e 1978 e não devem
estar em alguma das outras 5 partições, então repita o PCP para esse 
conjunto de tamanho k-1 e continue o processo,
você verá que a última partição não poderá ter 2 elementos do conjunto e 
aí você chega numa contradição.

[ ]'s
Saudações,
 
Eu sou novo no grupo e gostaria de saber se alguém pode me ajudar a 
resolver o seguinte problema:
 
*Prove que se o conjunto {1, 2, ... , 1978} é partido em 6 
subconjuntos, em algum desses subconjuntos existe um elemento que é 
igual à soma de dois elementos, não necessariamente distintos, do 
mesmo subconjunto.*
 
Não consegui resolver e já procurei em alguns livros e também na 
internet mas não encontrei nada.
 
Este problema se encontra no livro /Análise Combinatória e 
probabiblidade/  da /Coleção do professor de Matemática/.
 

=
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] idéia - problema da IMC

[Domingos Jr.]

Domingos Jr. wrote:
Olá!
Tive uma idéia pra um dos problemas da IMC (um que eu achei bem 
difícil...).
Enunciado (copiado de uma msg da lista):

5) Let X be a set of  binomial(2k-4, k-2) + 1  real numbers,
k>=2. Prove that there exists a monotone sequence x_1, x_2, ..., x_k in
X such that |x_{i+1} - x_1| >= 2|x_i - x_1|
for all i = 2,...,k-1.
Vou tentar re-escrever isso aqui de forma decente... vou provar que se 
um conjunto de reais S
tem tamanho |S| >= n! então há uma seq. de n elementos satisfazendo as 
condições do enunciado.

Lema 1: se X é um conjunto de k reais, então uma das duas vale:
(i) Existe uma seq. monótona de tamanho k (ou seja, o conjunto X 
ordenado) satisfazendo as CE
(ii) Existe uma seq. crescente com 3 elementos e que satisfaz as 
condições do enunciado (CE)

Dem.: Sejam x_1 < x_2 < ... < x_k os elementos de X.
Se não há uma seq. crescente de 3 elementos nas CE, então
a seq. monótona decrescente x_k > x_{k-1} > ... > x_1 é tal que, para 
todo 1 <= j < k
x_k - x_j >= 2(x_k - x_{j+1}), caso contrário teríamos para algum j,
x_k - x_j < 2(x_k - x_{j+1}) e, portanto, x_j < x_{j+1} < x_k é uma seq. 
de tamanho 3
nas CE, pois x_k - x_j = x_k - x_{j+1} + x_{j+1} - x_j < 2(x_k - 
x_{j+1}), logo
x_{j+1} - x_j < x_k - x_{j+1}, donde tiramos que
x_k - x_j > 2(x_{j+1} - x_j).
Caso não haja uma seq. decrescente de 3 elementos nas CE um raciocínio 
análogo mostra
que a seq. x_1 < ... < x_k está nas CE.

Lema 2: se y_1 < y_2 < ... < y_k é uma seq. nas CE e z_1 < ... < z_r são 
reais entre
y_1 e y_2 (inclusive) nas CE, então z_1 < ... < z_r < y_3 < ... < y_k é 
uma seq. nas CE.

Dem.: precisamos mostrar que para todo j >= 3
y_{j+1} - z_1 >= 2(y_j - z_1)
note que z_1 = y_1 + s, com s >= 0, temos então
y_{j+1} - z_1 = y_{j+1} - y_1 - s
y_j - z_1 = y_j - y_1 - s
Por hipótese, temos y_{j+1} - y_1 >= 2(y_j - y_1), logo
y_{j+1} - z_1 = y_{j+1} - y_1 - s >= 2(y_j - y_1) - s >= 2(y_j - y_1 - 
s) = 2(y_j - z_1).
Evidentemente o lema se estende para o caso de seq. decrescentes nas CE.

Definição: f(n) := menor inteiro tal que qualquer conjunto S com |S| = 
f(n) reais possui
uma seq. monótona nas CE com pelo menos n termos.

Teorema: f(n) < n! para n >= 2
Dem.: os casos n = 2, 3 são triviais, suponha n > 3
Seja T um conjunto com |T| = (n-1) (f(n)-1) elementos.
Se y_1 < y_2 < ... < y_{(n-1)(f(n)-1)} são os elementos de T, defina
X = {x_{1 + (n-1).r}, r = 0..f(n)-1}, temos que |X| = f(n), então, pela
hip. de indução X possue uma seq. x_1, x_2, ..., x_n nas CE.
se a seq. for crescente, então considere os elementos x_1 e x_2 e
todos os elementos entre eles em T (há pelo menos n-1 desses
por construção); estamos considerando pelo menos n+1 elementos e,
de acordo com o lema 1 ou
(i) há uma seq. de tamanho n+1 nas CE (e aí não precisamos fazer mais 
nada) ou
(ii) temos pelo menos uma seq. crescente e uma seq. decrescente de 
tamanho 3 nas CE.
tome z_1 < z_2 < z_3 satisfazendo as CE e aplique o lema 2, a seq.
z_1 < z_2 < z_3 < y_3 < ... < y_n tem tamanho n+1 e satisfaz as CE.

Isso demonstra que f(n+1) <= (n-1)(f(n)-1), disso segue f(n) < n! para 
todo n >= 2.

[ ]'s
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
=

[obm-l] idéia - problema da IMC

[Domingos Jr.]

Olá!
Tive uma idéia pra um dos problemas da IMC (um que eu achei bem difícil...).
Enunciado (copiado de uma msg da lista):
5) Let X be a set of  binomial(2k-4, k-2) + 1  real numbers,
k>=2. Prove that there exists a monotone sequence x_1, x_2, ..., x_k in
X such that |x_{i+1} - x_1| >= 2|x_i - x_1|
for all i = 2,...,k-1.
A idéia é a seguinte: eu gostaria de um número pequeno r tal que para 
todo conjunto S de tamanho |S| = r tenhamos tenhamos x_1 < x_2 < x_3 e 
y_1 > y_2 > y_3 em S com x_3 - x_1 >= 2(x_2 - x_1) e y_1 - y_3 >= 2(y_1 
- y_2), ou seja, quero encontrar tanto uma seq. monótona crescente com a 
propriedade acima quanto uma decrescente.

Suponha que f(n) é o menor valor para o qual qualquer conjunto S de 
tamanho |S| >= f(n) possua uma seq. de tamanho n da maneira colocada no 
enunciado.
Então se se tivermos um conjunto T com |T| >= f(n)*(r-1) elementos, T 
deve possuir uma seq. de tamanho n + 1 da maneira colocada no enunciado.
Para ver isso, ordene T, pegue o menor elemento e jogue num conjunto X, 
elimine os próximos r-2 elementos de T e novamente pegue um elemento de 
T e jogue em S, repita o processo até não haver mais elementos em T. 
Note que |X| >= f(n) pois a cada passo estamos retirando (r-1) elementos 
de T e um deles vai para X.

Por hipótese, X possui uma seq. de tamanho n com a propriedade desejada. 
Seja x_1, x_2, ..., x_n tal seq. e, sem perda de generalidade*, assuma 
que ela é crescente.

Temos r-2 elementos entre x_1 e x_2 em T (os que foram descartados), 
sejam y_1 < y_2 < ... < y_{r-2} tais elementos. Note que, o conjunto 
{x_1, y_1, ..., y_{r-2}, x_2} tem r elementos e, portanto possui uma 
seq. crescente de tamanho 3, digamos z_1 < z_2 < z_3, com a propriedade 
desejada.

Agora veja que a seqüência z_1 < z_2 < z_3 < x_3 < x_4 <  ... < x_n 
satisfaz a propriedade desejada, pois
x_3 - z_3 >= x_3 - x_2 >= 2(x_2 - x_1)
z_3 - z_1 <= x_2 - x_1, logo
x_3 - z_3 >= 2(z_3 - z_1).

* se a seq. fosse decrescente, ou seja, x_1 > x_2 > ... > x_n, 
tomaríamos z_1 > z_2 > z_3

Então, o que vocês acham?
A idéia me lembra a demonstração do teorema de Van der Waerden.
http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem
[ ]'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
=