Oi, pessoal: Aqueles problemas dos 6 matematicos / 2 temas ou 17 matematicos / 3 temas, etc. sao casos particulares do teorema de Ramsey (vide artigo do Gugu na Eureka no. 6)
Estes problemas podem ser expressos de forma mais sucinta com a linguagem de grafos. Muito informalmente, um grafo pode ser representado por um conjunto de pontos num plano (vertices) e linhas ligando pares desses pontos (arestas). Se duas arestas se cruzarem (e em certos casos isso eh inevitavel), o ponto de interseccao nao eh contado como vertice. Um grafo completo de ordem n consiste de n vertices e das Binom(n,2) = n(n-1)/2 arestas ligando cada par de vertices. Um subgrafo de um dado grafo consiste de um subconjunto dos vertices do grafo e de todas as arestas (e somente estas) pertencentes ao grafo e que ligam dois vertices quaisquer desse subconjunto. Agora, o problema dos 6 matematicos / 2 temas pode ser reformulado da seguinte forma: Prove que se pintarmos cada aresta de um grafo completo de ordem 6 com uma dentre duas cores, este grafo conterah um subgrafo monocromatico de ordem 3 (um triangulo, por assim dizer). O dos 17 matematicos / 3 temas fica: Prove que se pintarmos cada aresta de um grafo completo de ordem 17 com uma dentre tres cores, este grafo conterah um triangulo monocromatico. A mensagem anterior do Nicolau generalizou este problema aumentando o numero de cores. Dado um numero de cores, o problema eh achar o menor numero de vertices que forca a existencia de um triangulo monocromatico. Repare que, mesmo para um caso relativamente pequeno como 4 cores, o maximo que se sabe eh que o numero minimo de vertices eh maior do que 50 e menor do que 63. Essa situacao de ignorancia eh tipica da teoria de Ramsey (de novo, veja o artigo do Gugu para ter uma ideia do quao pouco se sabe). *** Uma outra forma de se generalizar o problema eh mantendo o numero de cores fixo em 2 mas exigindo-se a presenca de um subgrafo monocromatico completo de ordem maior do que 3. Chamando as cores de azul e vermelho, o menor numero de vertices necessario para garantir a presenca de um subgrafo completo azul de ordem m ou de um subgrafo completo vermelho de ordem n eh denotado por R(m,n). Por exemplo, sabe-se que R(3,3) = 6 (esse eh o caso dos 6 professores / 2 temas), R(3,4) = R(4,3) = 9 e que R(4,4) = 18. Um bom exercicio eh provar que R(4,4) <= 18. Provar a igualdade eh mais dificil. Uma forma eh exibindo um grafo completo de ordem 17, em que cada aresta eh pintada com uma dentre duas cores, e que nao contenha nenhum subgrafo monocromatico completo de ordem 4. Um abraco, 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 =========================================================================
