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

[Ralph Teixeira <RALPH@xxxxxx>]

    Estah correto...

    Mas soh para voces terem uma ideia de como o pessoal lah era rigoroso,
esta solucao valeria 6 pontos.

    O pequeno detalhe que estah faltando eh o seguinte. NO caso (2),
dividimos a inducao em T_{k} e T_{n-k} e, por inducao acabou, certo? Bom,
nao exatamente... Note que poderiamos ter k=0 ou k=n, e um dos triangulos
simplesmente nao teria ponto algum. Entao estah faltando uma das duas
coisas:

    (i) Ou voce cita o caso T_{0} explicitamente e nota que tambem vale a
tal proposicao (voce soh citou T_1 e T_2)...
    (ii) ...ou voce separa o caso 2 em 2(a) (que vira dois triangulos) e
este caso especial (onde ha de fato um triangulo soh T_{n}).

    Eles nao queriam uma demonstracao complicada destas coisas, que sao de
fato obvias. O que eles querem eh uma *mencao* de que este caso (o
"triangulo vazio") existia e nao se enquadrava perfeitamente na inducao. No
criterio de correcao, nao fazer o caso T_0 era um erro mais ou menos
semelhante a esquecer o caso inicial de uma inducao... e por isso perdia-se
um ponto (o que explica a grande quantidade de "6" desta questao).

    Abraco,
         Ralph


-----Original Message-----
From: Marcio
To: obm-l@mat.puc-rio.br
Sent: 7/27/02 9:18 AM
Subject: [obm-l] IMO dia 1, Q1 (solucao?!)

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