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

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 14.05.04 18:28, Domingos Jr. at dopikas@uol.com.br wrote:

> 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
> 
Oi, Domingos:

Li e reli o seu argumento e nao achei nenhum furo.
Se estiver mesmo OK (colegas da lista, por favor deem sua opiniao tambem),
ele terah sido um grande passo pra solucao.

Infelizmente, como o Auggy apontou, o limitante inferior de 65 estava
errado.
Logo, estamos com 38 <= Ncritico <= 66 (os dois limitantes sao seus).

Mas a melhor noticia eh que esse estah sendo um problema dificil no qual
varios participantes da lista estao pensando. Acho que isso eh um exemplo de
como essa lista pode ser interessante e valiosa.

[]s,
Claudio.


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