[obm-l] Fw: sub-seqüência de {1,...,204}

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

aqui vão, 37 elementos entre 1 e 2004 de forma que não existem a < b < c < d
com a+d = b+c.

1 2 3 5 8 13 21 30 39 53 74 95 128 152 182 212 258 316 374 413 476 531 546
608 717 798 862 965 1060 1161 1307 1386 1435 1556 1722 1834 1934

fiz uns testes com uns algoritmos aleatórios e nenhum deles deu mais que
37... será que a resposta do problema é 38?

olha o que eu estava pensando...

seja um S subcj. de [2004] em que não possamos tomar a < b < c < d com a + d
= b + c.
suponha que existam elementos a, a + k e b, b + k, com b != a, a + k
então, a + (b + k) = (a + k) + b e isso não pode ocorrer.
logo se uma diferença entre elementos de S se repete, só pode acontecer com
elementos
a, a + k, a + 2k
note que não podemos inserir a + 3k no conjunto, c.c., a + (a + 3k) = (a +
k) + (a + 2k)
ou seja, a diferença k pode aparecer no máximo 2 vezes.

eu imagino que vcs já tinha percebido isso, né?


[ ]'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
=========================================================================