Тасование Гилбрита: принцип и математика

Метод перетасовки колоды карт

Тасование Гилбрита (Gilbreath shuffle) — это способ перетасовки колоды карт, названный в честь математика Нормана Гилбрита (Norman Gilbreath), известного также своей гипотезой Гилбрита.

Принцип Гилбрита описывает свойства колоды, которые сохраняются при таком типе тасования, а перестановка Гилбрита — это перестановка, которая может быть получена в результате тасования Гилбрита.

Описание

Тасование Гилбрита состоит из двух этапов:

• Снять с верхней части колоды любое количество карт, образуя вторую кучку.
• Перетасовать новую кучку с оставшейся частью колоды способом «рифл» (перемешивание краями).

Это отличается от более распространённого способа разделения колоды на две части с последующим рифл-тасованием тем, что первый этап снятия карт обращает порядок карт в новой кучке, тогда как простое разделение колоды сохраняет этот порядок.

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

Несмотря на кажущуюся случайность, тасования Гилбрита сохраняют множество свойств исходной колоды. Например, если исходная колода чередует чёрные и красные карты, то после одного тасования Гилбрита колода сохранит свойство, что при группировке в последовательные пары каждая пара будет содержать одну чёрную и одну красную карту. Аналогично, если применить тасование Гилбрита к колоде, где каждая карта имеет ту же масть, что и карта на четыре позиции раньше, и разбить результат на последовательные группы по четыре карты, то каждая группа будет содержать по одной карте каждой масти. Это явление известно как принцип Гилбрита и лежит в основе нескольких карточных фокусов.

Перестановки Гилбрита

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

Тасование Гилбрита может быть однозначно определено указанием того, какие позиции в результирующей перетасованной колоде занимают карты, снятые во вторую кучку, и какие позиции занимают карты, которые не были сняты. Поэтому существует 2ⁿ возможных способов выполнить тасование Гилбрита на колоде из n карт. Однако каждая перестановка Гилбрита может быть получена двумя разными тасованиями Гилбрита, так как первая позиция перестановки могла произойти из любой из двух кучек. Поэтому существует 2ⁿ⁻¹ различных перестановок Гилбрита.

Циклические перестановки Гилбрита порядка n находятся во взаимно однозначном соответствии с вещественными числами c, для которых итерация x ↦ x² + c (начиная с x = 0), лежащая в основе множества Мандельброта, является периодической с периодом n. В этом соответствии перестановка, соответствующая данному значению c, описывает численный отсортированный порядок итераций для c. Количество циклических перестановок Гилбрита (и, следовательно, количество вещественных периодических точек множества Мандельброта) для n = 1, 2, 3, … задаётся целочисленной последовательностью 1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170, 315, 585, 1091, …

Универсальный принцип Гилбрита

Теорема, называемая «универсальным принципом Гилбрита», утверждает, что для перестановки π множества {1, 2, 3, …, n} следующие четыре свойства эквивалентны:

• π является перестановкой Гилбрита.
• Для каждого j верхние j карт π(1), …, π(j) различны по модулю j.
• Для каждых j и k, где kj ≤ n, j карт π((k−1)j+1), π((k−1)j+2), …, π(kj) различны по модулю j.
• Для каждого j верхние j карт являются последовательными в последовательности 1, 2, …, n.