パーフェクト・シャッフル　其ノ弐

前回、 ${ N }$ 枚のトランプを ${ m }$ 回パーフェクト・シャッフルしたら元に戻るとき、 ${ N }$ と ${ m }$ との間で満たされるべき条件を導きました：

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

「 ${ N }$ が与えられたとき、この条件を満たす ${ m }$ を求める」ってのが目標です。

簡単な場合として、 ${ N }$ がある自然数 ${ k }$ を使って「 ${ N = 2^k }$ 」と書けるとき、「 ${ m = k }$ 」となります。　例えば、 ${ 16\;(= 2^4) }$ のとき、4回のパーフェクト・シャッフルで元に戻ります。

前回の最後に書いたように、上式を使って一般の ${ N }$ の場合に ${ m }$ を求めるのは結構メンドクサイ計算です。　なので、もう少し見通しのある ${ m }$ の計算方法を見ていきましょう。　そこそこ手間は掛かりますが・・・

着目する点は、 ${ 2^m - 1 }$ を2進数で表すと*1

　　 ${ [2^2 - 1]_2 = 111\cdots1 }$

と、「1」が ${ m }$ 個並ぶことです。

${ m }$ を求める手順の概要は以下の通り：

一般的な場合を説明するのは大変なので、次節で具体例を計算するにとどめます。

前節の手順に従って、「 ${ N = 12 }$ 」の場合に具体的にやってみましょう。

${ N-1 = 11 }$ なので、11=8+2+1 より

　　 ${ [11]_2 = 1011 }$

ここが一番手間の掛かる計算。　2進数の足し算に慣れればどうってこともないんですが。

やることは、「1011」に、「1011」の桁を左にずらしたものをどんどん足していって、最終的に全てが「1」になるようにすることです。　この際、一番右（位が低い）の「0」から順に消していきましょう。　具体的には次のように、筆算で計算すると良いでしょう：

「1011」の場合は、最終的に「1」だけになったとき、それが10個連なってました。　よって、 ${ N = 12 }$ （トランプ12枚）では10回のパーフェクト・シャッフルで元の順番に戻ることが分かります。

一応、 ${ N }$ が与えられたときに ${ m }$ を計算する方法の説明は完了。　一般には、この計算は結構手間ですが、簡単にこの計算ができる ${ N }$ の値というのはどんなものでしょうか？

まず最初に思いつくのは、既に ${ [N-1]_2 }$ が「1」のみの場合です。　これは（この記事の最初にも書いた）「 ${ N = 2^k }$ 」と書ける場合です。　これは、桁をずらして足したりする必要がありません。　結果は「 ${ m = k }$ 」となります。

また、その次の偶数「 ${ N = 2^k + 2 }$ 」も比較的簡単に計算できます。　この場合は、 ${ N-1 }$ を2進数で表すと「 ${ 100 \cdots 001 }$ 」（0が ${ k-1 }$ 個）となるので、（計算は省きますが）「 ${ m = 2k }$ 」となります。

次に、桁を1つだけずらす様な場合、例えば「10101」のように「1」と「0」が交互になっているような場合です。　結果だけ書くと、「 ${ N = (4^k + 2)/3 \; (k \ge 2) }$ 」*2のとき「 ${ m = 2k }$ 」となります。

さて、「 ${ N = 52 }$ 」の場合はどうなっているんでしょうか？　実際に計算してみると ${ [N-1]_2 = [51]_2 = 110011 }$ となっていて、これは桁を2つずらすだけで「1」の並びになります。　これは比較的特別な値（数の並び）と言っていいでしょう。

ちなみに ${ N = 50 }$ の場合は ${ m = 21 }$ 、 ${ N = 52 }$ の場合は ${ m = 52 }$ になりました。　やはり ${ N = 52 }$ は特別！

*1: ${ [\dots]_2 }$ は10進数の数字...を2進数で表した数字です： ${ [5]_2 = 101 }$

*2:小さい値のものを幾つか書き下しておくと、6, 22, 86, 342 となっています。

倭マン's BLOG