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

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

Перетасовка Гилбрета состоит из следующих двух шагов: ^[1]

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

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

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

Математически перетасовки Гилбрета можно описать перестановками Гилбрета , перестановками чисел от 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 может быть однозначно определена путем указания того, какие позиции в перетасованной колоде занимают карты, которые были розданы во вторую стопку, а какие позиции занимают карты, которые не были розданы. Таким образом, существуют возможные способы выполнения перетасовки Gilbreath на колоде карт. Однако каждая перестановка Gilbreath может быть получена из двух разных перетасовок Gilbreath, поскольку первая позиция перестановки могла быть взята из любой из двух стопок. Таким образом, существуют различные перестановки Gilbreath. ^{[1] [3]}${\displaystyle 2^{n}}$${\displaystyle n}$${\displaystyle 2^{n-1}}$

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

${\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]${\displaystyle \пи}$${\displaystyle \{1,2,3,\точки ,n\}}$

• ${\displaystyle \пи}$является перестановкой Гилбрета.
• Для каждого из них верхние карты различны по модулю .${\displaystyle j}$${\displaystyle j}$${\displaystyle \pi (1),\dots \pi (j)}$${\displaystyle j}$
• Для каждого и с , карты различны по модулю .${\displaystyle j}$${\displaystyle к}$${\displaystyle kj\leq n}$${\displaystyle j}$${\displaystyle \pi {\bigl (}(k-1)j+1{\bigr)},\pi {\bigl (}(k-1)j+2{\bigr)},\dots,\pi (кДж)}$${\displaystyle j}$
• Для каждого верхние карты идут последовательно в .${\displaystyle j}$${\displaystyle j}$${\displaystyle 1,2,\точки ,n}$