[obm-l] Problema 6 da OBM nível U, outra solução

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

Há mais ou menos uma semana, enviei para a lista uma solução
para o problema 6, nivel U. Segue outra (resumida),
baseada na solução incompleta apresentada na prova
pelo Fabio Dias Moreira (com permissão dele).

Sejam A e B como no enunciado; escreverei A' = A^(-1), B' = B^(-1).
Seja G o grupo gerado por A e B.

Seja H o conjunto das matrizes X = (a b \\ c d) 2x2 de coeficientes inteiros,
com a = 1 (mod 4), b = 0 (mod 2), c = 0 (mod 2), d = 1 (mod 4).
É fácil verificar que H é um grupo e que G está contido em H.
Defina |X| = |a| + |b| + |c| + |d|.

Conjectura: Dada X em H, X diferente de I, exatamente um dentre
os módulos |XA|, |XA'|, |XB|, |XB'| é menor do que |X|
(os outros três são estritamente maiores).

A conjectura é correta e será demonstrada abaixo.

A conjectura implica que G = H.
Vamos provar por indução em m que se X pertence a H e |X| < m
então X pertence a G. O caso m = 3 é trivial.
Seja X um elemento de H com |X| = m >= 4.
Pela conjectura, uma das matrizes XA, XA', XB, XB' tem módulo
menor logo por indução pertence a G.

A conjectura também resolve o problema pois se a_1, b_1, ... são não nulos
temos então que |I| < |A^(a_1)| < |A^(a_1) B^(b_1)| < |A^(a_1) B^(b_1) A^(a_2)|
e assim por diante.

Para provar a conjectura, vamos definir quatro subconjuntos de R^2:
A+ = {(x,y) | |x| > |y|, xy > 0}
A- = {(x,y) | |x| > |y|, xy < 0}
B+ = {(x,y) | |y| > |x|, xy > 0}
B- = {(x,y) | |y| > |x|, xy < 0}
Assim, os conjuntos são disjuntos e cada conjunto é a união disjunta
de dois ângulos abertos. O fecho da união é o plano.
Podemos dizer que cortamos o plano em 8 fatias como se fosse uma pizza.

Usaremos no plano a norma |(x,y)| = |x| + |y|.
As seguintes afirmações são de fácil verificação:
se v pertence a A+ então |A'v| < |v| < |Av|, |Bv|, |B'v|;
se v pertence a A- então |Av| < |v| < |A'v|, |Bv|, |B'v|;
se v pertence a B+ então |B'v| < |v| < |Av|, |A'v|, |Bv|;
se v pertence a A- então |Bv| < |v| < |Av|, |A'v|, |B'v|.

Seja agora X uma matriz em H, X diferente da identidade.
Uma das colunas de X pertence a A+, A-, B+, B-
(ou seja, pelo menos uma das colunas não está nem nos eixos
nem nas retas x = +-y).
Não é difícil provar que a outra coluna deve estar no fecho do mesmo conjunto;
ou seja, não podemos ter uma coluna em A+ e outra em B+, por exemplo,
sem violar a condição det X = 1.
Assim, uma das quatro matrizes A, A', B, B' diminui as duas colunas de X
e as outras três aumentam. Por exemplo, se as duas colunas estão em A-
então A diminui as colunas de X mas A', B e B' aumentam.
Isto prova que |AX| < |X| < |A'X|, |BX|, |B'X|.
A conjectura agora segue.

[]s, N.

PS: Os leitores são convidados a refletir sobre a relação entre os conjuntos
A+, A-, B+, B- nesta demonstração e seus homônimos na outra.


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