Diez habitaciones para 20 aventureros

—No, Ven, tú compartirás con algún amiguito tuyo, yo voy a dormir con Fran.

—Pero yo soy tu hermano y te quiero más.

—Ya lo se pero tú y yo compartimos habitación todas las noches, Ven. No te enfades, pero me gustaría dormir con un amigo mío, tú podrás dormir con alguno de los tuyos.

—Es que creo que te echaré de menos, Sal…

—Y yo a ti, pero sólo serán dos noches. Después volvemos a casa y volvemos a dormir en la misma habitación, ¿vale?

—No vale, yo prefiero dormir en el mismo cuarto que tú.

—Vaya, parece que estos niños preparan alguna aventura… —Mati acababa de llegar.

—¡Hola, Mati! —saludó Sal con alegría.

—Mati, Sal no quiere compartir habitación conmigo en Sierra Nevada —dijo Ven con voz de pena.

—Pero Ven, si vais de excursión, deberías aprovechar para dormir con algún amiguito, con Sal compartes siempre.

—Eso le he dicho yo, Mati. Además, Ven, a ti te encantan las fiestas pijama, sería como hacer una minifiesta pijama con un amigo tuyo.

—Toma, eso mola —Ven volvió a sonreír.

—Uy, esto me recuerda a un problema muy bonito… —comenzó a decir la pelirroja.

—¡¡De Matemáticas!! —gritaron al unísono los niños y se sentaron en el suelo dispuestos a escuchar a Mati.

—Creo que no voy a tener más remedio que contarlo…—dijo Mati con falso y cómico fastidio.

—¡Sí! —respondió enérgicamente Ven.

—Allá voy. Supongamos que 20 niños van de excursión y tienen que compartir habitación por parejas. Cada uno elige con quién compartir su habitación, pero puede ocurrir que haya conflicto porque haya varios niños que quieran compartir, por ejemplo, con la misma persona. ¿Cuál es la forma más eficiente de resolver este conflicto?

—¿Con una moneda? —preguntó Ven.

—Escribiendo los nombres de todos los niños en un papelito, se echan todos en una bolsa y cada uno coge uno. Si sale su propio nombre, lo echa en la bolsa y coge otro.

—¿Y si el último coge su propio nombre? —preguntó el pequeño.

—Empezamos de nuevo —repuso el gafotas.

—Eso puede tardar mucho… —se quejó Ven.

—Sí —afirmó Mati —y además puede que compartan habitación dos personas que no quieran estar juntas, porque aunque el sorteo sea justo, no está teniendo en cuenta las preferencias de los niños.

—Entonces, ¿cómo se hace, Mati? —quiso saber Sal.

—Ya veréis. Cada niño entrega al monitor encargado de asignar las habitaciones una lista con los nombres de sus 19 compañeros, ordenados por orden de preferencia para compartir. Éste, el monitor, tiene que conseguir los emparejamientos de forma estable. Es decir, si Eva prefiere a Mati antes que a Ana y Mati prefiere a Eva antes que Pepe, no puede ocurrir que haga estas parejas: Ana con Eva y Mati con Pepe. A esto lo llamamos emparejamiento inestable, porque Eva y Mati intentarán cambiar de parejas en cuanto puedan ¿Me explico?

—Creo que sí, Mati —dijo el gafotas sin levantar demasiado la voz — Si las dos quisieran estar juntas antes que compartir con los que les ha tocado, se llama inestable, ¿no?

—Eso es —respondió ella.

—Hay que conseguir que nunca ocurra esto, que dos personas prefieran estar juntas antes que con sus respectivos compañeros asignados, ¿me explico?

—Sí, Mati. Pero si no te asignan el primero de tu lista, siempre lo querrás por encima del que te toque, ¿no? —preguntó el gafotas.

—Claro, pero si tu primer candidato no te ha puesto a ti antes que al que le han asignado, se considera estable.

—¿Y cómo se hace? —preguntó el pequeño.

—Os voy a enseñar un método, que diseñó un señor, Robert Irving. Pero en lugar de hacerlo con 20 niños que sería muy largo, os lo explico con 6, ¿vale? Vamos a escribir en la pizarra los 6 nombres de los niños y sus listas de preferencias. Ya tenemos cuatro nombres, añadimos dos más, Sal y Ven, ¿qué os parece?

Los niños sonrieron y asintieron.

—Ahora, hacemos una primera asignación de parejas como sigue. Cada uno, por orden, le propone compartir cuarto al primero de su lista, mientras nadie se lo haya propuesto antes. Empieza Ana…

—Que se lo propone a Mati —Sal termina la frase.

—Eso —aceptó la gafotas.

—Y ahora Eva se lo propone a Ven, o sea, a mí —dijo el pequeño con sonrisa pícara.

—Muy bien, chicos. Seguimos: Mati se lo propone a Eva, Pepe se lo propone a Sal, Sal se lo propone a Mati, pero, ¡un momento! A Mati ya se lo había propuesto Ana.

—¿Qué hacemos, Mati? —preguntó Ven.

—Miramos la lista de Mati y descubrimos que ella prefiere a Sal antes que a Ana, así que Mati rechaza a Ana y acepta, por ahora, la propuesta de Sal. Por lo tanto, Ana, tiene que hacer otra propuesta, que se la hará a Pepe, que es el segundo en su lista. Y seguimos con Ven que se lo propone a Sal. Pero A Sal y se lo había propuesto Pepe, y como Sal prefiere a Pepe se queda con él y Ven elige al segundo de su lista.

—No te enfades, Ven, es un ejemplo —le dijo el gafotas a su hermano que estaba muy enfurruñado mientras le echaba un brazo por los hombros.

—Claro, Ven, es un juego —dijo Mati —Ya tenemos la primera asignación.

—¿Hemos terminado, chicos?

—Que va, Mati, así no sirve —contestó Sal.

—Efectivamente, ese emparejamiento no sirve, debe ser uno formado sólo con 3 parejas diferentes. Vamos a arreglarlo buscando, como decía Irving, rotaciones.

—¡¡¿¿Cómo??!! —preguntaron los niños.

—Ya veréis. Busco la primera pareja que no tenga a su simétrica en la esta asignación: (Ana, Pepe). Porque no está (Pepe, Ana), ¿verdad?

—Verdad —repuso Ven.

—Buscamos el siguiente a Pepe en la lista de preferencias de Ana, y miramos quién le ha propuesto compartir.

—El siguiente de Pepe en la lista de Ana es Eva —dijo Sal —y se lo propuso Mati, o sea tú.

—Muy bien, ésa será nuestra segunda pareja, (Mati, Eva) —contestó ella —Buscamos el siguiente a Eva en la lista de Mati y quién se lo propuso.

—El siguiente de Eva para Mati es Pepe y se lo propuso Ana —contestó alegremente Ven.

—Nos volvemos a encontrar con la pareja del principio, ¿no? Pues ya podemos hacer una rotación —concluyó Mati.

—Intercambiamos los segundos nombres, moviendo una posición hacia adelante cada nombre blanco. Irving demuestra que esto no crea nunca parejas que inestables. Y tenemos una segunda asignación. Repetimos el proceso, buscando una rotación.

—Déjame que yo lo diga, Mati —pidió con vehemencia el gafotas.

—Adelante, caballero —respondió Mati cómicamente.

—Miramos la primera pareja, (Ana, Eva). Como no existe (Eva, Ana), nos vale. Ahora buscamos el siguiente de Eva en la lista de Ana, que es Ven, y vemos quién le propuso compartir a Ven, que fue Eva. La segunda pareja para la rotación es (Eva, Ven). Tenemos que seguir hasta llegar a (Ana, Eva)…

—Sigo yo —interrumpió su hermano —Buscamos el siguiente de Ven en la lista de Eva, que es Sal. Busco quién se lo ha propuesto a Sal…es Pepe. La siguiente pareja es (Pepe, Sal).

—En la lista de Pepe, después de Sal —continuó el gafotas —es Eva, que se lo propuso Ana. Ya está, ya hemos llegado a (Ana, Eva)

—Pero, bueno, bueno, bueno…Qué rápido habéis entendido el método —Mati estaba muy orgullosa —Vamos a rotar los nombres blancos, moviéndolos una posición.

—¿Seguimos, chicos?

—¡Sí! —respondieron Sal y Ven al unísono.

—Pues, venga, aquí tenéis la nueva asignación después de la rotación que acabamos de hacer.

—Miramos la primera pareja, (Ana, Ven) —comenzó a hablar el gafotas — Como ahora sí que tenemos la pareja (Ven, Ana), pasamos de ella. Tomamos la siguiente pareja, (Eva, Sal). Ésta sí nos vale porque aún no tenemos la pareja (Sal, Eva) y buscamos el siguiente a Sal en la lista de Eva que es…Pepe, que le propuso compartir…Mati. La siguiente pareja de la rotación es (Mati, Pepe).

—Buscamos el siguiente de Pepe en la lista de Mati… —continuó su hermano —que es Sal…que se lo propuso Eva y …¡ya está! Apareció la pareja (Eva, Sal) del principio, ¡podemos rotar!

—¡Muy bien! —Mati estaba realmente entusiasmada —Ya tenemos otra nueva asignación.

—¡Toma, toma, toma! ¡Lo hemos conseguido!¡Lo hemos conseguido! —el pequeño Ven abrazaba a su hermano preso de la euforia.

—¡Es maravilloso, Mati! —al gafotas le brillaban los ojitos.

—Sí, lo es. Y con este método de las rotaciones es imposible que aparezcan parejas inestables, de las que dijimos al principio.

—¡Ese Irving como mola! ¡Se merece una ola! —Ven alzaba sus brazos, Gauss intentaba escapar de los abrazos de su dueño.

—Pues sí, Irving y su método molan —siguió diciendo Mati —pero el problema no siempre tiene solución, ¿eh?

—Entonces… —la cara de Ven perdió luz instantáneamente.

—Es que este problema, no siempre tiene solución. Vamos a verlos ocn un ejemplo muy sencillito. Nos quedamos con los cuatro niños del principio: Ana, Eva, Mati y Pepe. Los dibujamos aquí y también sus listas de preferencia.

—Pues bien, en este caso no hay solución, las tres posibles distribuciones de los niños en 2 habitaciones es inestable.

—Pobre Ana, todo el mundo la ha puesto la última —se entristeció Ven.

—Es sólo un ejemplo, Ven —le intentó consolar su hermano —Quizás Ana es una pegona abusona.

—No lo parece, Sal —respondió Ven cada vez más triste.

—Que es un ejemplo, Ven, no te preocupes —el gafotas siguió insistiendo.

—Es cierto, Ven —intervino Mati —es sólo un ejemplo para explicaros que a veces, este problema no tiene solución. Pero si la tiene, el método de Irving la consigue, y si no la tiene, también el método de Irving te lo hará saber, bien porque no puedes hacer una asignación inicial, bien porque salen cadenas de rotación raras. Pero, mira, si lo hacemos con conjuntos separados, siempre hay solución. Si separamos por ejemplo, por un lado los chicos y por otro las chicas, y hacemos habitaciones de chico y chica, siempre tiene solución.

—Pero así es un rollo, Mati, ¿no? —protestó el gafotas —Obligarte a compartir con una chica, o con un chico, es un rollo.

—Tienes razón, Sal —respondió Mati — En estos tiempos, ya no tiene sentido clasificar en función del sexo. Vamos entonces a contar el problema con príncipes y princesas de un reino fantástico muy lejano. Éste es un problema diferente, pero parecido al de los compañeros de cuarto, que se conoce como el problema del matrimonio estable.

—¿Cómo es? —al pequeño Ven se le había pasado la pena al oír que Mati les ia a proponer otro problema.

—Ahora tenemos 4 príncipes y 4 princesas. Las princesas tienen que elegir pareja entre los príncipes pretendientes.

—¿Qué es pretendiente, Mati? —preguntó Ven.

—En este caso, un pretendiente de una princesa es alguien que aspira al matrimonio con ella. Pues cada uno de los príncipes ordena a las princesas del 1 al 4, según sus preferencias y cada una de las princesas tiene ordenados del 1 al 4 a los príncipes, de la misma manera. Pues bien, si el número de príncipes y princesas es el mismo, este problema siempre tiene solución.

—¿Seguro? —preguntó el gafotas con desconfianza.

—Seguro, lo demostraron en 1962 dos señores, David Gale y Lloyd Shapley. El método para resolverlo es usar la sólo la primera fase, la de la primera asignación de Irving, no serán necesarias hacer las rotaciones.

—¡Cómo mola! —el pequeño Ven estaba de nuevo emocionado.

—Vamos a verlo con un ejemplo. Escribimos las listas de preferencias de 4 princesas y 4 príncipes. Las princesas, por orden, van a proponer matrimonio al primero de su lista mientras éste esté libre.

—Comenzamos. La princesa 1 propone matrimonio al príncipe 2; la princesa 2 propone matrimonio al príncipe 1, la princesa 3 propone matrimonio al prínicipe 2…¡Ojo! El príncipe 2 ya estaba pedido por la princesa 1.

—¿Qué hacemos Mati? —preguntó el pequeño preocupado.

—Miramos a quién prefiere el príncipe 2 según su propia lista —intervino el gafotas —Como hacíamos con los compañeros de cuarto.

—Efectivamente —corroboró Mati —Y descubrimos que en la lista del príncipe 2, la princesa 3 es preferida a la princesa 1. En esta caso, el príncipe 2 rechaza la oferta de la princesa 1 y se va con la princesa 3. La princesa 1, por lo tanto, tiene que proponer matrimonio a otro príncipe de su lista, al siguiente del 2…

—O sea, el 3 —dijo Ven con cómica suficiencia.

—Muy bien, chicos. Es el turno de la princesa 4, que elige al primero de su lista, el príncipe 3 pero, ¡ojo!,que está ya comprometido con la princesa 1.

—Ya —intervino Sal — pero si miramos en la lista del príncipe 3, él prefiere a la princesa 1, así que se queda con ella.

—Eso es —asintió Mati —Ahora la princesa 4 propone matrimonio al siguiente príncipe de su lista, esto es, al príncipe 2.

—El príncipe 2 está con la princesa 3 —dijo Ven —Y además, en su lista el prínicipe 2 prefiere a la princesa 4 así que rechaza a la princesa 3 y se va con la 4.

—¡Muy bien! —Mati sonrió satisfecha — La princesa 3 tendrá que hacer una nueva propuesta de matrimonio, al siguiente del príncipe 2 en su lista que es el príncipe 1.

—Que está ya con la princesa 2 —afirmó Sal.

—Sí —continuó Ven —Pero resulta que en la lista del príncipe 1 la princesa 3 está antes que la 2, así que se va con la princesa 3…¡Esto no va a terminar nunca!

—Claro que termina, Ven —Mati sonrió y alborotó el pelo del apasionado Ven. — Ahora es la princesa 2 la que, al ser rechazada por el príncipe 1 tiene que proponer matrimonio al siguiente del 1 en su lista que es el príncipe 3.

—¡Ajajá! Te lo dije, que está con la princesa 1 —dijo el pequeño con cansancio.

—Sí, Ven —respondió su hermano —Pero el príncipe 3 se quedará con la princesa 1 que es la primera de su lista, entonces la princesa 2 se lo propondrá al prínicpe 4 ¡que está libre! ¡Ya están las 4 parejas!

—¡Toma, toma, toma! —Ven levantaba y bajaba los brazos de alegría —¡Me encanta, Mati!

Matí sonrió viendo la cara de entusiasmo de los dos hermanitos.

—Ya os dije que con el mismo número de príncipes y princesas siempre tenía solución.

—¡Es chulísimo, Mati! ¡Chulísimo! —Sal estaba alucinando.

—Bueno, Sal, está bien. Yo compartiré con Pablo en la excursión. Así podremos charlar de nuestras cosas —dijo Ven haciéndose el interesante y tratando de intrigar a su hermano.

—Claro, Ven, es lo mejor. Y yo te echaré tanto de menos que estaré deseando volver a casa para volver a dormir contigo —Sal abrazó a su hermano que le correspondió con fuerza.

Mati contemplaba la escena llena de ternura mientras Gauss… ¿dónde se habría metido Gauss?

FIN

Los dos problemas que hemos tratado de explicar en nuestro capítulo de hoy son dos problemas bien conocidos en Combinatoria y Teoría de Juegos. El primero de ellos se conoce con el nombre de el problema del compañero de cuarto estable (stable roommates problem) y no siempre tiene solución como acabamos de ver. el algoritmo propuesto Por Rob Irving nos permite saber si existe solución y, en caso afirmativo encontrarla. Este algoritmo como acabamos de ver, está dividido en dos fases: en la primera de ellas se hace una asignación y en la segunda se buscan las cadenas de rotación. Pues bien, para el segundo problema que hemos contado, el de las princesas y los príncipes, conocido como el problema del matrimonio estable (stable marriage problem) sólo es necesaria la primera de las fases del algoritmo de Irving. Este segundo problema, el del matrimonio estable siempre tiene solución, si el número de príncipes es el mismo que el número de princesas. Para jugar con este segundo problema, podéis probar aquí.

Hasta pronto.

MATI