Teorema de la amistad

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.

Para analizar el problema podemos realizar 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.

grafo amistad

Se observa que en todas las representaciones no se puede evitar que exista un triángulo rojo o un triángulo azul, es decir, tres personas mutuamente extrañas o tres personas mutuamente conocidas, lo cual demuestra el teorema.

Otra forma de abordar el problema es utilizando el Principio del Palomar. Elijamos uno de los vértices. Hay cinco aristas incidentes en ese vértice, cada una coloreada con el color rojo o azul. Pues bien, de esas cinco necesariamente tres aristas deben ser del mismo color, ya sea azul o roja.

El Teorema de la amistad apareció por primera vez en 1930, en un trabajo titulado «On a Problem in Formal Logic» (Sobre un problema en lógica formal), donde Frank P. Ramsey demostró un teorema más general, conocido en la actualidad como Teorema de Ramsey en el que el Teorema de la amistad es un caso particular. Frank Plumpton Ramsey (1903- 1930) fue un matemático y filósofo inglés que hizo importantes contribuciones teóricas a la matemática, la estadística y la economía. La inteligencia de Ramsey impresionó de forma temprana a los académicos de Cambridge: se graduó con la máxima calificación de su promoción, fue capaz de aprender alemán en tan sólo una semana y accedió como profesor al King’s College con tan solo 21 años. Desgraciadamente sufría una dolencia crónica de riñón y tras una operación murió a la edad de 26 años, acabando con una prometedora carrera.

Frank_Plumpton_Ramsey

Frank P. Ramsey

SI TE HA GUSTADO, COMPÁRTELO:

Add to FacebookAdd to DiggAdd to Del.icio.usAdd to StumbleuponAdd to RedditAdd to BlinklistAdd to TwitterAdd to TechnoratiAdd to Yahoo BuzzAdd to Newsvine

Anuncios

2 comentarios (+¿añadir los tuyos?)

  1. Josep M.
    Ago 04, 2015 @ 12:22:52

    Sugiero cambiar el título de esta entrada, que lleva a confusión. Existe un teorema de la amistad (“Friendship Theorem”) que no està relacionado con el resultado que se comenta, aunque también pertence a la teoria de grafos. En términos coloquiales el teorema de la amistad es el siguiente: si en una reunión de n personas cada dos persones tienen exactamente un conocido en común, entonces hay alguien que conoce a todo el mundo.

    Responder

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s