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

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

Por enquanto fiz isso aqui para o caso 8:
Seja [n]={1,2,...,n}
Este e o conjunto [8]: 1,2,3,4,5,6,7,8

Estes sao os conjuntos proibidos:

1,2,3,4
1,2,4,5
1,2,5,6
1,2,7,8
1,3,4,6
1,3,5,7
1,3,6,8
1,4,5,8
2,3,4,5
2,3,5,6
2,3,6,7
2,3,7,8
2,4,5,7
2,4,6,8
3,4,5,6
3,4,6,7
3,4,7,8
3,5,6,8
4,5,6,7
4,5,7,8
5,6,7,8

Sabemos que sao permitidos no maximo 3 elementos
de cada conjunto proibido. A cada numero que
escolhemos (o 1 por exemplo) apagamos ele de
todos os conjuntos. So pode sobrar um de cada
conjunto.
Ai eu cheguei em algo meio tosco...

 --- Claudio Buffara
<claudio.buffara@terra.com.br> escreveu: > 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!
> 
> 
>  

=====
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! 
http://br.download.yahoo.com/messenger/
=========================================================================
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
=========================================================================