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 é <[EMAIL PROTECTED]> =========================================================================
