Tasowanie Gilbreatha

Tasowanie Gilbreath to sposób na tasowanie talii kart, nazwanej na cześć matematyka Normana Gilbreatha (znanego również z hipotezy Gilbreatha ). Zasada Gilbreatha opisuje właściwości talii, które są zachowywane przez ten typ tasowania, a permutacja Gilbreath to permutacja , którą można utworzyć przez tasowanie Gilbreath.

Opis

Tasowanie Gilbreath składa się z dwóch następujących kroków:

• Rozłóż dowolną liczbę kart z wierzchu talii na nowy stos kart.
• Przemieszaj nowy stos z pozostałą częścią talii.

Różni się od częściej stosowanej procedury dzielenia talii na dwa stosy, a następnie przerzucania stosów tym, że pierwszy krok rozdawania kart odwraca kolejność kart w nowym stosie, podczas gdy przecinanie talii zachowałoby ten porządek.

Zasada Gilbreatha

Chociaż pozornie bardzo losowe, tasowanie Gilbreath zachowuje wiele właściwości początkowej talii. Na przykład, jeśli początkowa talia kart składa się z czarnych i czerwonych kart, to po pojedynczym tasowaniu Gilbreath talia nadal będzie miała tę właściwość, że jeśli zostanie pogrupowana w kolejne pary kart, każda para będzie miała jedną czarną kartę i jedną Czerwona kartka. Podobnie, jeśli tasowanie Gilbreath jest używane na talii kart, w której każda karta ma ten sam kolor co karta cztery pozycje wcześniej, a wynikowa talia jest pogrupowana w kolejne zestawy czterech kart, to każdy zestaw będzie zawierał po jednej karcie każdego koloru . Zjawisko to znane jest jako zasada Gilbreatha i jest podstawą kilku sztuczek karcianych .

Permutacje Gilbreatha

Z matematycznego punktu widzenia tasowanie Gilbreath można opisać permutacjami Gilbreath , permutacjami liczb od 1 do n , które można uzyskać za pomocą tasowania Gilbreath z talią kart oznaczoną tymi liczbami w kolejności. Permutacje Gilbreath charakteryzują się tym, że każdy przedrostek zawiera kolejny zestaw liczb. Na przykład permutacja (5,6,4,7,8,3,2,9,1,10) jest permutacją Gilbreatha dla n = 10, którą można uzyskać, rozdając pierwsze cztery lub pięć kart i mieszając je z całą resztą. Każdy z jego przedrostków (5), (5,6), (5,6,4), (5,6,4,7) itd. zawiera zestaw liczb, które (po posortowaniu) tworzą kolejny podciąg liczby od 1 do 10. Równoważnie, jeśli chodzi o wzorce permutacji , permutacje Gilbreath to permutacje, które unikają dwóch wzorców 132 i 312.

Tasowanie Gilbreath można jednoznacznie określić, określając, które pozycje w wynikowej przetasowanej talii są zajęte przez karty, które zostały odłożone na drugi stos, a które pozycje są zajęte przez karty, które nie zostały rozdane. $Dlatego$ istnieją $sposoby$ wykonania tasowania Gilbreath na . Jednak każdą permutację Gilbreath można uzyskać z dwóch różnych tasowań Gilbreath, ponieważ pierwsza pozycja permutacji mogła pochodzić z jednego z dwóch stosów. Dlatego istnieją $_$

Cykliczne permutacje Gilbreatha rzędu $są$ relacji jeden do jednego z $Displaystyle$ rzeczywistymi , dla których iteracja $x \ mapsto x ^ {2 } + c}$ (począwszy od $u$ podstaw zbioru Mandelbrota jest okresowy z $okresem$ . W tej korespondencji permutacja odpowiadająca danej wartości $}$ numeryczną kolejność posortowanych iteracji dla ${\ displaystyle c$ . Liczba cyklicznych permutacji Gilbreatha (a zatem także liczba rzeczywistych okresowych punktów zbioru Mandelbrota), dla ${\ Displaystyle n = 1,2,3, \ kropek}$ } ciąg całkowity

1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, ... (sekwencja A000048 w OEIS ) .

Ostateczna zasada Gilbreatha

$\\ 3 \\ 4\\5\\6\\7\\8\\9\\10\koniec{macierzy}}\do {\początek{macierzy}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\koniec {macierz}}}$

Oto przykład ilustrujący to twierdzenie. W przypadku talii dziesięciokartowej możemy rozdać cztery karty na małym stosie na stole (jedna po drugiej), a następnie przetasować je, aby doprowadzić do układu π powyżej

Twierdzenie zwane „ostateczną zasadą Gilbreatha” stwierdza, że ​​dla permutacji { $,$$Displaystyle \ {1,2,3, \ kropki, n$ następujące cztery właściwości są równoważne:

• ${\ Displaystyle \ pi}$ jest permutacją Gilbreath.
• Dla każdego $,$ karty $\$$Displaystyle \ pi (1), \ kropki \ pi (j)}$ są modulo ${ \displaystyle j}$ .
• dla każdego $Displaystyle$ k $kj$$\ równoważnik n}$ , jot { $Displaystyle j$${\ Displaystyle \ pi {\ bigl (} (k-1) j + 1 {\ bigr)}, \ pi {\ bigl (} k- 1) j + 2 {\ bigr)}, \ kropki, \ pi (kj)}$ są różne modulo ${\ displaystyle j}$ .
• Dla każdego górne ${$ są kolejne w $, n}$$\ Displaystyle 1,2, \$ kropki