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

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 17.05.04 18:05, Qwert Smith at lord_qwert@hotmail.com wrote:

> 
>> 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}
> 
Oi, Auggy:

Concordo com o que voce disse.
Voce consegue exibir 9 elementos de {1,2,...,30} tais que quaisquer dois
pares disjuntos desses elementos tem somas distintas?

Alem disso, o seu argumento reduz o limitante superior do N critico de
{1,2,...,2004} para 64.

O problema eh que ninguem conseguiu obter um subconjunto de 38 elementos com
todas as somas distintas. E de 38 ateh 64 tem um belo gap.


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