[obm-l] Re: [obm-l] Fw:_sub-seq üência_de_{1,...,204}(*um problema parecido na Ibero*)

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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