Teorema del matrimonio

Hay un bonito problema que se conoce como el “Teorema del matrimonio” y que plantea la posibilidad de emparejamientos entre D mujeres y C hombres. En realidad se trata de estudiar cómo deben ser los dos conjuntos para que sea posible formar parejas.

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 algunos ejemplos sencillos donde no es posible que todas las damas puedan bailar: si dos de ellas conocen a un solo caballero y se trata del mismo, una de ellas quedará sin parejo. O si tres damas conocen solo a dos caballeros y son los mismos, no podrán formarse entonces 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 las damas D. Más exactamente, si cada conjunto de K damas conoce al menos a K caballeros, para todos los valores de K = 1, K = 2, …, K = C, entonces es seguro que existe un emparejamiento posible para que todas las damas bailen el vals.

Esto es justamente lo que afirma el Teorema del matrimonio, demostrado en 1935 por el matemático británico Philip Hall y enunciado con novias y novios o parejas que podrían casarse; por eso se le llama así o también se conoce como “Teorema de Hall”. El problema parece ser muy sencillo, pero no es trivial. 

Si la dama D1 conoce a los caballeros C1, C2 y C3; la dama D2 conoce a los caballeros C2, C3 y C4; y la dama D3 conoce a los caballeros C3 y C5, un posible emparejamiento es (D1, C2), (D2, C3) y (D3, C5). Otro puede ser (D1, C1), (D2, C4), (D3, C3). Y hay más.

Pero si ahora tenemos un grupo de cuatro damas: la dama D1 conoce a los caballeros C1, C2, C3 y C4; la dama D2 conoce a los caballeros C2 y C3; la dama D3 solo conoce al caballero C2; y la dama D4 solo conoce al caballero C3, entonces ya no se cumplen las condiciones del teorema, pues las damas D2, D3 y D4 solo conocen a los caballeros C2 y C3 y en total las cuatro damas solo pueden formar tres parejas ya que la dama D4 solo puede tener a C3 como parejo y la dama D3 solo puede emparejarse con C2, lo que impide que D2 pueda tener parejo.  

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, se puede emparejar a cada uno de los caballeros con alguna dama conocida. Aunque este resultado no resuelve el problema práctico de encontrar las parejas, sí garantiza la existencia de una solución.

Veamos un juego con una baraja de póker para comprender mejor el alcance del resultado. Barajamos las 52 cartas y las repartimos sobre una mesa con las caras destapadas formando una matriz de 13 columnas y 4 filas, como aparece a continuación.

Ahora vamos a jugar un solitario consistente en encontrar el mayor número de cartas, eligiendo solo una en cada columna, de modo que todas las cartas seleccionadas tengan diferente valor, sin importar el palo. El número máximo de cartas posibles es 13 y podemos decir que ganamos el juego si encontramos 13 cartas.

Por ejemplo, con la distribución de arriba voy sacando una carta de cada columna hasta la columna 8 y voy formando una fila superior así:

Continuando en esta forma logro completar la fila superior de tal manera que al final tengo 13 cartas, todas con diferente valor, desde el as hasta el rey:

En este caso he conseguido el objetivo de sacar las 13 cartas. Aclaro que las cartas no estaban previamente preparadas. A diferencia de la mayoría de los solitarios, éste nunca falla, lo que quiere decir que no es un juego de azar solamente, pues sea cual sea el el reparto de las cartas, siempre existe al menos una solución con las 13 cartas. Puede usted jugarlo ahora para comprobarlo y divertirse.

El juego solitario de las cartas ilustra, tal vez mejor, el Teorema del matrimonio, basta imaginar un grupo de 13 damas (las columnas) donde cada una de ellas conoce a 4 caballeros que son los que están en las filas correspondientes. Es fácil verificar que si comparamos dos columnas cualesquiera, encontramos cartas de al menos dos valores distintos; en tres columnas hay cartas que tienen al menos tres valores distintos y en general, en m columnas hay al menos m valores distintos de cartas, con lo cual se cumplen las condiciones del teorema.

Hoy en día se usa el Teorema del matrimonio en otros campos, desde asignar puestos de trabajo a un grupo de empleados, seleccionar rutas de transporte o elegir y repartir los alimentos apropiados en las dietas de un grupo de pacientes de un hospital. 

Como información final debo agregar que el Teorema del matrimonio es una herramienta matemática que se estudia formalmente en la Teoría de Grafos. 

@MantillaIgnacio