[obm-l] IMO 2003 -- Problema 1

["Fábio Dias Moreira" <fabio.dias.moreira@xxxxxxxxxxxx>]

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