Ciencia y Tecnología

El truco matemático para organizar las mesas en un banquete de bodas

Este problema tiene su solera: en 1877, el físico escocés Peter Guthrie Tait enunció un problema parecido en sus trabajos de teoría de nudos.

Los seguidores habituales de estas y otras columnas matemáticas, sin otra formación que la escolar, seguramente hayan ido descubriendo que además de efectuar operaciones y cálculos, las matemáticas son una herramienta para analizar y tratar de resolver problemas. Pero no exclusivamente los problemas técnicos a los que sólo los matemáticos encontramos sentido (ya saben, plantear y resolver ecuaciones diferenciales, buscar soluciones a ecuaciones aparentemente sin utilidad, determinar estimaciones a integrales no resolubles en modo exacto, etc.),sino aquellos derivados de situaciones reales, cotidianas. Hoy vamos a describir uno aparentemente inocente, que en nuestra vida cotidiana solventaríamos en un pis-pas (o sea del modo más chapucero que se nos ocurra para salir del paso), pero que a nada que profundicemos un poco, veremos cómo surgen esas expresiones, fórmulas y relaciones que tantos quebraderos de cabeza decimos que nos dan.

Empecemos por lo más sencillo. Vamos a un evento (una boda de las de antes, una reunión, una fiesta, o sencillamente a un parque) en el que coincidimos con otras tres personas. Queremos sentarnos en un banco. ¿De cuántas maneras podemos hacerlo? La cuenta es fácil para cualquiera: se sienta el primero donde le da la real gana, y a continuación, la siguiente persona tiene dos opciones, o a la derecha o a la izquierda del primero (encima no, que aparte de no cumplir con las normas actuales, no es de buena educación, en general). O sea, tiene 2 opciones. ¿Cuántas opciones tiene después la siguiente persona? Está claro que 3, ¿no? Y la siguiente 4, y así sucesivamente, de modo que el número total de posibilidades es 4 x 3 x 2 x 1, lo que en matemáticas se llama el factorial de 4, y se representa por 4! Para los que ‘amaron’ la combinatoria en el instituto, eso representa el número de permutaciones de cuatro elementos. Por cierto,si se sentaran en una mesa circular en lugar de en un banco, ¿habría el mismo número de posibilidades? ¿Podrían dar el número para n personas?

No me vengan con la cantinela de que ya estamos los matemáticos «tocando las narices». ¿Se venden mesas circulares, o no? Seguro que ustedes tienen alguna mesa camilla por casa, de modo que, ¿quién toca nada? La situación se da, y hay que darle respuesta. Como indicación les diré que, en una mesa redonda, si tenemos sentadas cuatro personas (pongamos en el orden ABCD), si todas se levantan y se sientan en la silla de la derecha (quedando por tanto BCDA), a los efectos del conteo configuración es la misma, no cuenta como dos diferentes. Porque la mesa es redonda y no debe influir desde donde empezamos a considerar a los comensales. Esto es una pista importante para que averigüen el número de configuraciones distintas, que son por tanto menos que si estamos en un banco corrido.

Un pequeño inciso. Esto es un caso particular del conocido como principio fundamental del conteo: si hay p formas de hacer una cosa, q formas de hacer otra cosa, y r de una tercera, entonces hay p x q x r formas de hacer las tres.

La cosa se empieza a complicar cuando tenemos que empezar a cumplir con algunas exigencias de los invitados. Por ejemplo, las parejas quieren sentarse juntas (o al revés, no quieren, que a lo mejor es más común), o los de un determinado partido político o de un equipo de fútbol no quieren estar al lado (o enfrente) de los colegas de otro signo distinto. Estas situaciones que, vuelvo a decir, se dan, ¿no? Pues a ver cómo las solventamos para que la fiesta acabe en paz, sobre todo teniendo en cuenta que, no hablamos de 5 o 10 personas. ¡Hablamos de 300, pongo por caso! E imaginen que cada uno con sus exigencias.

Este problema no es ni mucho menos actual, tiene su solera. En 1877, el físico escocés Peter Guthrie Tait (1831 – 1901) enunció un problema equivalente en sus trabajos de teoría de nudos: de cuántas maneras pueden disponerse n letras, de modo que A no puede estar ni en primer, ni en segundo lugar; B no puede estar ni en segundo, ni en tercer lugar; y así con el resto. A nada que lo piensen verán que es un problema equivalente. Un año después, en 1878, Arthur Cayley (1821 – 1895) y Thomas Muir (1844 – 1934), independientemente, publican soluciones utilizando relaciones de recurrencia o funciones generatrices, pero no dando una fórmula explícita general.

Catorce años después, en 1891, el célebre matemático Édouard Lucas (1842 – 1891), paradójicamente más conocido por inventar algunos juegos recreativos que por sus aportaciones a las matemáticas (trabajos sobre la sucesión de Fibonacci, a la que él mismo bautizó así, y por un test de primalidad), lo enuncia, en su estilo, como el problema de las parejas, y reproduce las soluciones de Cayley y Muir (que al parecer desconocía). Deberían pasar otros 43 años para que, en 1934, el matemático francés Jacques Touchard (1885 – 1968) publicara una fórmula, pero ¡¡sin demostración!! La primera prueba de la fórmula explícita de Touchard se dio nueve años después, en 1943, ¡¡66 años después de que Tait planteara la cuestión!!

La proporcionó el canadiense-norteamericanoIrving Kaplansky (1917 – 2006) (en la imagen). Por supuesto entremedias ha habido otros matemáticos que han aportado sus trabajos, unos veinte en total. Les cuento todo esto para que vuelvan a replantearse cómo funcionan las cosas en ciencia y valoren en su justa medida el logro de hallar una vacuna a algo desconocido en sólo un año.

Pero este problema tiene otra vertiente, que, por curiosa, suele asociarse a este problema. Revisiones posteriores de la solución (Kenneth P. Bogart y Peter G. Doyle, en 1986, 43 años más tarde) llevan a una lapidaria conclusión sobre la prueba de Kaplansky de sólo tres palabras: «las damas primero». ¿Por qué? Se lo cuento al final.

¿Tan difícil es resolverlo?

Para hacernos una idea, vamos a intentar resolver algunas situaciones particulares, con números sencillos, y al final, sin demostrársela, les doy la solución general, por si alguien se anima. Recordemos el enunciado del problema:

¿De cuántas maneras pueden sentarse n parejas en una mesa circular, alternándose hombres y mujeres, de modo que nadie se siente al lado de su pareja?

Como se suele hacer en matemáticas, simplifiquemos un poco más la situación, a ver si así nos resulta más fácil o nos da la idea de cómo atacar el problema general. Vamos a mantener la condición de que nadie se siente al lado de su pareja, pero vamos a quitar la de que se alternen hombres y mujeres, es decir, que sí puedan sentarse dos hombres o dos mujeres al lado uno del otro. Esta nueva situación se conoce como el problema de las parejas relajado.

Para entender el razonamiento que siguieron Bogart y Doyle vamos a tratar de resolver el problema para solo 2 parejas, es decir, 4 personas. Sean éstas A, B, C y D. Supongamos que tanto A y C, como B y D son pareja en la vida real, y por tanto tenemos que encontrar todas las posibles disposiciones en una mesa circular sin que estén juntas ninguna de esas parejas. Bogart y Doyle construyen entonces un número r < n de ‘nuevas’ parejas que no se conozcan. Para que se cumpla esa desigualdad, en el caso de n = 2 (2 parejas, 4 personas), sólo podemos formar una pareja (por tanto, r = 1). Sea ésta AB. Vamos a pensar en esa pareja como una ficha de dominó, y vamos a ver de cuántas maneras diferentes podemos colocarla en una mesa circular con 4 sillas. Es sencillo si hacemos un dibujo.

A ver, no se dejen engañar. En el dibujo anterior, tal y como indicamos en un comentario anterior sobre la disposición en mesas circulares, sólo hay estrictamente dos posiciones distintas. A ver si las encuentran. Habría otras dos con AB juntos (aunque en diferente orden) que serían BADC y CBAD. Total 4. Ahora bien, en lugar de ‘emparejar’ inicialmente A con B, también podemos hacer A con D, teniendo otras cuatro posibilidades (igual al dibujo anterior, sólo que ahora la pieza de dominó es AD). En total por tanto tenemos 8 formas distintas.

Para hacer un razonamiento general (sólo lo esbozaré), fijémonos que colocar una sola pieza de dominó (r, en general), es lo mismo que disponer 2 asientos restantes (en general 2n – 2r) en a lo sumo r arcos de circunferencia. Compruébenlo en la siguiente imagen en que se han elegido 3 parejas (3 fichas de dominó) a colocar en una mesa circular con 16 asientos (o sea 8 parejas). Al colocar esas tres piezas de dominó, debemos ver cómo hay que disponer las otras 10 personas en 3 arcos (si como en la imagen quedan huecos entre las tres piezas), 2 arcos (si dos piezas de dominó van juntas) o un solo arco (si se colocan las tres piezas de dominó juntas).

Otro modo de decir lo mismo: empezaremos contando el número de formas posibles de colocar r fichas de dominó sin que se superpongan en un ciclo con 2n posiciones. Con lo dicho, pensemos cómo calcularlas. Elegimos un sitio concreto entre los 2n lugares. Evidentemente esto se puede hacer de 2n formas diferentes. Situemos ahora los dominós idénticos con un número indeterminado de espacios vacíos en cada uno de los r arcos que quedan entre dos dominós consecutivos. En estos arcos deben disponerse 2n – 2r espacios vacíos. Es un problema típico de combinatoria (no inmediato), que se resuelve con la expresión:

Recordemos que el factor 2n corresponde al número total de formas de elegir el primer sitio, y que el divisor r es porque la mesa es circular y hay r configuraciones equivalentes (por lo que para ver las diferentes hay que dividir por ese valor). Simplificando un poco ese producto tenemos que es igual a:

Finalmente es necesario aplicar el principio de inclusión-exclusión para eliminar repeticiones (otro día les cuento de un modo sencillo en que consiste) como las que vimos en el caso de 2 parejas, llegando como fórmula final que nos da el número total a:

 

Si calculan algunos de esos valores verán que, para 2 parejas, en efecto aparecen 8 posibilidades diferentes, pero ya para 3 parejas (o sea 6 personas) salen 192, para 4 parejas se tienen 11904, …, para 10 parejas (20 personas) 826060810479206400 posibilidades.

Recuerden que esta es la solución al problema relajado, es decir, sin exigir que, además, vayan alternados hombres y mujeres. En ese caso, el número de posibilidades es, evidentemente más pequeño. A modo de curiosidad les doy también la fórmula final:

 

que para 2 parejas (4 personas) no hay ninguna disposición que cumpla las dos condiciones, para 3 parejas hay 12, para 4 parejas salen 96 posibilidades, …, y para 10 parejas (por comparar con la anterior) hay 3191834419200 disposiciones. Bastantes menos, pero también un mogollón.

Por supuesto, la mayor parte de los lectores no están en condiciones de llegar a deducir la fórmula final, pero el objetivo de la reseña es mostrar cómo en problemas aparentemente sencillos, se esconden desarrollos complicados que precisan de matemáticas de cierto nivel. Suele ocurrir que los problemas aparentemente más sencillos e inocentes, acaban resultando los más puñeteros (permítanme la expresión).

Ah, que no se me olvide, la sorpresa final.

Un título desafortunado

Bogart y Doyle, queriendo dar un toque de humor, titularon el artículo con su solución (básicamente la que hemos expuesto aquí) «Una solución no sexista al problema de las parejas» (Non-sexist solution of the ménage problem; pueden encontrarlo en internet sin problema). La forma de resolver el problema (llegando por supuesto a la misma fórmula) de Kaplansky era colocar en sitios fijos o a los hombres o a las mujeres, para cumplir desde el principio la condición de que vayan alternados, y luego calcular todas las posibles disposiciones del otro sexo. Así resulta un típico problema de combinatoria. Pero se le ocurrió escribir:

«Comencemos por fijar las posiciones de los esposos y las esposas; pongamos las esposas, por cortesía».

Observemos que Bogart y Doyle eligen parejas de desconocidos, sin especificar el sexo ni si primero van los hombres o las mujeres (por eso de solución «no sexista» que decían). El caso es que esa forma de abordar el problema, a efectos de razonamientos y cálculos posteriores, resulta mucho más sencilla que la de Kaplansky. Y como siempre ha habido gente con ganas de hacer ruido, al bueno de Kaplansky le cayeron un montón de críticas, al punto que tuvo que hacer la siguiente declaración:

«Da igual que se empiece por hombres o mujeres. Supongan que tienen chips blancos y chips rojos. Es bastante natural en una primera aproximación ingenua decir: ‘Intentemos poner las fichas blancas primero’».

Incluso se argumentó que la culpa fue de Édouard Lucas, una mentalidad del siglo XIX, por enunciar el problema en términos de maridos y esposas. Es claro, a día de hoy, año 2021, que nos queda mucho, pero mucho, por acercar las condiciones sociales y laborales de hombres y mujeres, aunque haya quien no lo quiera ver, pero desde luego a base de temas importantes, no por meras anécdotas de este tipo, que no hacen sino evadir el verdadero problema. Al menos así es desde un punto de vista estrictamente matemático.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.