Re: [obm-l] IMO_2003_--_Problema_1(quem fez o 3?)

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

E,realmente,o problema parece extremamente
folgado...Mas e uma folga beeeem esquisita.Minha
soluçao ficou parrecida com a do Marcio Cohen mas
nao pensei em apertar muito,apesar de o numero
parecer crescer descontroladamente.Talvez olhar
nao mude muito...

Quem fez o tres???

 --- Fábio_Dias_Moreira
<fabio.dias.moreira@terra.com.br> escreveu: > Oi
pessoal,
> 
> Acabei de chegar do Japão, e dei uma olhada
> rápida nos emails da lista. Eu li as soluções
> do P1 da IMO, que estão na linha da solução do
> Alex. Eu acabei descobrindo sem querer na prova
> que o problema é muito folgado, se as escolhas
> dos ti's forem apropriadas.
> 
> Tome dA = {x-y|x>y, x e y elementos de A}. |dA|
> <= 5050.
> 
> Tome t1 = 1. Marque como proibidos todos os
> inteiros da forma 1+dA, i.e. da forma 1+x com x
> em dA. Tome o menor elemento de S que ainda não
> foi proibido e chame-o de t2. Proíba todo mundo
> da forma t2+dA. Tome o menor elemento de S não
> proibido de t3. (...)
> 
> É impossível que tj-ti esteja em dA, com j>i,
> pois então tj>ti, logo tj = ti+x, x em dA,
> *absurdo*, pois então tj teria sido proibido,
> por construção. Logo basta verificar que todos
> os ti's estão 
> 
> Mas há no máximo 5050 proibidos e 1 escolhido
> antes de t2, logo t2 <= 5051; t3 <= 10102; ...;
> t100 <= 5051*99 = 500049 << 10^6.
> 
> (Um subproblema: Seja A um conjunto de inteiros
> positivos tal que |dA| = n. Quanto vale k, o
> valor mínimo de max(A)? Eu acho que n = 5050 =>
> k > 10^6, mas não pensei a fundo no problema.
> Se isso for verdade, o problema é mais folgado
> ainda.)
> 
> []s,
> 
> -- 
> Fábio "ctg \pi" Dias Moreira
> 
>
=========================================================================
> 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
>
========================================================================= 

_______________________________________________________________________
Yahoo! Mail
Mais espaço, mais segurança e gratuito: caixa postal de 6MB, antivírus, proteção contra spam.
http://br.mail.yahoo.com/
=========================================================================
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
=========================================================================