Перетасовка Gilbreath - Gilbreath shuffle

А Перетасовка Gilbreath это способ тасовать колода карт, названная в честь математика Норман Гилбрит (также известен Гипотеза Гилбрета ). Принцип Гилбрита описывает свойства колоды, которые сохраняются при этом типе тасования, а Перестановка Гилбрита это перестановка который может быть сформирован перетасовкой Gilbreath.^[1]

Описание

Перемешивание Gilbreath состоит из следующих двух шагов:^[1]

• Сложите любое количество карт сверху колоды на новую стопку карт.
• Перемешайте новую стопку с оставшейся частью колоды.

Он отличается от более часто используемой процедуры разрезания колоды на две стопки с последующим перемешиванием стопок тем, что на первом этапе сдачи карт порядок карт в новой стопке меняется на обратный, тогда как разрезание колоды сохранит этот порядок.

Принцип Гилбрита

Хотя перетасовка Gilbreath кажется весьма случайной, она сохраняет многие свойства исходной колоды. Например, если исходная колода карт чередуется между черными и красными картами, то после одного тасования Gilbreath колода все еще будет иметь свойство, что если она сгруппирована в последовательные пары карт, каждая пара будет иметь одну черную карту и одну. Красная карточка. Точно так же, если перетасовка Gilbreath используется в колоде карт, где каждая карта имеет ту же масть, что и карта за четыре позиции до этого, и результирующая колода сгруппирована в последовательные наборы из четырех карт, то каждый набор будет содержать по одной карте каждой масти. . Это явление известно как Принцип Гилбрита и является основой для нескольких карточные фокусы.^[1]

Перестановки Gilbreath

Математически перетасовку Gilbreath можно описать следующим образом: Перестановки Gilbreath, перестановки чисел от 1 до п который может быть получен перетасовкой Gilbreath с колодой карт, помеченных этими числами по порядку. Перестановки Гилбрета можно охарактеризовать тем свойством, что каждая префикс содержит последовательный набор чисел.^[1] Например, перестановка (5,6,4,7,8,3,2,9,1,10) является перестановкой Гилбрета для п = 10, которые можно получить, сдав первые четыре или пять карт и смешав их с остальными. Каждый из его префиксов (5), (5,6), (5,6,4), (5,6,4,7) и т. Д. Содержит набор чисел, которые (при сортировке) образуют последовательную подпоследовательность числа от 1 до 10. Эквивалентно, с точки зрения шаблоны перестановок, перестановки Гилбрета - это перестановки, которые избегают двух шаблонов 132 и 312.^[2]

Перетасовку Gilbreath можно однозначно определить, указав, какие позиции в получившейся перетасованной колоде заняты картами, сданными во вторую стопку, и какие позиции заняты картами, которые не были сданы. Следовательно, есть 2^п возможные способы перетасовки Gilbreath на колоде п открытки. Однако каждая перестановка Гилбрета может быть получена из двух разных перетасовок Гилбрета (первая позиция перестановки могла быть получена из любой из двух стопок), поэтому есть 2^п − 1 различные перестановки Гилбрита.^[1][3]

В циклический Гилбритские перестановки порядка п находятся во взаимно однозначном соответствии с действительные числа c для которого итерация ${\displaystyle x\mapsto x^{2}+c}$ (начиная с ${\displaystyle x=0}$) лежащих в основе Набор Мандельброта периодичен с периодом п. В этом соответствии перестановка, соответствующая данному значению c описывает числовой порядок итераций для c.^[1] Количество циклических перестановок Гилбрета (а значит, и количество вещественных периодических точек множества Мандельброта) для п = 1, 2, 3, ..., задается целочисленная последовательность

1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, ... (последовательность A000048 в OEIS ).

Абсолютный принцип 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}}}$

Вот пример, иллюстрирующий теорему. Для десятикарточной колоды мы можем сложить четыре карты в небольшую стопку на столе (одну за другой), а затем перемешать их, чтобы получить расположение π выше.

Теорема (окончательный принцип Гилбрета)

Для перестановки π числа {1, 2, 3,. . . , N} следующие четыре свойства эквивалентны:^[1]

• π - перестановка Гилбрета.
• Для каждого j верхние j карт {π (1), π (2), π (3),. . . , π (j)} различны по модулю j.
• Для каждого j и k, kj ≤ N, j карт {π ((k - 1) j + 1), π ((k - 1) j +2) ,. . . , π (kj)} различны по модулю j.
• Для каждого j верхние j карт идут подряд в 1, 2, 3,. . . , N

Рекомендации

1. Диаконис, Перси; Грэм, Рон (2012), "Глава 5: От принципа Гилбрита к множеству Мандельброта" (PDF), Магическая математика: математические идеи, воплощающие в жизнь великие фокусы, Princeton University Press, стр. 61–83..
2. Велла, Антуан (2002), «Избегание шаблонов в перестановках: линейные и циклические порядки», Электронный журнал комбинаторики, 9 (2): R18, Дои:10.37236/1690, МИСТЕР  2028287. См., В частности, предложение 3.3.
3. Велла (2002) связывает этот результат с количеством перестановок Гилбрета в Симион, Родика; Шмидт, Франк В. (1985), «Ограниченные перестановки», Европейский журнал комбинаторики, 6 (4): 383–406, Дои:10.1016 / s0195-6698 (85) 80052-4, МИСТЕР  0829358.