Thread by @pgroisma

#TeRegaloUnTeorema abandona el letargo para decirte que te cuides del Corona y que no hagas reuniones con mucha gente, porque te puede pasar esto

🆃🅴🅾🆁🅴🅼🅰
En cualquier fiesta con más de 5 personas pasa una de las siguientes cosas 👇

(a) Hay al menos 3 que se conocen todos entre sí,

o

(b) Hay al menos 3 que no se conocen entre sí (ninguno con ninguno).

Antes de la demo, bancarse el chamuyo.

El teo se lo debemos a Ramsey, es un poco más general y dice que para cualquier número k, existe un tamaño de reunión N, tal que si la reunión tiene al menos N personas, entonces pasa (a) o (b) (cambiando 3 por k).

Por ejemplo, en cualquier fiesta con más de 47 personas

(a) Hay al menos 5 que se conocen todos entre sí, o
(b) Hay al menos 5 que no se conocen entre sí (ninguno con ninguno).

Peeero, cuál es la fiesta más pequeña para la cual podemos asegurar que sí o sí pasa a) o b) con k=5?

Eso no lo sabemos. Al número ese se lo llama número de Ramsey y se lo escribe R(5,5).

El teorema del principio dice que R(3,3) es a lo sumo 6 (vamos a ver que es exactamente 6).

Como les decía, R(5,5) no lo conocemos, pero en 2017 Angeltveit y McKay probaron que es a lo sumo 48. Al respecto, el gran Erdös (que estaba muy involucrado con este tipo de problemas) decía...

“Imagínense que una fuerza alienígena, mucho más poderosa que nosotros, llega a La Tierra y nos exige el valor de R(5,5) a cambio de no destruir el planeta. En ese caso deberíamos juntar todas nuestras computadoras y a todos nuestros matemáticos y tratar de calcularlo.

Pero...

... si nos pide R(6,6), deberíamos tratar de destruir a los aliens.”

Erdös trataba de ejemplificar cómo crece la complejidad del problema al pasar de R(5,5) a R(6,6).

Basta de cháchara y a la prueba.

🅳🅴🅼🅾🆂🆃🆁🅰🅲🅸🅾🅽

La hacemos para una fiesta con 6 personas. Si hay más, mejor para nosotros. Agarremos a un invitado en particular (Juan, ponele) y analicemos su relación con los otros 5 invitados. Sí o si tiene que pasar que

I. Al menos 3 son conocidos (de Juan)
o
II. Al menos 3 son extraños (para Juan).

Supongamos que pasa (I) (si pasa II se procede de manera similar) y llamemos Vera, Ana y Santi a los tres conocidos de Juan. Analicemos las relaciones entre Vera, Ana y Santi.

Si ninguno de ellos se conoce entre sí, encontramos un grupo de 3 en que no se conocen entre sí y listo (ganamos!). Pero si ese no es el caso, tiene que pasar que al menos dos de ellos se conocen entre sí. Y ambos conocen también a Juan.

O sea que encontramos tres que se conocen todos entre sí y también ganamos! Listo!

Ah! Esto demuestra que R(3,3) es a lo sumo 6, para ver que no puede ser menor que 6, les dejo este dibujito para pensar.

#TeRegaloUnTeorema, #TeRegaloUnProblema.