Sobre fiestas, saludos y teoría de grafos

No es la primera vez (ni la segunda) que hablamos de teoría de grafos en esta casa, ni tampoco será la última, créanme ¿Por qué? Pues, entre otras razones más prosaicas, porque esta rama de las matemáticas proporciona unas herramientas muy potentes para la resolución de problemas con una elegancia y simplicidad que las hacen dignas de estar, algunas de ellas, colgadas en las paredes de algún museo. Bueno, igual me he excedido, pero sí sería interesante que se conociera la teoría de grafos a nivel de ESO por eso, porque permitiría al estudiante resolver problemas matemáticos complicados con herramientas intuitivas y atractivas... y, ¿quién sabe?, igual acabaríamos con el desapego de una parte importante del alumnado por esta disciplina: las matemáticas.

Hace en algún tiempo contábamos cómo organizar el banquete de su boda con unos rotuladores, es decir, coloreando un grafo. Hoy seguimos de fiesta y seguimos con grafos: vamos con un acertijo sobre una fiesta y unos saludos.

Pongamos que Ana y Blas  asisten a una fiesta junto con otras cuatro parejas. Al encontrase  algunos se saludan con un apretón de manos y otros con un beso. Al acabar la fiesta, Blas pregunta a los asistentes a cuánta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. ¿A cuántas personas ha dado la mano Ana?

Les dejo un rato para que lo piensen, hagan todas las cuentas que quieran.

Ya.

Lo más importante para resolver un problema de matemáticas es saber leer. Lo leemos con atención y tratamos de extraer de la lectura toda la información que nos puede ser útil para resolver el mismo, por ejemplo, que Blas ha recibido nueve respuestas diferentes. Tenemos a diez personas en la fiesta, uno de ellos, Blas, les pregunta a los demás y obtiene nueve respuestas diferentes, eso significa que todas las respuestas eran distintas. Parece una tontería, pero no lo es.

Seguimos.

Cada uno de los nueve asistentes a los que Blas preguntó puede haber dado la mano a un número de personas entre 0 (este sería el besucón o la besucona de la fiesta) y 9 (este sería el más tímido o menos besucón que solo saluda con apretones de manos).

O sea que las respuestas que dieron los asistentes de la fiesta a Blas estaban comprendidas dentro del conjunto {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Alguna sobra porque en este conjunto hay 10 números y solo fueron 9.

Vamos a pensar un poco más, que es gratis y gratificante. No tiene sentido que ningún asistente le diera la mano a nueve personas. ¿Por qué? Pues porque eso significa que al llegar saludó con un apretón de manos también a su propia pareja y, normalmente, cuando se va en pareja a un fiesta se va 'saludado' de casa, ¿no? Estupendo, porque con esto eliminamos el 9 del conjunto de respuestas posibles y ya sabemos que las respuestas que obtuvo Blas de los otros asistentes de la fiesta fueron:

{0, 1, 2, 3, 4, 5, 6, 7, 8}

Seguimos. Recuerdo que tenemos que averiguar a cuántas personas dio la mano Ana. Para ello vamos a representar en un grafo a los diez asistentes a la fiesta. Dibujamos diez vértices (puntos) y los etiquetamos de la siguiente manera: a un vértice lo llamamos Blas y los otros 9 asistentes estarán etiquetados con el número correspondiente con la respuesta que le dieron a Blas.

Ahora vamos a unir con aristas (líneas) cada vértice (que corresponde con un asistente) con los  vértices correspondientes a los asistentes a los que dio la mano. Empezamos con el 8. El asistente con la etiqueta 8 lo tenemos que unir con ocho de los nueve vértices restantes. Bueno, es fácil, lo unimos con todos menos el de la etiqueta 0 que no estará unido con nadie (este era el besucón, les recuerdo):

¿Qué podemos deducir del grafo anterior? Efectivamente, que el vértice 0 es la pareja del vértice 8, porque este último le ha dado la mano a todos los demás y no es normal (ni deseable) saludar con un apretón de manos a tu pareja cuando llegas a una fiesta.

Estupendo. Coloreamos con el mismo color el 0 y el 8 para señalar que son pareja (como si de dos jublilados teutones se tratara) y seguimos dibujando el resto de aristas (líneas) del grafo.

Es el turno del 7. De este vértice tienen que salir siete aristas, y ya tenemos una, la que lo une con el 8, así que tenemos que añadir seis. Con el 0 no lo unimos porque el 0 no se une con nadie, con el 1 tampoco porque ya tiene una arista (la que llega del 8) y solo puede tener una (porque lleva la etiqueta 1), y con el 8 ya estaba unido, nos quedan el 2, el 3, el 4, el 5,  el 6 y Blas. Vamos a ello:

Pues ya hemos fichado a la pareja del 7, debe ser el 1. ¿Por qué? Porque el 7 ha saludado con un apretón de manos a todos menos al 0 y al 1, pero el 0 es la pareja del 8, así que no queda otra opción. Los pintamos del mismo color para indicar que son pareja y seguimos dibujando aristas del grafo.

Le toca al 6

Del 6 ya salen dos (la del 7 y la del 8), así nos faltan cuatro. No lo podemos unir ni con el 0, ni con el 1, ni con el 2 porque estos están completos; nos quedan el 3, 4, 5 y Blas. Vamos a ponerlas:

Ya lo tienen, ¿verdad? La pareja del 6 es el 2 porque es de los tres que no ha saludado con un apretón de manos (0, 1, 2) el único que no está emparejado ya. Coloreamos a la nueva pareja con el mismo color y seguimos con el 5.

Del vértice 5 ya salen tres aristas, así que necesitamos dos más y las únicas opciones posibles son 4 y Blas (el resto de los vértices ya están completos, es decir, tienen tantas aristas como marcan sus respectivas etiquetas):

Siguiendo un razonmiento similar a los anteriores concluimos que el 5 es pareja del 3. También los coloreamos con el mismo color y ya no hay que dibujar más aristas porque todos los vértices están completos:

Pues ya está. Ana, la pareja de Blas,  es el vértice 4 y, por lo tanto, saludó a cuatro de sus amigos con un apretón de manos y a los otros cuatro con un beso.

Curioso, ¿verdad? Volvemos con más grafos y con más fiestas otro día. Disfruten de la semana.