[obm-l] Teoria de Ramsey

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Oi, pessoal:

Esse eh um assunto bem interessante e relevante para quem tem interesse em
olimpiadas de matematica. A teoria de Ramsey, baseada num teorema
demonstrado pelo matematico/economista ingles Frank Ramsey em 1930, pode ser
vista como a extensao natural do principio das casas de pombos para
situacoes mais complexas.

O exemplo mais simples dessa teoria eh o fato de que numa reuniao de 6
pessoas, existem 3 que se conhecem mutuamente ou 3 que se desconhecem
mutuamente (ou ambos). Por outro lado, se a reuniao tiver apenas 5 pessoas,
isso pode nao acontecer.

Surpreendentemente, o teorema de Ramsey implica que existe um numero natural
N tal que numa reuniao de N pessoas, existem 5 que se conhecem mutuamente ou
5 que se desconhecem mutuamente. No entanto, ateh hoje ninguem conseguiu
descobrir o menor valor de N para o qual isso acontece. O maximo que se sabe
eh que esse valor critico de N eh maior do que 42 e menor do que 50.

Existe um belo artigo introdutorio escrito pelo Gugu na Eureka no. 6, o qual
contem referencias bibliograficas pra quem quiser se aprofundar.

O artigo:
www.dpmms.cam.ac.uk/~bjg23/papers/gazette.ps
trata de algumas ocorrencias da teoria de Ramsey nas olimpiadas
internacionais.

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
=========================================================================