Гилрает перетасовка способ перетасовать колоду карт, названную в честь математика Норман Гилрает (также известную гипотезу гильбрайта ). Принцип Гилбрета описывает свойства колоды, которые сохраняются при этом типе тасования, а перестановка Гилбрета - это перестановка, которая может быть образована тасованием Гилбрета. [1]
Описание
Перемешивание Gilbreath состоит из следующих двух шагов: [1]
- Сложите любое количество карт сверху колоды на новую стопку карт.
- Перемешайте новую стопку с оставшейся частью колоды.
Он отличается от более часто используемой процедуры разделения колоды на две стопки и последующего перемешивания стопок тем, что на первом этапе раздачи карт порядок карт в новой стопке меняется на обратный, тогда как разрезание колоды сохранит этот порядок.
Принцип Гилбрита
Хотя перетасовка Gilbreath кажется очень случайной, она сохраняет многие свойства исходной колоды. Например, если исходная колода карт чередуется между черными и красными картами, то после одного тасования Gilbreath колода все еще будет иметь свойство, что, если она сгруппирована в последовательные пары карт, каждая пара будет иметь одну черную карту и одну. Красная карточка. Точно так же, если тасование Gilbreath используется в колоде карт, где каждая карта имеет ту же масть, что и карта на четыре позиции до этого, и результирующая колода сгруппирована в последовательные наборы из четырех карт, то каждый набор будет содержать по одной карте каждой масти. . Этот феномен известен как принцип Гилбрета и лежит в основе нескольких карточных фокусов . [1]
Перестановки Gilbreath
Математически тасование Гилбрета может быть описано перестановками Гилбрета , перестановками чисел от 1 до n, которые могут быть получены путем перемешивания Гилбрета с колодой карт, помеченных этими числами по порядку. Перестановки Гилбрета можно охарактеризовать тем свойством, что каждый префикс содержит последовательный набор чисел. [1] Например, перестановка (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]
Перетасовка Gilbreath может быть однозначно определена путем указания, какие позиции в получившейся перетасованной колоде заняты картами, сданными во вторую стопку, и какие позиции заняты картами, которые не были сданы. Следовательно, есть 2 n возможных способов перетасовать колоду из n карт. Однако каждая перестановка Гилбрета может быть получена из двух разных тасовок Гилбрета (первая позиция перестановки могла быть получена из любой из двух стопок), поэтому существует 2 n - 1 различных перестановок Гилбрета. [1] [3]
Эти циклические Гилрают перестановки порядка п находятся во взаимно-однозначном соответствии с действительными числами с , для которых итерации (начиная с ), лежащая в основе множества Мандельброта, периодичен с периодом n . В этом соответствии перестановка, соответствующая данному значению c, описывает числовой отсортированный порядок итераций для c . [1] Количество циклических перестановок Гилбрета (и, следовательно, также количество вещественных периодических точек множества Мандельброта) для n = 1, 2, 3, ... задается целочисленной последовательностью
Абсолютный принцип Gilbreath
- Теорема (абсолютный принцип Гилбрета)
- Для перестановки π числа {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
Рекомендации
- ^ a b c d e f g Диаконис, Перси ; Грэм, Рон (2012), «Глава 5: От принципа Гилбрита к множеству Мандельброта» (PDF) , « Магическая математика: математические идеи, воплощающие в жизнь великие фокусы» , Princeton University Press, стр. 61–83.
- ^ Велья, Антуан (2002), "предотвращение перестановок в шаблон: линейные и циклические порядки" , Электронный журнал Комбинаторика , 9 (2): R 18, DOI : 10,37236 / 1690 , МР 2028287. См., В частности, предложение 3.3.
- ^ Велла (2002) приписывает этот результат количеству перестановок Гилбрита в Симион, Родика ; Шмидт, Фрэнк В. (1985), "Restricted перестановок", Европейский журнал комбинаторика , 6 (4): 383-406, DOI : 10.1016 / s0195-6698 (85) 80052-4 , MR 0829358.