Gilbreath-shuffle

Een Gilbreath-shuffle is een manier om een pak kaarten te schudden, genoemd naar de wiskundige Norman Gilbreath (ook bekend van het vermoeden van Gilbreath). Het principe van Gilbreath beschrijft de eigenschappen van een kaartspel die behouden blijven door dit type shuffle, en een Gilbreath-permutatie is een permutatie die kan worden gevormd door een Gilbreath-shuffle.

Beschrijving

Een Gilbreath-shuffle bestaat uit de volgende twee stappen:

• Deel een willekeurig aantal kaarten van de bovenkant van een stapel uit om een tweede stapel kaarten te vormen.
• Meng de 2 stapels door mekaar zoals bij bridge de gewoonte is (door ze met de duimen op te tillen en in mekaar te laten vallen).

Dit verschilt van de meer algemeen gebruikte procedure waarbij een kaartspel in twee stapels wordt gesneden en vervolgens door mekaar gemengd, doordat eerst de volgorde van de kaarten in een van de stapels wordt omgekeerd.

Het principe van Gilbreath

Hoewel een Gilbreath-shuffle schijnbaar zeer willekeurig is, behoudt de nieuwe stapel veel eigenschappen van de oorspronkelijke stapel. Als het aanvankelijke kaartspel bijvoorbeeld afwisselend zwarte en rode kaarten bevatte, zal het kaartspel na een enkele Gilbreath-shuffle nog steeds de eigenschap hebben dat, als het in opeenvolgende paren kaarten is gegroepeerd, elk paar één zwarte kaart en één rode kaart heeft. En als een Gilbreath-shuffle wordt gebruikt op een kaartspel te schudden waarbij elke kaart dezelfde kleur heeft als de kaart vier posities eerder, en het resulterende kaartspel is gegroepeerd in opeenvolgende sets van vier kaarten, dan zal elke set één kaart van elke kleur bevatten. Dit fenomeen staat bekend als het principe van Gilbreath en vormt de basis voor verschillende kaarttrucs.

Gilbreath-permutaties

Wiskundig gezien kunnen Gilbreath-shuffles worden beschreven door Gilbreath-permutaties, permutaties van de getallen van 1 tot n die kunnen worden verkregen door een Gilbreath-shuffle met een pak kaarten waarop deze getallen in volgorde zijn gelabeld. Gilbreath-permutaties kunnen worden gekenmerkt door de eigenschap dat elke deelreeks aan het begin een opeenvolgende reeks getallen bevat. De permutatie (5,6,4,7,8,3,2,9,1,10) is bijvoorbeeld een Gilbreath-permutatie voor n = 10 die kan worden verkregen door de eerste vier of vijf kaarten uit te delen en deze met de rest te delen. Elke deelreeks aan het begin (5), (5,6), (5,6,4), (5,6,4,7), etc. bevat een reeks getallen die (indien gesorteerd) op mekaar volgen. Op basis van de permutatiepatronen zijn de Gilbreath-permutaties de permutaties die de twee patronen 132 en 312 vermijden.

Een Gilbreath-shuffle kan op unieke wijze worden bepaald door te specificeren welke van de posities in het resulterende geschudde kaartspel worden ingenomen door kaarten die op de tweede stapel zijn uitgedeeld, en welke posities worden ingenomen door kaarten die niet zijn uitgedeeld. Daarom zijn er $2^{n}$ mogelijke manieren om een Gilbreath-shuffle uit te voeren op een kaartspel van $n$ kaarten. Elke Gilbreath-permutatie kan echter worden verkregen uit twee verschillende Gilbreath-shuffles, aangezien de eerste positie van de permutatie afkomstig kan zijn van een van de twee stapels. Daarom zijn er $2^{n-1}$ verschillende Gilbreath-permutaties.

De cyclische Gilbreath-permutaties van orde $n$ zijn in één-op-één correspondentie met de reële getallen $c$ waarvoor de iteratie $x\mapsto x^{2}+c$ (beginnend vanaf $x=0$ ) die ten grondslag ligt aan de Mandelbrot-verzameling periodiek is met periode $n$. In deze correspondentie beschrijft de permutatie die overeenkomt met een bepaalde waarde $c$ de numeriek gesorteerde volgorde van de iteraties voor $c$. Het aantal cyclische Gilbreath-permutaties (en dus ook het aantal reële periodieke punten van de Mandelbrot-verzameling), voor $n=1,2,3,\dots$, wordt gegeven door de reeks gehele getallen:

1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, ... (reeks A000048 in de OEIS).

Ultieme Gilbreath-principe

${\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}}$

Hier is een voorbeeld dat het principe illustreert. We kunnen van een stapel van 10 kaarten 4 kaarten op tafel aftellen en ze dan mengen met de rest, wat leidt tot de combinatie π hierboven

Een stelling genaamd "het ultieme Gilbreath-principe" stelt dat, voor een permutatie $\pi$ van $\{1,2,3,\dots ,n\}$ de volgende vier eigenschappen gelijkwaardig zijn:

• $\pi$ is een Gilbreath-permutatie.
• Voor elk $j$, zijn de bovenste $j$ kaarten $\pi (1),\dots \pi (j)$ verschillend modulo $j$ .
• Voor elke $j$ en $k$ met $kj\leq n$, zijn de $j$ kaarten $\pi {\bigl (}(k-1)j+1{\bigr )},\pi {\bigl (}k-1)j+2{\bigr )},\dots ,\pi (kj)$ verschillend modulo $j$ .
• Voor elke $j$, zijn de bovenste $j$ kaarten opeenvolgend in $1,2,\dots ,n$ .