El verano trae consigo irremediablemente jugar a las cartas más a menudo que de costumbre. Bien sean las noches sentados en el césped, como los descansos del estudio en la biblioteca para el café.

Y si hay algo común a todos los juegos de cartas es barajarlas para poder repartirlas de la forma más aleatoria posible. Me gusta hacer la clásica mezcla que hacen croupiers y magos, tomando dos mitades y dejando caer las cartas intercaladas. A falta de un nombre mejor, la denominaba Mezcla Americana, pero Googleando un poco, parece ser que le llaman Riffle Shuffle.

Un día pensé ¿Y si se hace la mezcla perfecta? Imaginemos que tenemos un dominio tal de la baraja que somos capaces de partir exactamente por la mitad y luego soltarlas una a una, quedando perfectamente intercaladas, una de cada mazo. Entonces me planteé qué ocurriría si se repetía ese proceso varias veces ¿Se volvería a la posición inicial? Y de ser así ¿En cuántas veces?

Quiero que quede claro ya desde aquí que no es una cuestión estadística. No estamos haciendo una mezcla normal, en la que las cartas quedan de forma aleatoria cada vez, sino una totalmente definida y que está claro que siempre será igual. Lo digo ya porque mucha gente a la que se lo he planteado fue la respuesta que me dieron al principio, y es evidente que aquí la probabilidad está fuera de lugar.

Al principio no pasó de un simple pensamiento veraniego, pero dos o tres días después lo recordé estando con mis amigos en un bar y les comenté el problema, así que tras pensarlo un poco empezamos a escribir en una servilleta cómo iba evolucionando el conjunto de cartas. Lo hicimos muy resumido, sólo las primeras y últimas cartas de cada mitad, con puntos suspensivos por en medio, para tratar de imaginar cómo se iba comportando. En que llegamos a la tercera iteración nos dimos cuenta de que era una tarea tediosa y puramente mecánica, así que decidí hacer un programa al día siguiente que lo ejecutase.

La tarde posterior programé lo necesario para hacer las iteraciones, y 56 líneas después empecé a probar resultados. El problema no hubiera pasado de ahí, de no ser porque las soluciones se escapaban de lo predecible. ¿Quién iba a pensar que las veces que hay que barajar no aumentan con el número de cartas? ¿Cómo iba a imaginar que con 40 naipes hacen falta 12 mezclas y con 64 solo 6? Cuantos más conjuntos de cartas probaba, más sorprendido me quedaba.

Así que fui envenenando a diferentes amigos con el problema, picando la curiosidad de todos, hasta que me descubrí buscando las ecuaciones que definen el problema. Desgraciadamente sólo uno se lo está “tomando en serio” y nos estamos quedando sin ideas. Necesitamos un soplo de aire fresco de alguien con nuevas ideas, pues las que teníamos las hemos explotado bastante.

Yo conseguí una ecuación recursiva definida en dos trozos que explicaba a dónde iba la carta, y que aplicándola iterativamente hasta que la posición volvía a ser la original, daba el número de mezclas. Él, matemático, lo analizó como una matriz, aplicando transformaciones y obteniendo la solución como la matriz unidad, con vectores propios y diagonalización. Yo ahora estoy empezando con grafos y me he dado cuenta de que me equivoqué en una premisa inicial, por lo que la fórmula que tenía no es esencialmente correcta. Ahora pongo algunos conjuntos de ejemplo, por si a alguien no le ha quedado claro cómo se mezcla.

Conjunto de 8 cartas. [1, 2, 3, 4, 5, 6, 7, 8]
Vuelta número 1
Primera mitad: [1, 2, 3, 4]
Segunda mitad: [5, 6, 7, 8]
Mazo mezclado: [1, 5, 2, 6, 3, 7, 4, 8]

Vuelta número 2
Primera mitad: [1, 5, 2, 6]
Segunda mitad: [3, 7, 4, 8]
Mazo mezclado: [1, 3, 5, 7, 2, 4, 6, 8]

Vuelta número 3
Primera mitad: [1, 3, 5, 7]
Segunda mitad: [2, 4, 6, 8]
Mazo mezclado: [1, 2, 3, 4, 5, 6, 7, 8]

Así se puede ver como, para 8 cartas, con mezlcar 3 veces, volvemos a la posición de partida.
Copio, ahora, la solución para 52 naipes, la baraja francesa.

Conjunto de 52 cartas.
Vuelta número 1
Primera mitad: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]
Segunda mitad: [27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52]
Mazo mezclado: [1, 27, 2, 28, 3, 29, 4, 30, 5, 31, 6, 32, 7, 33, 8, 34, 9, 35, 10, 36, 11, 37, 12, 38, 13, 39, 14, 40, 15, 41, 16, 42, 17, 43, 18, 44, 19, 45, 20, 46, 21, 47, 22, 48, 23, 49, 24, 50, 25, 51, 26, 52]

Vuelta número 2
Primera mitad: [1, 27, 2, 28, 3, 29, 4, 30, 5, 31, 6, 32, 7, 33, 8, 34, 9, 35, 10, 36, 11, 37, 12, 38, 13, 39]
Segunda mitad: [14, 40, 15, 41, 16, 42, 17, 43, 18, 44, 19, 45, 20, 46, 21, 47, 22, 48, 23, 49, 24, 50, 25, 51, 26, 52]
Mazo mezclado: [1, 14, 27, 40, 2, 15, 28, 41, 3, 16, 29, 42, 4, 17, 30, 43, 5, 18, 31, 44, 6, 19, 32, 45, 7, 20, 33, 46, 8, 21, 34, 47, 9, 22, 35, 48, 10, 23, 36, 49, 11, 24, 37, 50, 12, 25, 38, 51, 13, 26, 39, 52]

Vuelta número 3
Primera mitad: [1, 14, 27, 40, 2, 15, 28, 41, 3, 16, 29, 42, 4, 17, 30, 43, 5, 18, 31, 44, 6, 19, 32, 45, 7, 20]
Segunda mitad: [33, 46, 8, 21, 34, 47, 9, 22, 35, 48, 10, 23, 36, 49, 11, 24, 37, 50, 12, 25, 38, 51, 13, 26, 39, 52]
Mazo mezclado: [1, 33, 14, 46, 27, 8, 40, 21, 2, 34, 15, 47, 28, 9, 41, 22, 3, 35, 16, 48, 29, 10, 42, 23, 4, 36, 17, 49, 30, 11, 43, 24, 5, 37, 18, 50, 31, 12, 44, 25, 6, 38, 19, 51, 32, 13, 45, 26, 7, 39, 20, 52]

Vuelta número 4
Primera mitad: [1, 33, 14, 46, 27, 8, 40, 21, 2, 34, 15, 47, 28, 9, 41, 22, 3, 35, 16, 48, 29, 10, 42, 23, 4, 36]
Segunda mitad: [17, 49, 30, 11, 43, 24, 5, 37, 18, 50, 31, 12, 44, 25, 6, 38, 19, 51, 32, 13, 45, 26, 7, 39, 20, 52]
Mazo mezclado: [1, 17, 33, 49, 14, 30, 46, 11, 27, 43, 8, 24, 40, 5, 21, 37, 2, 18, 34, 50, 15, 31, 47, 12, 28, 44, 9, 25, 41, 6, 22, 38, 3, 19, 35, 51, 16, 32, 48, 13, 29, 45, 10, 26, 42, 7, 23, 39, 4, 20, 36, 52]

Vuelta número 5
Primera mitad: [1, 17, 33, 49, 14, 30, 46, 11, 27, 43, 8, 24, 40, 5, 21, 37, 2, 18, 34, 50, 15, 31, 47, 12, 28, 44]
Segunda mitad: [9, 25, 41, 6, 22, 38, 3, 19, 35, 51, 16, 32, 48, 13, 29, 45, 10, 26, 42, 7, 23, 39, 4, 20, 36, 52]
Mazo mezclado: [1, 9, 17, 25, 33, 41, 49, 6, 14, 22, 30, 38, 46, 3, 11, 19, 27, 35, 43, 51, 8, 16, 24, 32, 40, 48, 5, 13, 21, 29, 37, 45, 2, 10, 18, 26, 34, 42, 50, 7, 15, 23, 31, 39, 47, 4, 12, 20, 28, 36, 44, 52]

Vuelta número 6
Primera mitad: [1, 9, 17, 25, 33, 41, 49, 6, 14, 22, 30, 38, 46, 3, 11, 19, 27, 35, 43, 51, 8, 16, 24, 32, 40, 48]
Segunda mitad: [5, 13, 21, 29, 37, 45, 2, 10, 18, 26, 34, 42, 50, 7, 15, 23, 31, 39, 47, 4, 12, 20, 28, 36, 44, 52]
Mazo mezclado: [1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52]

Vuelta número 7
Primera mitad: [1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50]
Segunda mitad: [3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52]
Mazo mezclado: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52]

Vuelta número 8
Primera mitad: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51]
Segunda mitad: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52]
Mazo mezclado: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52]

De todas las personas con las que he hablado, ninguno había escuchado jamás este problema, así que si ya existe formulado como tal, quizás no sea muy famoso. Aunque este blog no lo lee mucha gente espero que alguien se anime, o se lo contéis a alguien que pueda interesarle, a mí por lo menos me tiene atrapado.

Dentro de un par de semanas o así publicaré todo lo que hemos averiguado hasta ahora, que tampoco es mucho, pero tenemos el problema más o menos cogido por algunos puntos.

Asumo que todos tenéis la máquina Java instalada en vuestro ordenador. Para utilizar el programa que hice tenéis que ir al Símbolo del Sistema (Inicio > ejecutar > cmd > Aceptar), acudir a la carpeta donde lo hayáis descargado y escribir, respetando las mayúsculas javac Mezcla.java con lo que lo compilaréis. Luego, cada vez que queráis ejecutarlo, basta con poner java Mezcla N siendo N=”Número par de cartas a mezclar“. Por ahora suponemos una baraja que se pueda dividir en dos mitades iguales, por lo que ha de ser múltiplo de dos. Si estáis bajo un sistema GNU/Linux (imagino que cualquiera basado UNIX también) podéis redirigir la salida estándar a un fichero de texto, para guardar los datos que saca haciendo:

java Mezcla N >> mezclaN.txt