[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [obm-l] IMO dia 1, Q1 (solucao?!)
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.
--- 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>
=========================================================================