[obm-l] IMO dia 1, Q1 (solucao?!)

["Marcio" <mcohen@xxxxxxxxxx>]

Me ajudem a detectar possiveis falhas nessa solucao!

"Traducao" : Seja n > 0 inteiro.  Seja T_n o conjunto dos ptos (x,y) do
plano com x,y inteiros nao negativos e x+y < n. Cada pto de T eh pintado de
R ou B. Se (x,y) eh R, entao tmb o serao tds os ptos (x',y') de Tcom x' <= x
e y'<=y. Defina uma X-set como um conjunto de n ptos azuis com coordenadas x
distintas, e uma
Y-set como um conjunto de n ptos azuis com coordenadas y distintas. Prove
que o nr de X-sets eh igual ao nr de Y-sets.

Minha solucao foi por inducao na seguinte proposicao:
Se a n-upla P = (p0, p1, ..., p_(n-1) ) da a qtd de ptos pintados de B nas
retas x=0, x=1, ..., x=n-1 (respectivamente), entao a qtd de B's nas retas
y=0, y=1, ..., y=n-1 nessa ordem eh dada por uma permutacao de P. (em
particular nr de X-sets = nr de Y-sets = Produtorio de p_i).

Em 1o lugar, note que se (x,y)=B, entao (x', y') = B sempre que x'>=x ou
y'>=y.

Para n=1, n=2 eh soh considerar todos os (poucos) casos possiveis e
confirmar que eh verdade.
Suponha valido para inteiros menores ou iguais a n, e consideremos o caso
n+1.

1) Se #X eh nao nulo, entao toda a diagonal externa x+y=n eh B (de fato, se
(a,n-a) = R, entao todos abaixo dele sao R e nessa reta x=a nao existe
nenhum pto B).
Apagando essa diagonal, note que o que sobre eh uma configuracao valida em
T_n e portanto, se nessa configuracao temos P = (p0, p1, ..., p_(n-1) ) B's
nas retas x=0,1,...,n-1, teremos /P = permutacao de P B's nas retas y=0,...
Reescrevendo a diagonal soh de B's, teremos P'=(p0+1, p1+1, ..., p_(n-1) +
1, 1) associada a qtd de ptos pintados de B nas retas x=0, x=1,... x=n e /P'
= (elementos de /P somados de 1 unidade, com 1 no final), donde /P' eh uma
permutacao de P'.

2) Se #X eh nulo, entao existe k tq a reta x=k soh tem R. Apagando o
retangulo de vertices
(0,0)-(k,0)-(k,n-k)-(0,n-k), ficamos com uma configuracao valida de T_(k)
(considerada sobre um novo eixo transladado em relacao ao original e com
centro em (0, n-k+1) e outra de T_(n-k) (...centro em (k+1,0) ) nas quais
podemos aplicar a hipotese de inducao e proceder como em (1).

Isso conclui a inducao e o problema.

Abracos,
Marcio

PS: Tmb tentei o problema 3, mas o melhor que eu consegui foi verificar que
se a divisao vale para infinitos inteiros, entao o polinomio do denominador
(em a) deve dividir o polinomio do numerador.. Depois devo tentar os
problemas do 2o dia..

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================