[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [obm-l] IMO dia 1, Q1 (solucao?!)
--- Johann Dirichlet
<peterdirichlet@yahoo.com.br> escreveu: > Peguei
as provas em PS e PDF da IMO.Se alguem
> puder me dizercomo eu faço para escrever um
> arquivo PS sendo que eu so tenho os
> visualizadores. E eu consegui fazer apenas o
> problema 2 desta IMO(geometria cearense sem do
> nem piedade.Estilo problema 1 da IMO da Coreia.
> Ao contrario do Cohen.Mas afinal de onde e
que ele teve a ideia de tirar complexos ali?
>
> --- Ralph Teixeira <RALPH@fgv.br> escreveu: >
>
> 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>
> >
>
=========================================================================
>
>
>
_______________________________________________________________________
> Yahoo! PageBuilder
> O super editor para criação de sites: é grátis,
> fácil e rápido.
> http://br.geocities.yahoo.com/v/pb.html
>
=========================================================================
> 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>
>
=========================================================================
_______________________________________________________________________
Yahoo! PageBuilder
O super editor para criação de sites: é grátis, fácil e rápido.
http://br.geocities.yahoo.com/v/pb.html
=========================================================================
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>
=========================================================================