Re: [obm-l] Mais casas de pombos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Uma cota inferior para N, provavelmente bem fraca, eh dada pelos numeros de
Fibonacci: {1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597} eh um
subconjunto de {1,2,...,2004} em que cada par tem uma soma distinta.
Ou seja, N >= 17.

Eh facil ver que cada par de {1,2,3,5} tem uma soma distinta.
Agora adicione o 8 para obter {1,2,3,5,8}.
A menor soma da qual 8 participa eh 9 = 1 + 8.
Por outro lado, a maior soma que nao envolve 8 eh 8 = 3 + 5.
Logo, ao adicionar o 8 nao repetimos nenhuma soma.
O raciocinio (indutivo) eh analogo para cada novo numero de Fibonacci
adicionado.

*****

Como a + d = b + c <==> b - a = d - c, podemos raciocinar com diferencas ao
inves de somas. No caso, temos 2003 diferencas possiveis
(1 = 2-1 = ... = 2004-2003  ateh  2003 = 2004-1)

Alem disso, Binom(63,2) = 1953 < 2003 < 2016 = Binom(64,2).
Isso implica que se escolhermos 64 elementos de {1,2,...,2004}, teremos mais
pares do que diferencas possiveis.
Infelizmente, podemos ter dois pares da forma {a,b} e {b,c} com b-a = c-b, o
que contraria o enunciado.
Portanto, nao podemos concluir que N <= 64.

[]s,
Claudio.
 
on 11.05.04 17:48, João Gilberto Ponciano Pereira at jopereira@vesper.com.br
wrote:

> Tenho uma idéia...
> Vamos pensar pequeno primeiro, um conjunto de 3 números (A, B, c), tal que
> A+B <> A+C <> B+C. Um exemplo seria o conjunto (1, 2, 4), e o número de
> somas diferentes seria o binomial (3,2).
> Para 4, um exemplo seria (1,2,4,7), e o número de somas seria o binomial
> (4,2), e a soma máxima seria 4+7 = 11.
> 
> Ora, se formos considerar um conjunto com N elementos, e nenhum deles é
> maior que 2004, podemos concluir que a soma máxima de dois elementos de M é
> 4005, logo, dado um conjunto N, podemos ter 4005 combinações diferentes.
> 
> Fazendo as contas, já podemos concluir que N =< 90.
> Mas isso ainda não prova nada, é só um limitante. Acho que o Cláudio pensou
> em algo parecido.
> 
> -----Original Message-----
> From: Johann Peter Gustav Lejeune Dirichlet
> [mailto:peterdirichlet2002@yahoo.com.br]
> Sent: Tuesday, May 11, 2004 5:00 PM
> To: obm-l@mat.puc-rio.br
> Subject: Re: [obm-l] Mais casas de pombos (uma ideia)
> 
> 
> Ola Claudio!
> estou tentando analisar casos pequenos nesse problema.
> Minha ideia e tentar escrever isto com linguagem de grafos. O problema e que
> eu nao sei como observar hipergrafos :(
> Outra ideia e calcular quantas somas de dois elementos existem e que sao
> diferentes. E muita conta mas vale a pena...
> PS.: Passa a sua demo pra gente tentar melhorar...
> 
> Claudio Buffara <claudio.buffara@terra.com.br> wrote:
> 
> Oi, Fred (e demais colegas):
> 
> Jah que estamos nesse assunto, aqui vai um problema que ainda estah em
> aberto na lista:
> 
> Ache o menor inteiro N tal que dados quaisquer N elementos distintos do
> conjunto {1,2,3,...,2004}, existem 4 elementos distintos dentre os N tais
> que a soma de dois deles eh igual a soma dos outros dois.
> 
> Por enquanto, eu soh consegui provar que o N critico eh <= 90.
> 
> []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
=========================================================================