Re: IMO2000 na minha home page

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Fri, 28 Jul 2000, Ponce wrote:

> Ol� amigos,
> Em resposta a proposta do Nicolau, vai uma poss�vel solu��o do primeiro
> problema, considerado o mais f�cil da prova.
> 
> Enunciado
> 
> Duas circunfer�ncias G1 e  G2  interceptam-se em M e N.Seja t a reta tangente
> comum a G1 e G2 mais pr�xima de M.
> Sejam A e B os pontos de intersec��o de t com G1 e G2 respectivamente.Seja s a
> reta paralela a t por M, C a sua intersec��o com G1 e D com G2 .As retas CA e DB
> interceptam-se em E, as retas AN e CD interceptam-se em
> P e as retas BN e CD interceptam-se em Q.  Mostre que EP = EQ.    (Origem: IMO �
> 2000)

Valeu, Ponce, confesso que ainda n�o li sua solu��o,
mas a� vai minha mensagem anterior desencriptada:

> > A resposta � para l >= 1/(n-1).
> > Devemos demonstrar duas coisas:
> >
> > (a) que para l >= 1/(n-1) existe uma seq��ncia infinita de movimentos
> > que vai levando as pulgas cada vez mais para a direita, ultrapassando
> > qualquer ponto prefixado M;
> >
> > (b) que para l < 1/(n-1) e para qualquer posi��o inicial dada das pulgas
> > existe um ponto M tal que as pulgas em um n�mero finito de movimentos
> > jamais alcan�am ou ultrapassam M.
> >
> > Come�arei pelo item (b). Sejam x_1, x_2, ..., x_n as posi��es iniciais
> > das pulgas, com x_1 <= x_2 <= ... <= x_n, de tal forma que x_n � a posi��o
> > da pulga mais � direita.
> > Seja M = (1/(1 - (n-1)l)) * (x_n - l*x_1 - l*x_2 - ... - l*x_{n-1}).
> > O ponto M claramente est� � direita de todas as pulgas.
> > Afirmamos que se ap�s alguns movimento as novas posi��es s�o
> > x'_1, ..., x'_n e se definimos
> > M' = (1/(1 - (n-1)l)) * (x'_n - l*x'_1 - l*x'_2 - ... - l*x'_{n-1})
> > ent�o M' <= M; isto concluir� a demonstra��o.
> > Basta considerar o que ocorre ap�s um movimento.
> > Se a pulga que estava em x_i pula sobre a pulga que estava em x_n
> > ent�o x'_n - x_n = l*(x_n - x_i) e x'_n - l*x_n = x_n - l*x_i e M' = M.
> > Qualquer outro caso � ainda mais favor�vel.
> >
> > O item (a) e a motiva��o para a f�rmula de M eu deixo para voc�s pensarem...

Para o item (a) minha estrat�gia � sempre fazer a pulga x_1 pular
por cima da pulga x_n. Isto equivale a considerar iteradas da matriz

[  0    1    0    0    0  ]
[                         ]
[  0    0    1    0    0  ]
[                         ]
[  0    0    0    1    0  ]
[                         ]
[  0    0    0    0    1  ]
[                         ]
[  -l   0    0    0   1+l ]

Agora um pouco de �lgebra linear mostra que para l = 1/(n-1)
1 � autovalor duplo com nilpot�ncia e para l > 1/(n-1)
o maior autovalor � maior do que 1.
Observe que 1 � sempre autovalor com autovetor � esquerda

[  -l   -l   -l   -l   1  ]

e foi da� que veio (para mim!) a f�rmula para M.
Enfim, para l >= 1/(n-1) quase todo vetor tende a infinito
e as exce��es v�m de ordenar errado.

[]s, N.