El verano trae consigo irremediablemente jugar a las cartas m\u00e1s a menudo que de costumbre. Bien sean las noches sentados en el c\u00e9sped, como los descansos del estudio en la biblioteca para el caf\u00e9.<\/p>\n
Y si hay algo com\u00fan a todos los juegos de cartas es barajarlas para poder repartirlas de la forma m\u00e1s aleatoria posible. Me gusta hacer la cl\u00e1sica 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<\/em>, pero Googleando un poco, parece ser que le llaman<\/a> Riffle Shuffle<\/em>.<\/p><\/a> Un d\u00eda pens\u00e9 \u00bfY si se hace la mezcla perfecta?<\/strong> 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<\/strong>. Entonces me plante\u00e9 qu\u00e9 ocurrir\u00eda si se repet\u00eda ese proceso varias veces \u00bfSe volver\u00eda a la posici\u00f3n inicial? Y de ser as\u00ed \u00bfEn cu\u00e1ntas veces?<\/p>\n Quiero que quede claro ya desde aqu\u00ed que no es una cuesti\u00f3n estad\u00edstica<\/strong>. No estamos haciendo una mezcla normal, en la que las cartas quedan de forma aleatoria cada vez, sino una totalmente definida y que est\u00e1 claro que siempre ser\u00e1 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\u00ed la probabilidad est\u00e1 fuera de lugar.<\/p>\n Al principio no pas\u00f3 de un simple pensamiento veraniego, pero dos o tres d\u00edas despu\u00e9s lo record\u00e9 estando con mis amigos en un bar y les coment\u00e9 el problema, as\u00ed que tras pensarlo un poco empezamos a escribir en una servilleta c\u00f3mo iba evolucionando el conjunto de cartas. Lo hicimos muy resumido, s\u00f3lo las primeras y \u00faltimas cartas de cada mitad, con puntos suspensivos por en medio, para tratar de imaginar c\u00f3mo se iba comportando. En que llegamos a la tercera iteraci\u00f3n nos dimos cuenta de que era una tarea tediosa y puramente mec\u00e1nica, as\u00ed que decid\u00ed hacer un programa al d\u00eda siguiente que lo ejecutase.<\/p>\n La tarde posterior program\u00e9 lo necesario para hacer las iteraciones, y 56 l\u00edneas despu\u00e9s<\/a> empec\u00e9 a probar resultados. El problema no hubiera pasado de ah\u00ed, de no ser porque las soluciones se escapaban de lo predecible. \u00bfQui\u00e9n iba a pensar que las veces que hay que barajar no aumentan con el n\u00famero de cartas? \u00bfC\u00f3mo iba a imaginar que con 40 naipes hacen falta 12 mezclas y con 64 solo 6? Cuantos m\u00e1s conjuntos de cartas probaba, m\u00e1s sorprendido me quedaba.<\/p>\n As\u00ed que fui envenenando a diferentes amigos con el problema, picando la curiosidad de todos, hasta que me descubr\u00ed buscando las ecuaciones que definen el problema. Desgraciadamente s\u00f3lo uno se lo est\u00e1 \u00abtomando en serio\u00bb<\/em> y nos estamos quedando sin ideas. Necesitamos un soplo de aire fresco de alguien con nuevas ideas, pues las que ten\u00edamos las hemos explotado bastante.<\/p>\n Yo consegu\u00ed una ecuaci\u00f3n recursiva definida en dos trozos que explicaba a d\u00f3nde iba la carta, y que aplic\u00e1ndola iterativamente hasta que la posici\u00f3n volv\u00eda a ser la original, daba el n\u00famero de mezclas. \u00c9l, matem\u00e1tico, lo analiz\u00f3 como una matriz, aplicando transformaciones y obteniendo la soluci\u00f3n como la matriz unidad, con vectores propios y diagonalizaci\u00f3n. Yo ahora estoy empezando con grafos y me he dado cuenta de que me equivoqu\u00e9 en una premisa inicial, por lo que la f\u00f3rmula que ten\u00eda no es esencialmente correcta. Ahora pongo algunos conjuntos de ejemplo, por si a alguien no le ha quedado claro c\u00f3mo se mezcla.<\/p>\n Conjunto de 8 cartas. [1, 2, 3, 4, 5, 6, 7, 8]<\/strong> Vuelta n\u00famero 2<\/em> Vuelta n\u00famero 3<\/em> As\u00ed se puede ver como, para 8 cartas, con mezlcar 3 veces, volvemos a la posici\u00f3n de partida. Conjunto de 52 cartas.<\/strong> Vuelta n\u00famero 2<\/em> Vuelta n\u00famero 3<\/em> Vuelta n\u00famero 4<\/em> Vuelta n\u00famero 5<\/em> Vuelta n\u00famero 6<\/em> Vuelta n\u00famero 7<\/em> Vuelta n\u00famero 8<\/em> De todas las personas con las que he hablado, ninguno hab\u00eda escuchado jam\u00e1s este problema, as\u00ed que si ya existe formulado como tal, quiz\u00e1s no sea muy famoso. Aunque este blog no lo lee mucha gente espero que alguien se anime, o se lo cont\u00e9is a alguien que pueda interesarle, a m\u00ed por lo menos me tiene atrapado.<\/p>\n Dentro de un par de semanas o as\u00ed publicar\u00e9 todo lo que hemos averiguado hasta ahora, que tampoco es mucho, pero tenemos el problema m\u00e1s o menos cogido por algunos puntos.<\/p>\n Asumo que todos ten\u00e9is la m\u00e1quina Java instalada en vuestro ordenador. Para utilizar el programa que hice<\/a> ten\u00e9is que ir al S\u00edmbolo del Sistema (Inicio > ejecutar > cmd<\/em> > Aceptar), acudir a la carpeta donde lo hay\u00e1is descargado y escribir, respetando las may\u00fasculas javac Mezcla.java<\/em> con lo que lo compilar\u00e9is. Luego, cada vez que quer\u00e1is ejecutarlo, basta con poner java Mezcla N<\/em> siendo N=\u00bbN\u00famero par de cartas a mezclar<\/em>\u00ab. Por ahora suponemos una baraja que se pueda dividir en dos mitades iguales, por lo que ha de ser m\u00faltiplo de dos. Si est\u00e1is bajo un sistema GNU\/Linux (imagino que cualquiera basado UNIX tambi\u00e9n) pod\u00e9is redirigir la salida est\u00e1ndar a un fichero de texto, para guardar los datos que saca haciendo:<\/p>\n java Mezcla N >> mezclaN.txt<\/em><\/p>\n<\/div>
\nVuelta n\u00famero 1<\/em>
\nPrimera mitad: [1, 2, 3, 4]
\nSegunda mitad: [5, 6, 7, 8]
\nMazo mezclado: [1, 5, 2, 6, 3, 7, 4, 8]<\/p>\n
\nPrimera mitad: [1, 5, 2, 6]
\nSegunda mitad: [3, 7, 4, 8]
\nMazo mezclado: [1, 3, 5, 7, 2, 4, 6, 8]<\/p>\n
\nPrimera mitad: [1, 3, 5, 7]
\nSegunda mitad: [2, 4, 6, 8]
\nMazo mezclado: [1, 2, 3, 4, 5, 6, 7, 8]<\/p><\/blockquote>\n
\nCopio, ahora, la soluci\u00f3n para 52 naipes, la baraja francesa.<\/p>\n
\nVuelta n\u00famero 1<\/em>
\nPrimera 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]
\nSegunda 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]
\nMazo 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]<\/p>\n
\nPrimera 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]
\nSegunda 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]
\nMazo 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]<\/p>\n
\nPrimera 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]
\nSegunda 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]
\nMazo 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]<\/p>\n
\nPrimera 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]
\nSegunda 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]
\nMazo 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]<\/p>\n
\nPrimera 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]
\nSegunda 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]
\nMazo 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]<\/p>\n
\nPrimera 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]
\nSegunda 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]
\nMazo 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]<\/p>\n
\nPrimera 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]
\nSegunda 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]
\nMazo 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]<\/p>\n
\nPrimera 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]
\nSegunda 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]
\nMazo 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]<\/p><\/blockquote>\n