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