Gilbreath barajar

Una baraja de Gilbreath es una forma de barajar una baraja de cartas, que lleva el nombre del matemático Norman Gilbreath (también conocido por la conjetura de Gilbreath ). El principio de Gilbreath describe las propiedades de un mazo que se conservan mediante este tipo de barajado, y una permutación de Gilbreath es una permutación que puede formarse mediante una baraja de Gilbreath. ^[1]

Descripción

Una reproducción aleatoria de Gilbreath consta de los dos pasos siguientes: ^[1]

• Reparta cualquier número de cartas de la parte superior de la baraja en una nueva pila de cartas.
• Riffle la nueva pila con el resto del mazo.

Se diferencia del procedimiento más comúnmente utilizado de cortar una baraja en dos pilas y luego revolver las pilas, en que el primer paso de repartir cartas invierte el orden de las cartas en la nueva pila, mientras que cortar la baraja preservaría este orden.

Principio de Gilbreath

Aunque aparentemente es muy aleatorio, las barajas de Gilbreath conservan muchas propiedades del mazo inicial. Por ejemplo, si la baraja de cartas inicial alterna entre cartas negras y rojas, luego de un solo barajado de Gilbreath, la baraja seguirá teniendo la propiedad de que, si se agrupa en pares consecutivos de cartas, cada pareja tendrá una carta negra y una tarjeta roja. De manera similar, si se usa un barajado de Gilbreath en una baraja de cartas donde cada carta tiene el mismo palo que la carta cuatro posiciones anteriores, y la baraja resultante se agrupa en conjuntos consecutivos de cuatro cartas, entonces cada conjunto contendrá una carta de cada palo. . Este fenómeno se conoce como el principio de Gilbreath y es la base de varios trucos de cartas . ^[1]

Permutaciones de Gilbreath

Matemáticamente, las combinaciones de Gilbreath se pueden describir mediante permutaciones de Gilbreath , permutaciones de los números del 1 al n que se pueden obtener mediante una combinación de Gilbreath con una baraja de cartas etiquetadas con estos números en orden. Las permutaciones de Gilbreath se pueden caracterizar por la propiedad de que cada prefijo contiene un conjunto de números consecutivos. ^[1] Por ejemplo, la permutación (5,6,4,7,8,3,2,9,1,10) es una permutación de Gilbreath para n = 10 que puede obtenerse repartiendo las primeras cuatro o cinco cartas y mezclándolas con el resto. Cada uno de sus prefijos (5), (5,6), (5,6,4), (5,6,4,7), etc.contiene un conjunto de números que (cuando se ordenan) forman una subsecuencia consecutiva del números del 1 al 10. De manera equivalente, en términos de patrones de permutación , las permutaciones de Gilbreath son las permutaciones que evitan los dos patrones 132 y 312. ^[2]

Un barajado de Gilbreath se puede determinar de forma única especificando cuáles de las posiciones en el mazo barajado resultante están ocupadas por cartas que se repartieron en la segunda pila y qué posiciones están ocupadas por cartas que no se repartieron. Por lo tanto, hay 2 ⁿ formas posibles de realizar un barajado de Gilbreath en una baraja de n cartas. Sin embargo, cada permutación de Gilbreath se puede obtener a partir de dos combinaciones de Gilbreath diferentes (la primera posición de la permutación puede provenir de cualquiera de las dos pilas), por lo que hay 2 ^{n  - 1} permutaciones de Gilbreath distintas. ^{[1] [3]}

Las permutaciones cíclicas de Gilbreath de orden n están en correspondencia uno a uno con los números reales c para los cuales la iteración${\displaystyle x\mapsto x^{2}+c}$ (empezando desde ${\displaystyle x=0}$) subyacente al conjunto de Mandelbrot es periódico con período n . En esta correspondencia, la permutación que corresponde a un valor c dado describe el orden numérico ordenado de las iteraciones para c . ^[1] El número de permutaciones cíclicas de Gilbreath (y por lo tanto también el número de puntos periódicos reales del conjunto de Mandelbrot), para n  = 1, 2, 3, ..., viene dado por la secuencia entera

1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, ... (secuencia A000048 en la OEIS ).

Principio definitivo de Gilbreath

${\displaystyle {\begin{matrix}1\\2\\3\\4\\5\\6\\7\\8\\9\\10\end{matrix}}\to {\begin{matrix}5\\6\\7\\8\\9\\10\end{matrix}}{\begin{matrix}4\\3\\2\\1\end{matrix}}\to {\begin{matrix}4\\5\\6\\3\\7\\2\\8\\9\\1\\10\end{matrix}}}$

Aquí hay un ejemplo que ilustra el teorema. Para un mazo de diez cartas, podemos repartir cuatro cartas en una pequeña pila en la mesa (una por una) y luego mezclarlas para llevar al arreglo π arriba

Teorema (El principio fundamental de Gilbreath)

Para una permutación π de {1, 2, 3,. . . , N}, las siguientes cuatro propiedades son equivalentes: ^[1]

• π es una permutación de Gilbreath.
• Para cada j, las j cartas superiores {π (1), π (2), π (3),. . . , π (j)} son módulos j distintos.
• Para cada j y k con kj ≤ N, las j cartas {π ((k - 1) j + 1), π ((k - 1) j +2) ,. . . , π (kj)} son módulo j distintos.
• Para cada j, las j cartas superiores son consecutivas en 1, 2, 3,. . . , N

Referencias

1. Diaconis, Persi ; Graham, Ron (2012), "Capítulo 5: Del principio de Gilbreath al conjunto de Mandelbrot" (PDF) , Matemáticas mágicas: las ideas matemáticas que animan grandes trucos de magia , Princeton University Press, págs. 61–83.
2. Vella, Antoine (2002), "Evitación de patrones en permutaciones: órdenes lineales y cíclicos" , Electronic Journal of Combinatorics , 9 (2): R18, doi : 10.37236 / 1690 , MR 2028287 . Ver en particular la Proposición 3.3.
3. Vella (2002) atribuye este resultado al número de permutaciones de Gilbreath a Simion, Rodica ; Schmidt, Frank W. (1985), "Permutaciones restringidas", European Journal of Combinatorics , 6 (4): 383–406, doi : 10.1016 / s0195-6698 (85) 80052-4 , MR 0829358 .