Mezcla faro

La mezcla faro es un método de mezcla de naipes por imbricación. Diaconis, Graham y Kantor la llamaban "la técnica" cuando es usada en el contexto cartomágico.

En una mezcla faro perfecta, la baraja se divide en dos partes iguales que luego se intercalan perfectamente una a una. De este modo, si un paquete contenía cartas rojas solamente y el otro cartas negras solamente, se obtendrá un mazo completo con los colores intercalados (rojo, negro, rojo, negro, etcétera).

Una mezcla faro que deje la cartas que inicialmente están encima y debajo del mazo en sus posiciones originales se llama faro exterior (abreviado faro-ext); una que mueva la carta de encima a la segunda posición de arriba, y la carta de debajo a la segunda posición de abajo se llama faro interior (abreviado faro-int).

Historia

La mezcla debe su nombre al un juego de cartas llamado Faro el cual termina con las cartas en dos pilas iguales que el crupier debe combinar para repartirlas para el próximo juego.

Parece haber aparecido por primera vez en 1860 el texto anónimo sobre juegos de azar, A Grand Exposé of the Science of Gambling. El autor describe el barajado junto con una técnica de lijado de los naipes para facilitar una mezcla perfecto. Esto fue esencial porque el recorte de las cartas de mediados del Plantilla:Siglo dejó bordes ásperos que dificultaba el entrelazados perfectos.

Según el mago John Maskelyne, se utilizó el método anterior, y lo llama "mezcla del crupier de faro". Maskelyne fue el primero en dar instrucciones claras, pero la mezcla se usó y se asoció con el juego faro desde antes, como lo descubrió principalmente el matemático y mago Persi Diaconis.

Mezclas perfectas

Una baraja de faro que deja la carta superior original en la parte superior y la carta inferior original en la parte inferior se conoce como una faro exterior, mientras que una que mueve la carta superior original a la segunda y la carta inferior original a la segunda desde abajo se conoce como una faro interior. Estos nombres fueron acuñados por el mago y programador informático Alex Elmsley.

Al ser perfecta no genera permutaciones aleatorias.

En general, $k$ mezclas faro-int volverán a su orden inicial una baraja de $n$ cartas si $2^k\equiv 1(\mathrm{mod}n+1)$. Por ejemplo, 52 faro-int consecutivas logran restaurar el orden de una baraja de 52 cartas, porque $2^{52}\equiv 1(\mathrm{mod}53)$.

En general $k$ mezclas faro-ext volverán a su orden inicial una baraja de $n$ cartas si $2^k\equiv 1(\mathrm{mod}n-1)$. En este caso sólo bastaran 8 faro-ext consecutivas para restaurar el orden de la baraja de 52 cartas, porque $2^8\equiv 1(\mathrm{mod}51)$ y sólo 6 faro-ext son suficientes para restaurar una baraja de 64 cartas.

En otras palabras, el número de mezclas requeridas para volver una baraja de $N$ cartas ($N$ siendo par), es igual al orden multiplicativo de 2 módulo (N + 1) para la mezcla faro interior y módulo (N - 1) para la mezcla faro exterior.

Por ejemplo, para una baraja N = 2, 4, 6, 8, 10, 12..., el número de mezclas necesarias son: 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, ... (secuencia A002326 en OEIS).

De acuerdo con Conjetura de Artin sobre raíces primitivas se deduce que hay infinitos tamaños de mazos que requieren el conjunto completo de $n$ mezclas.

Ejemplo

Por simplicidad se utilizará una baraja de 6 cartas.

Las siguientes tablas muestran el orden de la baraja luego de realizar k-mezclas, volviendo al orden inicial luego de 3 mezclas faro-int y 4 para las faro-ext.

Plantilla:Columnas

Faro Interior

	Posiciones
$k$	1	2	3	4	5	6
$0$	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color
$1$	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color
$2$	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color
$3$	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color

Faro Exterior

	Posiciones
$k$	1	2	3	4	5	6
$0$	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color
$1$	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color
$2$	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color
$3$	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color
$4$	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color	Plantilla:Color

Superior a la enésima posición

El mago y programador Alex Elmsley descubrió que se puede mover la carta superior a la posición $k$ utilizando sólo mezclas faro. El truco consiste en expresar $k-1$ como número binario y realizar faro-int para cada 1 y faro-ext para cada 0.

Por ejemplo, para mover la carta superior a la posición $k=11$ se debe expresar el número 10 ($k-1$) en sistema binario (1010₂) y realizar luego las mezclas Interior-Exterior-Interior-Exterior y así mover la carta que originalmente estaba en la posición superior a la posición 11.

La operación inversa (mover la carta de la posición $k$ a superior) es una operación ma compleja y ha sido un problema que ha estado abierto por 50 años, resuelto en 2018 por Persi Diaconis y Ron Graham.

Teoría de grupos

En matemáticas, una mezcla faro puede ser considerada como un elemento de un grupo de simetría.

Más generalmente, una mezcla perfecta es la permutación que divide el conjunto en dos pilas y las entremezcla:

$S_{2n}=\left(\begin{array}{ccccc}1& 2& 3& 4& \cdots \\ 1& n+1& 2& n+2& \cdots \end{array}\right)$

En otras palabras, es el mapa:

$k\mapsto \{\begin{array}{cc}\lceil \frac{k+1}{2}\rceil & k\text{impar}\\ n+\frac{k}{2}& k\text{par}\end{array}$

Análogamente, la mezcla $(k,n)$-perfecta es el elemento $S_{kn}$ que divide el conjunto en $k$ pilas y la entremezcla:

La mezcla mezcla $(2,n)$-perfecta denotada como ${\rho }_n$ es la composición de la mezcla $(2,n-1)$-perfecta con un $n$-ciclo así que el signo de ${\rho }_n$ es:

$\text{sgn}({\rho }_n)=(-1{)}^{n+1}\text{sgn}({\rho }_{n-1})$.

Por lo tanto el signo es $4$-periódico:

$\text{sgn}({\rho }_n)=(-1{)}^{\lfloor n/2\rfloor }=\{\begin{array}{cc}+1& n\equiv 0,1(\mathrm{mod}4)\\ -1& n\equiv 2,3(\mathrm{mod}4)\end{array}$

Las primeras mezcla perfectas ${\rho }_0$ y ${\rho }_1$ son triviales y ${\rho }_2$ es la transposición simple $(23)\in S_4$.

Arquitectura computacional

Diagrama de algoritmo de reducción paralela using Shuffle (SHFL)

Además de su uso en cartomagia, la mezcla faro es un concepto muy útil en arquitectura computacional. El principal problema en la computación paralela es la comunicación entre los elementos procesados. Es así que las mezclas perfectas fueron estudiadas en varias oportunidades como algorimos de reducción con el fin de optimizar las interconexiones de las redes de procesamiento.

En el libro Gpu-Based Parallel Implementation of Swarm Intelligence Algorithms de Ying Tan, presenta una implementación de la mezcla introducida en la arquitectur Kepler, permitiendo el intercambio de una variable entre subprocesos dentro de la misma urdimbre sin el uso de memoria compartida. En comparación con la reducción basada en memoria compartida, la implementación basada en la mezcla perfecta puede ser más rápida, alcanzando una mejora de hasta el 40% en varios tamaños de bloques.

Esta permutación se puede realizar muy rápidamente usando óptica clásica. Pero para lograr flexibilidad, la mezcla faro debe complementarse con las llamadas "cajas de intercambio". Estas cajas ofrecen la posibilidad de intercambiar dos elementos adyacentes, o no intercambiarlos, lo que generalmente se denomina bypass.

En un ordenador óptico digital, se puede implementar de varias formas. Se podrían utilizar fibras ópticas u ópticas integradas similares a una computadora electrónica convencional. Pero ese enfoque requeriría una mayor cantidad de conexiones de materiales. La mezcla óptica con propagación en el espacio libre se puede implementar mediante hologramas u óptica clásica.