ファロシャッフル

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

数学者は、デッキを26枚のカードの2つの均等な山に正確に並べ替え、それらを完璧に交互に配置することを説明するときに「ファロシャッフル」という用語を使用します。^[2]

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

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

ファロ シャッフルは、デッキを完全にランダム化しない制御されたシャッフルです。

カードが完全に交互に並ぶ完璧なファロシャッフルを行うには、シャッフルする人がデッキを 2 つの均等なスタックに切り分け、ハーフデッキを互いに押し込むときに適切な圧力をかける必要があります。

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

アウトシャッフルは、一番上と一番下のカードを取り除き、残りのカードでインシャッフルを行い、一番上と一番下のカードを元の位置に戻すのと同じ結果になります。アウトシャッフルを繰り返しても、デッキ全体の順序を逆にすることはできず、中央の n−2 枚のカードのみを逆にすることができます。ファロシャッフルに関する数学の定理は、アウトシャッフルに言及する傾向があります。

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

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

一般に、の場合、完全なインシャッフルによって カード 枚のデッキの順序が復元されます。たとえば、 の理由により、52 回連続してインシャッフルすると 52 枚のカード デッキの順序が復元されます。 ${\displaystyle k}$${\displaystyle n}$${\displaystyle 2^{k}\equiv 1{\pmod {n+1}}}$${\displaystyle 2^{52}\equiv 1{\pmod {53}}}$

一般に、の場合、完全なアウトシャッフルにより 枚のカードのデッキの順序が復元されます。たとえば、 回のアウトシャッフルを続けて実行できれば、 の理由により、 52 枚のカードのデッキは元の順序に戻ります。ただし、 64 枚のカードのデッキの順序を復元するには、 回のファロ アウトシャッフルのみが必要です。 ${\displaystyle k}$${\displaystyle n}$${\displaystyle 2^{k}\equiv 1{\pmod {n-1}}}$${\displaystyle 2^{8}\equiv 1{\pmod {51}}}$

言い換えれば、偶数サイズ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]

無限シーケンスのアウトシャッフルに類似した操作は、インターリーブシーケンスです。

簡単にするために、6 枚のカードのデッキを使用します。

以下は、各インシャッフル後のデッキの順序を示しています。このサイズのデッキは、3 回のインシャッフル後に元の順序に戻ります。

以下は、各アウトシャッフル後のデッキの順序を示しています。このサイズのデッキは、4 回のアウトシャッフル後に元の順序に戻ります。

マジシャンのアレックス・エルムズリーは、制御された一連のインシャッフルとアウトシャッフルを使用して、デッキの一番上のカードを任意の位置に移動できることを発見しました^{[要出典] 。そのトリックは、カードの望ましい位置を}2進数で表し、1ごとにインシャッフルを行い、0ごとにアウトシャッフルを行うことです。

たとえば、一番上のカードを下に移動して、その上に 10 枚のカードがあるようにするには、10 という数字を 2 進数で表します (1010 ₂ )。シャッフル イン、アウト、イン、アウト。デッキの上から 10 枚のカードを配ります。11 枚目が元のカードになります。10 という数字を 1010 ₂と表しても、 00001010 ₂と表しても問題ないことに注意してください。アウトシャッフルでは常に一番上のカードが上に来るため、予備的なアウトシャッフルは結果に影響しません。

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

より一般的には、 において、完全なシャッフルとは、集合を 2 つの山に分割し、それらを交互に配置する順列です。 ${\displaystyle S_{2n}}$

${\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{odd}}\\n+{\frac {k}{2}}&k\ {\text{even}}\end{cases}}}$

同様に、完全シャッフル順列^[9]は、集合をk個の山に分割し、それらをインターリーブするの元である。 ${\displaystyle (k,n)}$${\displaystyle S_{kn}}$

と表記される -完全シャッフルは、-完全シャッフルと-サイクルの合成であるため、 の符号は次のようになります。 ${\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). 「Multiway Perfect Shuffle Permutation のサイクル」(PDF) .離散数学と理論計算機科学. 5 : 169–180. doi :10.46298/dmtcs.308 . 2013 年12 月 26 日閲覧。

• マスケリン、ジョン(1894)。シャープスとフラッツ: チャンスとスキルのゲームでの不正行為の秘密の完全な暴露。ロングマンズ、グリーンアンドカンパニー。2013年12月26日閲覧。

• モリス、S. ブレント (1998)。『マジックトリック、カードシャッフル、およびダイナミックコンピュータメモリ』アメリカ数学協会。ISBN 0-883-85527-5. 2013年12月26日閲覧。

• コラタ、ジーナ (1982年4 月)。「パーフェクト シャッフルと数学との関係」。サイエンス。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]。