倭マン's BLOG

くだらない日々の日記書いてます。 たまにプログラミング関連の記事書いてます。 書いてます。

パーフェクト・シャッフル

古くから知られているトランプの不思議として、「52枚のトランプ(ジョーカーを除く)を8回パーフェクト・シャッフルすると順番が元に戻る」というのがあります。 そこに隠されている数学を少し垣間見てみましょう。

パーフェクト・シャッフルとは?

パーフェクト・シャッフル (perfect shuffle) とは、トランプの切り方(混ぜ方)の1種で、Wikipedia によると

デック(トランプ1束)を正確に2等分し、2つのパケット(2等分したトランプの束それぞれ)を完全に1枚ずつ噛み合わせる

切り方のことです(下図のシャッフル前、シャッフル後も参照)*1。 書くのは簡単ですが、実際にやるのはかなり難しい*2切り方です。

数学的に観れば・・・

数学的に観れば、パーフェクト・シャッフルは置換の問題ですね。 別にパーフェクト・シャッフルに限らず、トランプのシャッフルというのはカードの並びを変えることなので、「シャッフル = 置換」です。

で、せっかく数学的に観るなら、抽象化というか一般化をして、 { N } 枚のカードの場合を考えましょう。 目標は

N 枚のカードにパーフェクト・シャッフルを行うと、何回で元の順番に戻るか?

ってのを調べるってことになります*3。 以下、数学嫌いな人は飛ばして下さい。

パーフェクト・シャッフル何回で元に戻る?

では実際に、「パーフェクト・シャッフル何回で元に戻るか?」を求めてみましょう。 パーフェクト・シャッフルの仕方から、トランプの枚数  { N } は偶数とします。 回数を求める手順は以下の通り:

  1. 1回のシャッフルでトランプがどのように移動するかを求める
  2.  { m } 回のシャッフルでトランプがどのように移動するかを求める
  3.  { m } 回のシャッフルで順番が元に戻る」という条件から、回数を求める

です。

★Step 1★ 1回のシャッフルでのトランプの移動
文章で説明してもわかりにくいので、図にしてみました。 真ん中の状態は便宜上のものです(カード1枚分ずつあけてあるって状態)。 前半分と後半分を1枚ずつ交互に混ぜる際、剰余演算子*4「%」が出てくるのがチョットややこしさを醸し出しますが。 ちなみに、カードの順番が0から始まっているのにご注意を。

結果だけを書くと「n 番目にあったカードは、1回のシャッフルで { (2n) \% (N-1) } に移動する」となります。

★Step 2★  { m } 回のシャッフルでのトランプの移動
1回のシャッフルでカードがどう移動するか分かったので、これを  { m } 回適用すれば「 { m } 回のシャッフルでカードがどう移動するか」が分かります。

剰余演算子(%)を含む式はチョット扱いにくそうですが、今の場合は簡単で、「 { n } 番目にあったカードは、 { m } 回のシャッフルで { (2^m n) \% (N-1) } 番目に移動する」となります。

★Step 3★  { m } 回のシャッフルで順番が元に戻る条件
上記の結果から、「 { m } 回のシャッフルで順番が元に戻る条件」は { (2^m n) \% (N-1) = n } となります。 これを少々書き換えてやると*5

  { \displaystyle \frac{n(2^m-1)}{N-1} } が自然数

となります。 これが任意の  { n } について成り立つためには、

  { \displaystyle \frac{2^m-1}{N-1} } が自然数

となります。 これが求める条件です。

 { N = 52 }のとき

 { N = 52 } のとき  { m = 8 } とすると、

  { \displaystyle \frac{2^8-1}{52-1}=\frac{255}{51}=5 }

となって、確かに条件を満たします。 めでたしめでたし。

でも、一般の  { N } に対して  { m } を求めるのは結構手間が掛かるんですけどね。 これについては後日

*1:ここで扱うのは1番上と1番下のカードは常に入れ替わらない場合のみに限ります。

*2:フジ系「トリビアの泉」でトランプマンが実際にやってましたが。

*3:何度かやれば元に戻るのかってのも全く自明ではありませんが。

*4:自然数 A, B に対して、「A%B」 は「 A を B で割った余り」を表します。 数学では「≡, mod」を使って書く演算。 (C 言語系の)プログラムでは % 記号を使うので、ここではそうしてます。 A ≡ A%B mod B

*5:A を B で割ったときの商が Q、余りがR (=A%B) のとき、「A=BQ+R」が成り立ちます。 これを商 Q について解いてそれが自然数であるとすると「(A-R)/B が自然数」となります。