La teor¨ªa de Ramsey

Vamos a hacer una pausa en nuestro periplo por el Sistema Solar en busca de agua y de vida para detenernos brevemente en el problema planteado la semana pasada.

Recordemos el problema en versi¨®n resumida: Dadas diez personas tales que en cualquier grupo de tres de ellas hay al menos dos que no se conocen, demostrar que hay al menos un grupo de cuatro personas en el que ninguna conoce a otra.

La discusi¨®n entre nuestros "usuarios destacados¡± Manuel Amor¨®s y Francisco Montesinos (ver comentarios de la semana pasada) desemboca en una pista: para resolver el problema, puede ser ¨²til abordar antes este otro:

"Demostrar que, en un grupo de seis personas, o bien hay al menos tres que se conocen entre s¨ª, o bien hay al menos tres que no se conocen entre s¨ª".

Este tipo de problemas remiten a la denominada ¡°teor¨ªa de Ramsey¡± (en honor del matem¨¢tico y fil¨®sofo brit¨¢nico Frank P. Ramsey), que estudia las condiciones que se han de cumplir para que en un conjunto dado aparezca un cierto tipo de orden. O, m¨¢s concretamente, cu¨¢ntos elementos ha de haber en un conjunto para que aparezca una determinada propiedad.

El ¡°principio del palomar¡± puede considerarse un caso sencillo de la teor¨ªa de Ramsey, ya que podemos enunciarlo as¨ª: ?Cu¨¢ntas palomas ha de haber para que, dado un conjunto de n palomares, haya al menos un palomar con m¨¢s de una paloma? La respuesta, en este caso, es obvia: ha de haber m¨¢s palomas que palomares; es decir, si llamamos m al n¨²mero de palomas, la condici¨®n pedida es m > n. Un ejemplo menos sencillo podr¨ªa ser un acertijo misantr¨®pico planteado hace unos meses en estas mismas p¨¢ginas: Si el 70% de los hombres son feos, el 70% son tontos y el 70% son malos, ?cu¨¢l ser¨¢, como m¨ªnimo, el porcentaje de hombres que re¨²nan las tres ¡°cualidades¡±, es decir, que sean a la vez feos, tontos y malos?

El teorema de la amistad

El problema de las seis personas antes enunciado es, en realidad, todo un teorema, conocido como ¡°teorema de la amistad¡±, y tambi¨¦n como ¡°teorema de amigos y desconocidos¡±.

Un grupo de seis personas en el que cada una se relaciona de alguna manera con cada una de las dem¨¢s, se puede representar esquem¨¢ticamente mediante un hex¨¢gono con todas sus diagonales. En teor¨ªa de grafos, es un grafo completo, pues cada nodo (cada v¨¦rtice del hex¨¢gono) est¨¢ unido a todos los dem¨¢s. Pues bien, si las personas que se conocen las unimos con un trazo rojo y las que no se conocen con un trazo azul, el teorema de la amistad demuestra que habr¨¢ al menos un tri¨¢ngulo rojo o un tri¨¢ngulo azul (es decir, un grupo de tres conocidos o un grupo de tres desconocidos). ?C¨®mo se demuestra? Y si hubiera solo cinco personas, ?podr¨ªamos afirmar lo mismo?

El ¡°problema del final feliz¡±, denominado as¨ª por Paul Erd?s (por razones extramatem¨¢ticas), est¨¢ estrechamente relacionado con la teor¨ªa de Ramsey, y dice as¨ª:

Cualquier conjunto de cinco puntos en el plano en posici¨®n general (sin que haya tres o m¨¢s en l¨ªnea recta) tiene un subconjunto de cuatro puntos que son los v¨¦rtices de un cuadril¨¢tero convexo.

Pero ese es otro art¨ªculo.

Carlo Frabetti?es escritor y matem¨¢tico, miembro de la Academia de Ciencias de Nueva York. Ha publicado m¨¢s de 50 obras de divulgaci¨®n cient¨ªfica para adultos, ni?os y j¨®venes, entre ellos?Maldita f¨ªsica, Malditas matem¨¢ticas?o?El gran juego. Fue guionista de?La bola de cristal.