Re: [obm-l] Mais casas de pombos (uma ideia)

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Mais casas de pombos (uma ideia)

Um grafo eh um conjunto de pares (nao ordenados) de vertices.
Um hipergrafo eh um conjunto de n-uplas (nao ordenadas) de vertices.
Talvez seja melhor trabalhar diretamente com subconjuntos.

*****
 
Para cada N (3<=N<=4007), seja f(N) = numero de solucoes de x + y = N com x e y pertencentes a {1,2,...,2004} e x < y.
Se eu nao errei nas contas, f(N) eh dado por:
f(N) = [(N-1)/2], 
e
f(4010-N) = f(N) 
para 3 <= N <= 2005.

*****

A minha solucao parcial baseia-se na seguinte observacao:
Se os 4 numeros a < b < c < d sao tais que a + d = b + c, entao b - a = d - c.
Ou seja, se existem 4 numeros distintos tais que a soma de dois deles eh igual a soma dos outros dois, entao tambem eh verdade que a diferenca de dois deles eh igual a diferenca dos outros dois.

Dai eu usei um outro resultado que eu tinha provado ha algum tempo:
Colocando-se m + n pecas num tabuleiro m x n (no maximo uma peca em cada quadrado), sempre existirao quatro pecas que ocupam os vertices de um paralelogramo de area positiva.
(vale a pena tentar fazer esse)

A cota superior de 90 eh obtida tomando m = n = 45, e numerando os quadrados do tabuleiro de 1 a 2025 (=45*45). Repare que 45*44 = 1980 < 2004 < 2025.

[]s,
Claudio.


on 11.05.04 16:59, Johann Peter Gustav Lejeune Dirichlet at peterdirichlet2002@yahoo.com.br wrote:

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
=========================================================================r/~nicolau/olimp/obm-l.html
=========================================================================

TRANSIRE SVVM PECTVS MVNDOQVE POTIRI

CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE

Fields Medal(John Charles Fields)

N.F.C. (Ne Fronti Crede)

---

Yahoo! Messenger - Fale com seus amigos online. Instale agora!