パーフェクト・シャッフル
52枚のトランプの山を半分に分け、26枚ずつにする。この2つの山を1枚1枚互い違いに挟み込むようにシャッフルする。つまり、
1,2,3,4,5,6....26 27,28,29,30....52
という2つの山を
27,1,28,2,29,3....
というふうにシャッフルする。これをパーフェクト・シャッフルと呼ぶ。ふつうの人間がやると2、3枚重なってしまうかもしれないけど、訓練したマジシャンは、ある程度これができちゃうらしいことをYouTubeで発見して驚いた(8 Perfect Faro Shuffles)。
ともあれ、シャッフルするカードの枚数をnとすると、何度かパーフェクト・シャッフルすると、元の並びに必ず戻る。このとき、必要なシャッフルの回数はn回以下になる。
シャッフルの過程で現れるパターンが非常に面白い。 例えば10枚の場合、次のようになる。
% ./perfect.rb 10 [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [6, 1, 7, 2, 8, 3, 9, 4, 10, 5], [3, 6, 9, 1, 4, 7, 10, 2, 5, 8], [7, 3, 10, 6, 2, 9, 5, 1, 8, 4], [9, 7, 5, 3, 1, 10, 8, 6, 4, 2], [10, 9, 8, 7, 6, 5, 4, 3, 2, 1], [5, 10, 4, 9, 3, 8, 2, 7, 1, 6], [8, 5, 2, 10, 7, 4, 1, 9, 6, 3], [4, 8, 1, 5, 9, 2, 6, 10, 3, 7], [2, 4, 6, 8, 10, 1, 3, 5, 7, 9], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]] It takes 10 perfect shuffles.
1に注目すると、その位置は1,2,4,8……と放物線のように動いていく。16は10を超えているのでぐるっと回ってその剰余。よくよく見ていると、編み込まれた毛糸のようなパターンが見て取れる。
8枚の場合、次のようになる。
% ./perfect.rb 8 [[1, 2, 3, 4, 5, 6, 7, 8], [5, 1, 6, 2, 7, 3, 8, 4], [7, 5, 3, 1, 8, 6, 4, 2], [8, 7, 6, 5, 4, 3, 2, 1], [4, 8, 3, 7, 2, 6, 1, 5], [2, 4, 6, 8, 1, 3, 5, 7], [1, 2, 3, 4, 5, 6, 7, 8]] It takes 6 perfect shuffles.
縦の列を見ると3と6の欄は交互に交代しているだけで、特定の数字が現れる列は決まっている。このようにグループ別に色をつけて、スカーフの柄にした人がいる。面白い。
n枚のカードを何回パーフェクト・シャッフルしたら元に戻るか、事前にそれをnから予測することはできないか、少なくともそのような計算式は知られていないという。まるで素数のようだ。あるいはパイこね変換。
というわけで、n < 5800について調べてみた。1万まで調べようと思ったけど、ずいぶん時間がかかったので、途中でプログラムの実行を止めてしまった。考えてみたら計算量のオーダーはO(n^2)だ。結果は以下の通り。傾きの異なる線が6、7本ほど見える。
#!/usr/bin/env ruby # # perfect shuffle # # [1,2,3,4,5,6] -> [1,2,3] , [4,5,6] -> [4,1,5,2,6,3] def perfect_shuffle(deck) if deck.size.odd? then raise("deck can't be perfect-shuffled.") end middle = deck.size / 2 fhalf = deck[0, middle] lhalf = deck[middle, deck.size] lhalf.zip(fhalf).flatten end n = ARGV.shift.to_i deck = (1..n).to_a patterns = [] patterns << deck while true new_deck = perfect_shuffle(patterns.last) patterns << new_deck if new_deck == deck then break end end require 'pp' pp patterns print "It takes #{patterns.size - 1} perfect shuffles.\n"
