Fecha actual 18 Dic 2017, 06:00 Búsqueda avanzada

Conocidos y extraños

Moderador: sebagarage

Conocidos y extraños

Notapor sebagarage » 05 Jul 2008, 17:43

Pruebe que entre seis personas, siempre hay al menos [math] que se conocen entre ellas o al menos [math] que son completos extraños.
sebagarage
Moderador
 
Mensajes: 67
Registrado: 29 Jun 2008, 17:58

Re: Conocidos y extraños

Notapor Nicolavados » 22 Nov 2014, 17:36

El problema planteado se puede resolver usando el Teorema de la Amistad, el cual plantea que en cualquier grupo de seis personas, existen tres personas que son mutuamente conocidas o mutuamente desconocidas.
Para comprobarlo, usaremos grafos.
El grafo que usaremos tendrá 6 vértices no colineales que estén unidos todos entre sí por medio de aristas de diferente color, que representarán si las personas son conocidas o no lo son (Podemos usar los colores Rojo-Azul).
En este caso, habrían 15 aristas de diferente color y en cada vértice inciden 5 aristas.
Según el principio del Palomar, en un punto deberían haber 3 líneas de un color (Ya sea rojo o azul) y 2 de otro color (Si hay 3 rojas, debería haber 2 azules, y si hay 3 azules, debería haber 2 rojas).
Entonces, inevitablemente se formará un triangulo rojo o un triángulo azul dependiendo de la coloración de las líneas, y en base a él determinamos que habrían 3 personas mutuamente conocidas o 3 mutuamente desconocidas entre sí.
Nicolás A. Lavados T.
Nicolavados
 
Mensajes: 2
Registrado: 29 Ago 2014, 11:46
Ubicación: Santiago, Chile

Re: Conocidos y extraños

Notapor Jumbito » 27 Dic 2014, 13:59

Nicolavados escribió:El problema planteado se puede resolver usando el Teorema de la Amistad, el cual plantea que en cualquier grupo de seis personas, existen tres personas que son mutuamente conocidas o mutuamente desconocidas.
Para comprobarlo, usaremos grafos.
El grafo que usaremos tendrá 6 vértices no colineales que estén unidos todos entre sí por medio de aristas de diferente color, que representarán si las personas son conocidas o no lo son (Podemos usar los colores Rojo-Azul).
En este caso, habrían 15 aristas de diferente color y en cada vértice inciden 5 aristas.
Según el principio del Palomar, en un punto deberían haber 3 líneas de un color (Ya sea rojo o azul) y 2 de otro color (Si hay 3 rojas, debería haber 2 azules, y si hay 3 azules, debería haber 2 rojas).
Entonces, inevitablemente se formará un triangulo rojo o un triángulo azul dependiendo de la coloración de las líneas, y en base a él determinamos que habrían 3 personas mutuamente conocidas o 3 mutuamente desconocidas entre sí.


Correcto, aunque me permito comentar lo siguiente:

· Cuando dices "El problema planteado se puede resolver usando el Teorema de la Amistad, el cual plantea que en cualquier grupo de seis personas, existen tres personas que son mutuamente conocidas o mutuamente desconocidas" estoy entendiendo que quieres resolver el Teorema de la Amistad usando el Teorema de la Amistad. Esto es un error de redacción (porque me queda claro que no quisiste decir eso ya que luego demuestras el teorema). Hubiese sido mejor escribir "lo pedido se conoce como teorema de la amistad, que demostraremos a continuación".

· Si hablas de grafos, no es necesario mencionar que los puntos no son colineales. Esto nunca se usa y además es irrelevante tratándose de grafos. También en una parte escribiste "punto" en vez de "vértice" o nodo.

· Es cierto que si cada arista debe tener uno de dos colores, entonces en cinco aristas distintas deben haber al menos tres del mismo color, por el Principio del Palomar como dices. Sin embargo, no es cierto que sean o bien tres rojas y dos azules o tres azules y dos rojas. Podría suceder que sean cuatro rojas y una azul, etc. Lo importante aquí era observar que me basta con tener tres del mismo color.

· La conclusión está correcta pero falta algo de coherencia. ¿Por qué se forma necesariamente un triángulo de un mismo color?. Para el lector quizás esto no sea evidente.

Esos son los detalles que encuentro que hace que la solución no sea perfecta.

Ahora bien, también me permito comentar que este problema sirve como introducción para el problema de Ramsey, el cuál pueden buscar los interesados. Lo que aquí se muestra es que [math]. El problema de Ramsey es un problema desafiante e interesante de teoría de grafos.

Saludos
Felipe Arbulú
Jumbito
 
Mensajes: 55
Registrado: 19 Jul 2008, 15:50


Volver a Problemas Propuestos

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado

cron