ファロシャッフル

ファロシャッフル（アメリカ式）、ウィーブシャッフル（イギリス式）、またはダブテールシャッフルは、トランプをシャッフルする 方法で、デッキの半分を両手に持ち、親指を内側に向け、親指からカードを放して、カードが重なり合うようにテーブルに落とす。ディアコニス、グラハム、カントールは、マジックで使用される場合、このテクニックを「ファロシャッフル」とも呼んでいる。^{[ 1 ]}

数学者は、トランプの山札を26枚のカードからなる2つの等しい山に正確に並べ替え、それらを完全に交互に重ね合わせることを「ファロシャッフル」という用語で表現します。^{[ 2 ]}

右利きの人は、左手で上から、右手で下からカードを持ちます。デッキは、右手の親指で半分のカードを少し持ち上げ、左手の束を右手から前に押し出すことで、できれば均等な2つの部分に分けられます。2つの束は、位置を合わせるために交差させて軽く叩き合わせることがよくあります。次に、短い辺で押し合わせ、上または下に曲げます。すると、カードは交互に、理想的にはジッパーのように、それぞれの半分から1枚ずつ交互に落ちてきます。上から圧力をかけて束を曲げることで、華やかさを加えることができます。^{[ 3 ]}

ファロのゲームは、ディーラーが次のゲームのためにカードを配るために組み合わせなければならない2つの等しい山札で終了します。マジシャンのジョン・マスケリンによると、上記の方法が使用されており、彼はそれを「ファロディーラーのシャッフル」と呼んでいます。^{[ 4 ]}明確な指示を与えたのはマスケリンが最初でしたが、シャッフルはそれ以前からファロで使用され、関連付けられており、主に数学者でマジシャンのパーシー・ディアコニスによって発見されました。^{[ 5 ]}

ファローシャッフルは、デッキを完全にランダム化するのではなく、コントロールされたシャッフルを行う方法です。

完璧なファローシャッフル、つまりカードが完全に交互に並ぶシャッフルを行うには、シャッフルする人がデッキを2つの等しい山に切り分け、それぞれの山を押し合わせる際に適切な圧力をかける必要がある。

元の一番上のカードを一番上に、元の一番下のカードを一番下に残すファロシャッフルはアウトシャッフルと呼ばれ、元の一番上のカードを2番目に、元の一番下のカードを下から2番目に移動させるファロシャッフルはインシャッフルと呼ばれます。これらの名称は、マジシャンでありコンピュータープログラマーでもあるアレックス・エルムズリーによって考案されました。^{[ 6 ]}

アウトシャッフルは、一番上と一番下のカードを取り除き、残りのカードでインシャッフルを行い、最後に一番上と一番下のカードを元の位置に戻すのと同じ結果になります。アウトシャッフルを繰り返しても、デッキ全体の順番を逆にすることはできません。順番を逆にできるのは、真ん中のn-2枚のカードだけです。ファロシャッフルに関する数学的定理は、アウトシャッフルを前提としていることが多いです。

インシャッフルは、デッキの一番上に余分なカードを1枚、一番下に余分なカードを1枚追加し、その拡大したデッキでアウトシャッフルを行い、その後余分なカードを取り除くのと同じ結果になります。インシャッフルを繰り返すと、デッキの順番が逆になることがあります。

完璧なインシャッフルができれば、26回のシャッフルでデッキの順番が逆になり、さらに26回シャッフルすると元の順番に戻ります。^{[ 7 ]}

一般的に、${\displaystyle k}$完璧なインシャッフルは、${\displaystyle n}$-カードデッキの場合${\displaystyle 2^{k}\equiv 1{\pmod {n+1}}}$例えば、52回連続でシャッフルすると、52枚のカードのデッキの順番が元に戻ります。$2^{52}\equiv 1\pmod {53}$。

一般的に、${\displaystyle k}$完璧なアウトシャッフルは、${\displaystyle n}$-カードデッキの場合${\displaystyle 2^{k}\equiv 1{\pmod {n-1}}}$例えば、8回連続でアウトシャッフルを実行できれば、52枚のカードのデッキは元の順番に戻ります。$2^8\equiv 1\pmod 51$しかし、64枚のカードのデッキの順番を元に戻すには、ファロシャッフルを6回行うだけで十分です。

つまり、偶数サイズnのカードのデッキを元の順序に戻すために必要なシャッフルの回数は、 2 を法( n + 1)で割った乗法の順序で与えられます。  

例えば、デッキサイズがn = 2、4、6、8、10、12 ... の場合、必要なインシャッフルの回数は、2、4、3、6、10、12、4、8、18、6、11、... となります( OEISのシーケンスA002326 )。

アルティンの原始根に関する予想によれば、 n回のシャッフルの完全なセットを必要とするデッキサイズは無限に存在することになる。^{[ 8 ]}

無限シーケンスに対するアウトシャッフルに相当する操作は、インターリーブシーケンスです。

マジシャンのアレックス・エルムズリーは、インシャッフルとアウトシャッフルを巧みに組み合わせることで、デッキの一番上のカードを任意の位置に移動できることを発見した。その秘訣は、カードの希望する位置を二進数で表し、1ごとにインシャッフル、0ごとにアウトシャッフルを行うことだ。

例えば、一番上のカードを下にずらして、その上に10枚のカードが来るようにするには、10を2進数で表します（1010 ₂）。カードを出し入れして、10枚を配ります。11枚目が元のカードになります。10を1010 ₂と表しても00001010 ₂と表しても結果は変わらないことに注意してください。出し入れのシャッフルでは一番上のカードが常に一番上に残るため、事前の出し入れのシャッフルは結果に影響しません。

数学では、完全シャッフルは対称群の要素とみなすことができる。

より一般的には、${\displaystyle S_{2n}}$完全シャッフルとは、セットを2つの山に分割し、それらを交互に並べる順列のことです。

${\displaystyle S_{2n}}$=${\displaystyle {\begin{pmatrix}1&2&3&4&\cdots &2n-1&2n\\1&n+1&2&n+2&\cdots &n&2n\end{pmatrix}}}$

言い換えれば、それは地図です

${\displaystyle k\mapsto {\begin{cases}{\frac {k+1}{2}}&k\ {\text{奇数}}\\n+{\frac {k}{2}}&k\ {\text{偶数}}\end{cases}}}$

同様に、${\displaystyle (k,n)}$-完全シャッフル順列^{[ 9 ]}は、${\displaystyle S_{kn}}$これは、集合をk個の山に分割し、それらを交互に配置する。

の${\displaystyle (2,n)}$-パーフェクトシャッフル、表記$\displaystyle \rho _{n}}$は、${\displaystyle (2,n-1)}$-完璧なシャッフル${\displaystyle n}$-サイクルなので、$\displaystyle \rho _{n}}$は：

$\displaystyle {\mbox{sgn}}(\rho _{n})=(-1)^{n+1}{\mbox{sgn}}(\rho _{n-1}).}$

したがって、この符号は4周期的である。

${\displaystyle {\mbox{sgn}}(\rho _{n})=(-1)^{\lfloor n/2\rfloor }={\begin{cases}+1&n\equiv 0,1{\pmod {4}}\\-1&n\equiv 2,3{\pmod {4}}\end{cases}}}$

最初のいくつかの完璧なシャッフルは次のとおりです。$\displaystyle \rho _{0}}$そして$\displaystyle \rho _{1}}$些細なことであり、$\displaystyle \rho _{2}}$転置${\displaystyle (23)\in S_{4}}$。

• Diaconis, ペルシ島;グラハム, ロータリー州;カンター、W.M. (1983)。「完璧なシャッフルの数学」(PDF)。応用数学の進歩。4 (2): 175–196。土井: 10.1016/0196-8858(83)90009-X。

• Ellis, J.; Fan, H.; Shallit, J. (2002). "The Cycles of the Multiway Perfect Shuffle Permutation" (PDF) . Discrete Mathematics & Theoretical Computer Science . 5 308: 169– 180. doi : 10.46298/dmtcs.308 . 2013年12月26日取得.

• マスケリン、ジョン（1894）。『シャープス・アンド・フラッツ：偶然と技能のゲームにおける不正行為の秘密の完全暴露』ロングマンズ・グリーン・アンド・カンパニー。 2013年12月26日取得。

• モリス、S.ブレント（1998）。マジックトリック、カードシャッフル、および動的コンピュータメモリ。アメリカ数学協会。ISBN 0-883-85527-52013年12月26日に取得。

• Kolata, Gina (1982年4月)「パーフェクトシャッフルと数学との関係」Science . 216 (4545): 505–506 . Bibcode : 1982Sci...216..505K . doi : 10.1126/science.216.4545.505 . PMID 17735734 . 

• Jain, Peiyush (2008年5月). 「インシャッフルのためのシンプルなインプレースアルゴリズム」. arXiv : 0805.1598 [ cs.DS ].