Cuando el azar no basta: el teorema del matrimonio
¿Es posible que todas las damas de un baile encuentren pareja entre los caballeros que conocen? Una baraja de póker, un solitario que nunca falla y un teorema demostrado en 1935 permiten responder esa pregunta con matemáticas, en un problema que parece sencillo, pero no lo es.
Hay un bonito problema conocido como el «teorema del matrimonio», que plantea cuándo es posible formar parejas entre un grupo de mujeres y un grupo de hombres. En realidad, se trata de determinar qué condiciones deben cumplir ambos conjuntos para que cada persona pueda quedar emparejada.
Imaginemos una fiesta con un baile tradicional en un gran salón en el que se encuentran D damas y C caballeros. Cada una de las mujeres conoce a un determinado número de los hombres presentes, y para bailar el vals se forman las parejas de tal manera que cada dama baila con un caballero que ella conoce. Es decir no se forman parejas que no se hayan conocido antes de la fiesta. La pregunta es ¿bajo qué condiciones es posible que todas las damas encuentren un parejo para bailar el vals?
Es fácil encontrar ejemplos sencillos en los que no todas las damas pueden bailar. Si dos de ellas conocen a un solo caballero, y es el mismo, una quedará sin pareja. Lo mismo ocurre si tres damas conocen solo a dos caballeros, y son los mismos: no podrán formarse las tres parejas.
Como se puede concluir fácilmente, una primera condición es que el número de caballeros, C, sea mayor o igual que el de damas, D. Más exactamente, si cada grupo de K damas conoce al menos a K caballeros, para todos los valores K = 1, 2, …, D, entonces se puede asegurar que existe un emparejamiento en el que todas las damas bailan el vals. Y recíprocamente, si el emparejamiento existe, esa condición se cumple necesariamente.
Esto es justamente lo que afirma el teorema del matrimonio, demostrado en 1935 por el matemático británico Philip Hall. Se enuncia con novias y novios que podrían casarse, y por eso recibe ese nombre, aunque también se conoce como «teorema de Hall». El problema parece muy sencillo, pero no es trivial.
Supóngase que la dama D1 conoce a los caballeros C1, C2 y C3; la dama D2, a C2, C3 y C4; y la dama D3, a C3 y C5. Un posible emparejamiento es (D1, C2), (D2, C3) y (D3, C5). Otro es (D1, C1), (D2, C4) y (D3, C3). Y hay más.
Pero supóngase ahora un grupo de cuatro damas: D1 conoce a los caballeros C1, C2, C3 y C4; D2 conoce a C2 y C3; D3 solo conoce a C2; y D4 solo conoce a C3. En este caso no se cumple la condición del teorema, porque las damas D2, D3 y D4 conocen, en conjunto, solo a dos caballeros, C2 y C3. D4 solo puede bailar con C3 y D3 solo con C2, de modo que D2 se queda sin pareja. Por eso, entre las cuatro damas únicamente pueden formarse tres parejas.
Un resultado similar que se deriva del teorema del matrimonio es el siguiente: en un grupo de damas y caballeros, si existe un número P para el cual cada dama conoce exactamente a P caballeros y cada caballero conoce exactamente a P damas, es posible emparejar a todos los caballeros con damas que conocen. Este resultado no permite hallar las parejas, pero sí garantiza que existe una solución.
Considérese un juego con una baraja de póker para comprender mejor el alcance del resultado. Se barajan las 52 cartas y se reparten sobre una mesa, boca arriba, formando una matriz de 13 columnas y 4 filas, como se muestra a continuación:
A continuación, se propone un solitario que consiste en seleccionar el mayor número posible de cartas, tomando solo una de cada columna, de modo que todas las elegidas tengan valores distintos, sin importar el palo. El máximo posible es 13, y el juego se gana si se logra seleccionar 13 cartas.
Por ejemplo, con la distribución anterior se va sacando una carta de cada columna, hasta la columna 8, y se forma una fila superior así:
Si se continúa de esta manera, se logra completar la fila superior con 13 cartas, todas de valores distintos, desde el as hasta el rey:
En este caso se logró el objetivo de sacar las 13 cartas. Conviene aclarar que las cartas no estaban preparadas previamente. A diferencia de la mayoría de los solitarios, este nunca falla: no depende solo del azar, pues, sea cual sea el reparto de las cartas, siempre existe al menos una solución con las 13 cartas. Se invita a jugarlo para comprobarlo y divertirse.
El solitario de las cartas ilustra, quizá mejor, el teorema del matrimonio. Basta imaginar 13 damas, que son las columnas, y 13 caballeros, que son los valores posibles, del as al rey. Cada dama conoce a los caballeros cuyos valores aparecen en las cartas de su columna. Es fácil verificar que dos columnas cualesquiera contienen cartas de al menos dos valores distintos. Tres columnas contienen cartas de al menos tres valores distintos y, en general, m columnas contienen cartas de al menos m valores distintos. La razón es sencilla: m columnas tienen 4m cartas y, como cada valor aparece solo 4 veces en toda la baraja, hacen falta al menos m valores distintos para cubrirlas. Así se cumple la condición del teorema y, por lo tanto, siempre es posible elegir una carta de cada columna con valores todos distintos.
Hoy en día el teorema del matrimonio se usa en otros campos, como la asignación de puestos de trabajo a un grupo de empleados, la selección de rutas de transporte o la elección y el reparto de los alimentos apropiados para las dietas de un grupo de pacientes de un hospital.
Como información final, cabe agregar que el teorema del matrimonio es una herramienta matemática que se estudia formalmente en la teoría de grafos.
@MantillaIgnacio
Ignacio Mantilla Prada
Matemático
Profesor
Dr. Rer. Nat.
Rector 2012 – 2018
Universidad Nacional de Colombia
Este blog está dedicado principalmente a la divulgación matemática. Su objetivo es acercar al público general conceptos, resultados, paradojas, acertijos, curiosidades, problemas, relatos históricos, noticias e ideas matemáticas, presentándolos de forma accesible, rigurosa y clara. Aspira a tender puentes entre el conocimiento especializado y el interés del lector no experto, mostrando la belleza, la utilidad y las sorpresas que esconden las matemáticas.
Los editores de los blogs son los únicos responsables por las opiniones,
contenidos, y en general por todas las entradas de información que deposite en el mismo. Elespectador.com no
se hará responsable de ninguna acción legal producto de un mal uso de los espacios ofrecidos. Si considera
que el editor de un blog está poniendo un contenido que represente un abuso, contáctenos.