古くから知られているトランプの不思議として、「52枚のトランプ(ジョーカーを除く)を8回パーフェクト・シャッフルすると順番が元に戻る」というのがあります。 そこに隠されている数学を少し垣間見てみましょう。
パーフェクト・シャッフルとは?
パーフェクト・シャッフル (perfect shuffle) とは、トランプの切り方(混ぜ方)の1種で、Wikipedia によるとデック(トランプ1束)を正確に2等分し、2つのパケット(2等分したトランプの束それぞれ)を完全に1枚ずつ噛み合わせる
切り方のことです(下図のシャッフル前、シャッフル後も参照)*1。 書くのは簡単ですが、実際にやるのはかなり難しい*2切り方です。
数学的に観れば・・・
数学的に観れば、パーフェクト・シャッフルは置換の問題ですね。 別にパーフェクト・シャッフルに限らず、トランプのシャッフルというのはカードの並びを変えることなので、「シャッフル = 置換」です。で、せっかく数学的に観るなら、抽象化というか一般化をして、 枚のカードの場合を考えましょう。 目標は
N 枚のカードにパーフェクト・シャッフルを行うと、何回で元の順番に戻るか?
ってのを調べるってことになります*3。 以下、数学嫌いな人は飛ばして下さい。
パーフェクト・シャッフル何回で元に戻る?
では実際に、「パーフェクト・シャッフル何回で元に戻るか?」を求めてみましょう。 パーフェクト・シャッフルの仕方から、トランプの枚数 は偶数とします。 回数を求める手順は以下の通り:- 1回のシャッフルでトランプがどのように移動するかを求める
- 回のシャッフルでトランプがどのように移動するかを求める
- 「 回のシャッフルで順番が元に戻る」という条件から、回数を求める
です。
★Step 1★ 1回のシャッフルでのトランプの移動
文章で説明してもわかりにくいので、図にしてみました。 真ん中の状態は便宜上のものです(カード1枚分ずつあけてあるって状態)。 前半分と後半分を1枚ずつ交互に混ぜる際、剰余演算子*4「%」が出てくるのがチョットややこしさを醸し出しますが。 ちなみに、カードの順番が0から始まっているのにご注意を。結果だけを書くと「n 番目にあったカードは、1回のシャッフルで に移動する」となります。
★Step 2★ 回のシャッフルでのトランプの移動
1回のシャッフルでカードがどう移動するか分かったので、これを 回適用すれば「 回のシャッフルでカードがどう移動するか」が分かります。剰余演算子(%)を含む式はチョット扱いにくそうですが、今の場合は簡単で、「 番目にあったカードは、 回のシャッフルで 番目に移動する」となります。
★Step 3★ 回のシャッフルで順番が元に戻る条件
上記の結果から、「 回のシャッフルで順番が元に戻る条件」は となります。 これを少々書き換えてやると*5、が自然数
となります。 これが任意の について成り立つためには、
が自然数
となります。 これが求める条件です。
のとき
のとき とすると、となって、確かに条件を満たします。 めでたしめでたし。
でも、一般の に対して を求めるのは結構手間が掛かるんですけどね。 これについては後日。
*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 が自然数」となります。