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.