El teorema de amigos y extraños es un teorema matemático en un área de las matemáticas llamada teoría de Ramsey .
Declaración
Supongamos que una fiesta tiene seis personas. Considere dos de ellos. Es posible que se conozcan por primera vez, en cuyo caso los llamaremos extraños mutuos; o podrían haberse conocido antes, en cuyo caso los llamaremos conocidos mutuos. El teorema dice:
- En cualquier grupo de seis personas, al menos tres de ellos son (por parejas) extraños mutuos o al menos tres de ellos son conocidos mutuos (por parejas).
Conversión a una configuración teórica de gráficos
Una demostración del teorema no requiere nada más que una lógica de tres pasos. Es conveniente formular el problema en lenguaje teórico de grafos.
Suponga que una gráfica tiene 6 vértices y cada par de vértices (distintos) está unido por una arista. Esta gráfica se llama gráfica completa (porque no puede haber más aristas). Un gráfico completo en vértices se denota con el símbolo .
Ahora toma un . Tiene 15 aristas en total. Dejemos que los 6 vértices representen a las 6 personas de nuestro grupo. Dejemos que los bordes sean de color rojo o azul dependiendo de si las dos personas representadas por los vértices conectados por el borde son extraños o conocidos mutuos, respectivamente. El teorema ahora afirma:
- No importa cómo coloree los 15 bordes de un con rojo y azul, no puede evitar tener un triángulo rojo, es decir, un triángulo cuyos tres lados son rojos, que representan tres pares de extraños mutuos, o un triángulo azul, que representa tres pares de conocidos mutuos. En otras palabras, independientemente de los colores que utilice, siempre habrá al menos un triángulo monocromático (es decir, un triángulo cuyos bordes tengan el mismo color).
Bosquejo de una prueba
Elija cualquier vértice; llamarlo P . Hay cinco bordes dejando P . Cada uno es de color rojo o azul. El principio del casillero dice que al menos tres de ellos deben ser del mismo color; porque si hay menos de tres de un color, digamos rojo, entonces hay al menos tres que son azules.
Sean A , B , C los otros extremos de estos tres bordes, todos del mismo color, digamos azul. Si alguno de AB , BC , CA es azul, entonces ese borde junto con los dos bordes desde P hasta los extremos del borde forma un triángulo azul. Si nada de AB , BC , CA es azul, entonces los tres bordes son rojos y tenemos un triángulo rojo, a saber, ABC .
El papel de Ramsey
La absoluta sencillez de este argumento, que produce con tanta fuerza una conclusión muy interesante, es lo que hace atractivo el teorema. En 1930, en un artículo titulado "Sobre un problema de lógica formal", Frank P. Ramsey demostró un teorema muy general (ahora conocido como teorema de Ramsey ) del que este teorema es un caso simple. Este teorema de Ramsey forma la base del área conocida como teoría de Ramsey en combinatoria .
Límites del teorema
La conclusión del teorema no se cumple si reemplazamos el grupo de seis personas por un grupo de menos de seis. Para mostrar esto, damos una coloración de K 5 con rojo y azul que no contiene un triángulo con todos los bordes del mismo color. Dibujamos K 5 como un pentágono que rodea una estrella (un pentagrama ). Coloreamos los bordes del pentágono de rojo y los bordes de la estrella de azul. Por tanto, 6 es el número más pequeño para el que podemos afirmar la conclusión del teorema. En la teoría de Ramsey, escribimos este hecho como:
Referencias
- V. Krishnamurthy. Cultura, entusiasmo y relevancia de las matemáticas, Wiley Eastern, 1990. ISBN 81-224-0272-0 .
enlaces externos
- Conocidos de la fiesta en cut-the-knot (requiere Java)