Teorema de la amistad

Teorema de la amistad
Los 78 grafos posibles de amigos-extraños con 6 vértices. En cada grafo, las aristas de color azul/rojo muestran la relación mutua de amigos/extraños.

El teorema de amigos y extraños o teorema de la amistad es un teorema en el campo matemático llamado teoría de Ramsey.

Contenido

Formulación del teorema

Supongamos que en una fiesta hay 6 personas. Consideremos a cualquiera dos de ellos. Puede ser que se reúnen por primera vez, en cuyo caso son mutuamente extraños, o puede ser que se hayan conocido antes, en cuyo caso se les llamará mutuamente conocidos. Ahora, el teorema de la amistad nos dice que:

En cualquier grupo de seis personas, existen tres personas que son mutuamente conocidas o mutuamente desconocidas.

Conversión a grafos

Es conveniente expresar este problema usando el lenguaje de teoría de grafos.

Supongamos que un grafo tiene 6 vértices y cada par de vértices está unido por una arista. Este grafo se llama grafo completo. Un grafo completo de n vértices se denota por K_n \,. En el caso de un grafo de 3 vértices y en donde cada vértice es adyacente a los demás, se trata del grafo completo K_3 \, o del ciclo de longitud 3: C_3 \,, comúnmente llamado triángulo.

Ahora tomemos un K_6 \,. Este grafo completo tiene 15 aristas en total. Sean las 6 personas de la fiesta representadas por los 6 vértices. Sean las aristas coloreadas con los colores rojo o azul dependiendo de si las dos personas representadas por los vértices incidentes a la arista son mutuamente conocidos o desconocidos, respectivamente. El teorema de la Amistad afirma ahora:

No importa cómo se ha coloreado las aristas de K_6 \, con los colores rojo o azul, no se puede evitar que exista un triángulo rojo, es decir, un triángulo que tenga sus tres lados de color rojo, lo que representa tres personas mutuamente extrañas o un triángulo azul, que representan tres personas mutuamente conocidos.

Prueba

Elijamos uno de los vértices P. Hay cinco aristas incidentes a P, cada una coloreada con el color rojo o azul. Según el principio del palomar, al menos tres aristas deben ser del mismo color, porque si hay menos de tres de un solo color, por ejemplo roja, entonces hay al menos tres que son de color azul.

Sean A, B, C, los otros vértices extremos de estas tres aristas, todas del mismo color, por ejemplo azul. Si alguna de las aristas AB, BC, CA es azul, entonces esta arista junto con las dos aristas incidentes a P forman los lados de un triángulo azul. Si ninguna de las aristas AB, BC, CA es azul, entonces las tres aristas son de color rojo y tenemos un triángulo rojo de vértices ABC.

Trabajo de Ramsey

La total simplicidad de este argumento, que produce con tanta fuerza una interesante conclusión, es lo que hace atractivo este teorema. En 1930, en un trabajo titulado «On a Problem in Formal Logic» (Sobre un problema en lógica formal), Frank P. Ramsey demostró un teorema muy general, conocido en la actualidad como Teorema de Ramsey en el que el teorema de la amistad es un caso particular. El teorema de Ramsey es la base en la que sostiene el área de la combinatoria conocida como teoría de Ramsey.

Ámbito del teorema de la amistad

Un coloreado de dos colores de K5 sin un K3 monocromo.

La conclusión del teorema de la amistad no se tiene en grupos de menos de seis personas. Para demostrar esto, se colorea K5 de rojo y azul de forma que no contenga un triángulo cuyos lados sean todos del mismo color. Dibujamos K5 como un pentágono que rodea una estrella y coloreamos de rojo los lados del pentágono y de azul los de la estrella. Por lo tanto, 6 es el mínimo número para el cual se puede dar por buena la conclusión del teorema de la amistad. En la teoría de Ramsey, esto se denota por:

R(3,3: 2) = 6.\,

Referencias

  • V. Krishnamurthy. Culture, Excitement and Relevance of Mathematics, Wiley Eastern, 1990. ISBN 81-224-0272-0.

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Teoría de Ramsey — Según la teoría de Ramsey, del total de estrellas del cielo nocturno, siempre podemos seleccionar un subconjunto de ellas para dibujar diferentes objetos como: un triángulo, un cuadrilátero, un paraguas o un pulpo. La teoría de Ramsey, llamada… …   Wikipedia Español

  • Coloración de grafos — Una vértice coloración propia del grafo de Petersen con 3 colores, el número mínimo posible. En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del …   Wikipedia Español

  • Kurt Gödel — Para el lenguaje de programación, véase Gödel (lenguaje de programación). Kurt Gödel Kurt Gödel Nacimiento 28 de abril …   Wikipedia Español

  • Emmy Noether — Amalie Emmy Noether Nacimiento 23 de marzo de 1882 Erlangen, Baviera, Alemania Fallecimiento …   Wikipedia Español

  • Jean Paul de Gua de Malves — Nacimiento 1712 Carcasona, Francia Fallecimiento 2 de junio de 1786 París, Francia Residencia Francia …   Wikipedia Español

  • Homosexualidad en el cine — La homosexualidad en el cine ha sido retratada de maneras muy diversas dependiendo de la época, del país, o de la mirada personal del director. Se ha reflejado en comedias, cine experimental, de terror, histórico, policiaco, de denuncia social,… …   Wikipedia Español

  • Paul Erdős — Saltar a navegación, búsqueda Paul Erdős Paul Erdős en un seminario de estudiantes, Budapest, 1992 …   Wikipedia Español

  • Anexo:Episodios de The Big Bang Theory — Esta lista contiene información en forma cronológica sobre los capítulos y temporadas de la serie de televisión norteamericana The Big Bang Theory. La serie comenzó el 24 de septiembre de 2007 con el episodio Pilot . La segunda temporada comenzó… …   Wikipedia Español

  • Isaac Newton — Para otros usos de este término, véase Newton. Sir Isaac Newton …   Wikipedia Español

  • Mijaíl Ostrogradski — Mijaíl Ostrogradski. Mijaíl Vasílievich Ostrogradski (Михаил Васильевич Остроградский) (Pachenna, Ucrania, 1801 Poltava, Ucrania, 1861), fue un físico y matemático ucraniano. Empezó sus estudios de matemáticas en la Universidad de Járkov, y los… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”