ok, matei o problema!!!
o valor cr�tico � 65!!!
aqui eu demonstro que o limitante superior � 65, supondo que vcs
demonstraram corretamente que o limite inferior � 65, acabou!
Seja S = {s_1, ..., s_n} contido em {1,2,3, ..., 2004}
com s_1 < s_2 < ... < s_n
defina d_i = s_{i+1} - s_i, i = 1..n-1
se para algum i, d_i = d_{i+j} com j >= 2
s_{i+1} - s_i = s_{i+j+1} - s_{i+j}
<=> s_{i+j} + s_{i+1} = s_{i+j+1} + s_i
i < i + 1 < i+j < i+j+1 e portanto temos 4 elementos em S do jeito que
queremos.
supondo que n�o tenhamos isso...
seja 1 <= i < i + j < k < k + m <= n
veja que
s_i + s_{k+m} = s_{i+j} + s_k <=>
s_{k+m} - s_k = s_{i+j} - s_i <=>
(s_{k+m} - s_{k+m-1}) + (s_{k+m-1} - s_{k+m-2}) ... + (s_{k+1} - s_k) =
(s_{i+j} - s_{i+j-1}) + ... + (s_{i+1} - s_i) <=>
d_{k+m-1} + d_{k+m-2} + ... + d_k = d_{i+j-1} + ... + d_i
portanto provamos que duas somas consecutivas de elementos de {d_i},
isoladas, n�o podem ser iguais.
fixe um inteiro i > 1 e suponha a < i, b >= i com
(1) d_a + ... + d_{i-1} = d_i + ... + d_b de forma que b - a � m�ximo
suponha que tenhamos tamb�m a' < i, b' >= i com
d_{a'} + ... + d_{i-1} = d_i + ... + d_{b'}
n�o podemos ter b' > b, pois o lado direito da soma seria maior que (1) e o
lado esquerdo s� poderia aumentar de tamanho contrariando a hip�tese de b -
a ser m�ximo.
se i <= b' < b, a < a' < i e a� devemos ter
d_a + ... + d_{a' - 1} = d_{b' + 1} + ... + d_b, o que � absurdo, pois essas
s�o duas somas consecutivas isoladas.
ent�o mostramos que para i = 2,..., n h� no m�ximo 2 sub-seq��ncias
consecutivas de mesma soma...
temos um total de Binomial(n-1, 2) subseq��ncias poss�veis (basta escolher
um �ndice para o come�o e outro para o final) e no m�ximo n-1 s�o contadas
duas vezes, ou seja, temos pelo menos Binomial(n-1, 2) + 1 - n subseq��ncias
consecutivas com somas DISTINTAS, note que tais somas representam dist�ncias
entre elementos de S e, como no nosso caso, S contido em {1,..., 2004}, h�
2003 poss�veis diferen�as logo,
Binomial(n-1, 2) + 1 - n <= 2003
(n-1)(n-2)/2 + (1-n) <= 2003
(n-1)(n-4) <= 4006
n <= 65
[ ]'s
=========================================================================
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
=========================================================================
