on 14.05.04 18:28, Domingos Jr. at [EMAIL PROTECTED] 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
=========================================================================
