Re: [obm-l] 9 elementos de {1,2,...,25}

["Qwert Smith" <lord_qwert@xxxxxxxxxxx>]

>Algum consegue provar (ou dar um contra-exemplo) que qualquer subconjunto 
>de
>9 elementos de {1,2,...,25} possui quatro elementos tais que a soma de dois
>deles eh igual a soma dos outros dois?
>
>Com 8 elementos, isso nem sempre acontece. Ex: {1,2,3,5,9,15,20,25}.
>
>Repare que uma forma de proceder eh testar 2.042.975 subconjuntos...

Ki tal assim:

Temos um maximo de 24 diferencas possiveis entre cada 2 numeros de 
{1,2...24,25}

Seja T(x) o numero total de diferencas observadas num cunjunto de x 
elementos
(nao necessariamente distintas).

T(1) = 0
T(2) = 1
T(3) = 3
T(x) = Somatorio(1 to x-1)
T(8) = 28
T(9) = 36

A solucao otima e a que se vale do maximo possivel de diferencas repetidas
como ( a, a+x, a+2x)

M(x) = maximo possivel de repeticoes
M(3) = 1
M(4) = 2
M(x) = x-2
M(8) = 6
M(9) = 7

Entao na melhor das hipoteses para x elementos teremos
F(x) = T(x) - M(x) = x(x-1)/2 - (x-2)
Para x = 8   =>28 - 6 = 22 ( que e o caso do exemplo )
Para x = 9  => 36 - 7 = 29.
Como o maximo de diferencas distintas de {1,2...24,25] eh 24
e o melhor possivel com 9 elementos e 29 vemos que sempre ha
diferencas repetidas em excesso ao maximo possivel.

A diferenca aki e ki temos um exemplo de que f(8) ideal ou seja 22
eh possivel... nao sei como provar ki tal ideal e sempre possivel, e usar no
problema de [1,2...2003,2004}

_________________________________________________________________
Stop worrying about overloading your inbox - get MSN Hotmail Extra Storage! 
http://join.msn.click-url.com/go/onm00200362ave/direct/01/

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