[TitoNathan]

Buenas, estoy estudiando Técnicas de recuento y me he encontrado con este problema que no tengo ni idea de cómo afrontar:

Demostrar que en un conjunto de seis personas hay tres que se conocen mutuamente o tres mutuamente extrañas.

Mirando en internet he descubierto que es un problema famoso, sin embargo, en todos los sitios se demuestra mediante un grafo y aristas y yo aún no he estudiado el tema de la teoría de grafos (si es que tiene algo que ver) y en el tema de técnicas de recuento no viene nada tampoco de estos grafos.
No habría otra forma de demostrar esto?

[Fallen Angel]

Hola!

Lo cierto es que no se me ocurre cómo probarlo sin utilizar algún resultado de grafos. (Quiero decir, se pueden esconder resultados de grafos sin hablar de grafos, pero sólo sirve para volver el problema más complicado de seguir)

Sin embargo, sí que es un problema famoso, de hecho no se conoce una solución general, para más detalle puedes buscar Teoría de Ramsey en internet y te explicará la historia y forma de abordar clásica de éstos problemas.

Un saludo!

[TitoNathan]

Muchas gracias!
Habrá que pasar de este ejercicio entonces, a no ser que a alguien se le ocurra cómo hacerlo.

[Fallen Angel]

No, no pases de el, utiliza grafos que para este problema es bien sencillo.

Un grafo no es más que una colección de vértices (puntos) y aristas (segmentos) que los unen.

Para tu problema, una arista puede representar que dos personas se conocen mutuamente.

Tienes un grafo con 6 vertices y ciertas aristas.

Te piden probar que o bien en ese grafo o en su dual (mismos vértices y cambiando las aristas que aparecen por las que no) hay contenido un triangulo.

Dibújalo y podrás ver enseguida por qué.

Un saludo!

[TitoNathan]

Me refería a pasar de él por ahora !!
Ya que en unos días estudiaré la teoría de grafos y lo podré entender mucho más rápidamente 

[Asdrúbal Beltrán]

Hola, tengo esta idea que parece funcionar:

Haciendo uso del principio del palomar se puede probar que cada uno de los seis debe tener por lo menos 3 conocidos, o por lo menos 3 no conocidos, supongamos que en el grupo  hay uno \( A \) con al menos 3 conocidos, sean \( B, C \) y \( D \) sus tres conocidos, este conjunto de tres elementos debe cumplir que si tomamos por  parejas, se debe tener,  que se conocen o no se conocen, si existe por lo menos una pareja que se conozcan entonces junto con \( A \), formaran un grupo de tres que se conocen mutuamente, si no existe una pareja de conocidos entre estos 3 entonces se debe tener que \( B, C \) y \( D \) cumplen que no se conocen mutuamente.

Saludos

[Fallen Angel]

Efectivamente esa es la idea kike, matizando que si no existe tal A que conozca a 3 personas, entonces existe otro A' que no conoce a tres personas e inviertes las relaciones.

Un saludo!

[TitoNathan]

Muchísimas gracias tanto a Fallen Angel como a kike0001, habeis ayudado mucho !