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
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
Para [8], o N critico eh 6.
Por exemplo, {1,2,3,5,8} tem todos os pares com somas distintas (vide meu
e-mail anterior).
Por outro lado, aquele problema do tabuleiro mxn, com m = 4 e n = 2 mostra
que qualquer subconjunto de 6 (=m+n) elementos vai ter dois pares disjuntos
com mesma diferenca.
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 elementosexistem e que sao diferentes. E muita conta mas vale a
4 matches
Mail list logo
