El Problema de la Mezcla de Cartas

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

Únete a la conversación

11 comentarios

  1. Martin Gardner comenta en uno de sus libros que la mezcla perfecta se llama mezcla Faraón. Parece ser que un amigo mago de Gardner se especializó en hacer las mezclas faraón lo más rápido posible; es bastante habilidoso.
    Saludos!

  2. No quisiera equivocarme pero la Mezcla perfecta es «Mezcla Faro».
    Aunque en esta época de examenes he abandonado el problema, creo que lo retomaré con algo de fuerza. Si no voy mal encaminado creo que he conseguido indagando un poco por la internet una posible solución, aún así tengo que intentar comprenderla bien y dejar que sigais discurriendo.

  3. Muy interesante el descubrimiento de la increible relación entre la función fi de Euler y el número de iteraciones. Lástima que haya casos en los que parece no tener nada que ver, a ver si lo estudias algo mejor y sacas algo en claro, que cuando me lo comentaste no vi ningún patrón entre los que no cuadraban.

    Marcos ¡Qué habilidoso ha de ser el mago del que hablas! Tiene que ser francamente difícil lograr hacer la mezcla perfecta. Cuando pensé en el problema me vino a la idea inmediatamente el uso para un mago, pudiendo hacer N mezclas perfectas y lograr el orden de nuevo. ¿Supongo que no tendrás más información al respecto?

    ¡Saludos!

  4. La mezcla americana perfecta de la que habláis se conoce en el mundo de la magia como mezcla faro y es muy utilizada por los magos, en gran parte debido a las propiedades matemáticas que tiene. Es difícil realizarla, pero con un poco de práctica se puede hacer (a mi me sale!).
    En fin, me parece muy interesante este artículo, y de hecho, estoy realizando un trabajo de investigación sobre los diferentes tipos de mezclas. Me gustaría saber dónde estan las conclusiones posteriores de las que habláis al final del artículo.
    Gracias!!

Deja un comentario

Responder a Marcos Cancelar la respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *