Re: OBM

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

On Mon, Oct 22, 2001 at 10:52:10PM -0200, Bruno Fernandes Cerqueira Leite wrote:
> (...)
> >
> >Acho que já posso contar um segredo: esta questão foi gerada por um erro
> >tipográfico da Nelly quando ela transcrevia uma questão bem mais fácil.
> >Ficou ótima assim. :-)
> 
> 
> Acho que a Nelly também cometeu erros tipográficos na questão 3 do nível
> universitário! :-)
> 
> Essa questão era beeeeeem difícil, eu até agora não sei como fazer um
> avanço não trivial.
> 
> Aliás, ninguém parabenizou ainda a prova da universitária, então eu vou
> parabenizar: estava muito boa, as questões eram muito bonitas: valeu a pena
> pensar 9 horas nelas! (eu até pensaria mais) Como vcs foram?
> 
> Bruno Leite

Esta questão é minha. Obrigado pelos elogios. Segue uma solução.


O polinômio característico de M é da forma x^2 - tx + 1, t inteiro,
e as raízes (ou seja, os autovalores) devem ser raízes da unidade.
Isto nos limita aos casos t = 0, +-1, +-2.
Aliás, t é o traço da matriz, a soma dos autovalores.

Vamos considerar o caso t = 2. Sabemos que M deve ser conjugada
(via uma matriz X real, não inteira ainda!) a uma das matrizes abaixo:

(1 0)       (1 1)
(   )  ou   (   )
(0 1)       (0 1)


Como uma potência positiva da segunda matriz nunca dá a identidade
concluimos que M é conjugada e portanto igual à identidade.
O caso t = -2 é análogo.

Vamos considerar agora o caso t = 1 (os casos t = 0 e t = -1 são análogos).
Novamente M é conjugada via uma X real a

(0 -1)
(    )
(1  1)

Assim v e Mv nunca são colineares (para v != 0).
Suponha que o ângulo de v para Mv está sempre estritamente
entre 0 e Pi (o outro caso, quando o ângulo está entre -Pi e 0,
é análogo). Sempre temos M^2v = Mv - v e M^3v = -v.
Assim os pontos v, Mv, M^2v, M^3v, M^4v e M^5v são os vértices
de um hexágono convexo com centro na origem.
Seja v_0 um vetor não nulo de coordenadas inteiras tal que
a área do hexágono correspondente seja mínima. Isto significa
que não há nenhum ponto de coordenadas inteiras no interior
ou sobre os lados do hexágono. Assim, o determinante da matriz
inteira de colunas v_0 e Mv_0 é 1: esta matriz é a X pedida no problema.

[]s, N.