Solución: el problema de la fiesta

A continuación mostramos la solución al divertimento «El problema de la fiesta». Gracias a Alberto Castaño por la solución que ha aportado.

Divertimento: Se convoca una fiesta mediante las redes sociales a la que acuden doscientas personas, que pueden conocerse o no. Suponemos que si la persona A conoce a B, entonces B también conoce a A.

Justifica que hay al menos dos personas que conocen al mismo número de personas en la fiesta.

Justifica también que, si de entre las doscientas personas se escoge un grupo cualquiera de seis, hay al menos tres de ellas que se conocen entre sí o bien que no se conocen ninguna entre sí.

Si el lector sabe calcular cuál es el mínimo número de personas que hay que seleccionar para que obligatoriamente haya seis de ellas que o se conozcan todas entre sí o no se conozcan ninguna de ellas entre sí, que se ponga urgentísimamente en contacto con el IMUS.

Solución:

Supongamos que, de las 200 personas, una no conoce a ninguna de las 199 restantes; por tanto ninguna de estas la conoce a ella. De modo que cada una las personas conoce entre 0 y 198 personas. Si asociamos a cada una de las 200 personas el número de sus conocidos (que oscila entre 0 y 198), tiene que haber 2 con el mismo número de conocidos. Por otra parte, si todo el mundo conoce a alguien, se asocia a cada persona el número de sus conocidos, que ahora oscila entre 1 y 199, y se concluye igual.

Se selecciona un grupo de seis personas cualesquiera. Se escoge una de ellas, A, y se separan las otras cinco en dos grupos: los que conocen a la persona A y los que no. Uno de estos grupos tienen al menos 3 personas. Si el grupo con tres o más personas es el de los que conocen a A, puede ser que dos se conozcan, en cuyo caso estas dos y A forman las tres personas que se conocen. Si no hay dos que se conocen, es que hay al menos tres desconocidos. Si el grupo con más de tres personas es el de las que no conocen a A, puede ser que haya 3 que se conozcan entre sí, o bien que haya 2 que no se conocen, que junto con A forman la terna de desconocidos.

Este tipo de problemas permite definir los números de Ramsey : dados dos números \(n\) y \(m\) el número de Ramsey \(R(n,m)\) se define como el mínimo número entero \(N\) tal que en una reunión de \(N\) personas siempre hay \(n\) que se conocen entre sí o \(m\) que no se conocen entre sí. En el párrafo anterior se ha demostrado que \(R(3,3)\le 6\). No es difícil probar que en realidad \(R(3,3)=6\). Se sabe que los números de Ramsey son siempre finitos, pero muy poco más acerca de ellos. Por ejemplo, sabemos que \(R(4,4)=18\), \(R(4,5)=25\), pero no sabemos el valor de \(R(5,5)\), aunque sí que \(43 \le R(5,5) \le 49\). El matemático Paul Erdös decía que si vinieran unos extraterrestres con la amenaza de que destruirían el planeta si no le decíamos cuánto vale \(R(5,5)\), pondríamos a trabajar todos nuestros ordenadores, pero si lo que nos pidieran fuera \(R(6,6)\) más bien deberíamos de pensar en cómo destruirlos a ellos.

Para saber más: