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