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



前回の記事 “パーフェクト・シャッフル#1” の内容の補足と,そのあとに判った事実についてのメモ.まさかの続編.

スポンサーリンク

再定義

まずは定義について,より数学らしく表現する方法を載せる.前回の定義と同値な定義のはずである.ただし,奇数あるいは偶数のどちらかについて調べれば良さそうだと判断したため,$N$ が偶数のときのみを定義する.

Def 1.1-ex

$N (\geqq 2)$ を偶数とする.パーフェクト・シャッフル $P\colon\mathbb{R}^N \to \mathbb{R}^N$ を
\[
P(\left[
\begin{array}{c}
c_{1} \\
c_{2} \\
c_{3} \\
c_{4} \\
\vdots \\
c_{N-1} \\
c_{N}
\end{array}
\right]) =
\left[
\begin{array}{c}
c_{1} \\
c_{\frac{m}{2}+1} \\
c_{2} \\
c_{\frac{m}{2}+2} \\
\vdots \\
c_{\frac{m}{2}} \\
c_{\frac{m}{2}+\frac{m}{2}}
\end{array}
\right]
\]
によって定める.

 

Th 1.2-ex

$N (\geqq 2)$ を偶数とし, $\boldsymbol{x}_i \in \mathbb{R}^N ~(i = 0, 1,2,\ldots)$ を
\[
\boldsymbol{x}_0 = \left[
\begin{array}{c}
1 \\
2 \\
\vdots \\
N
\end{array}
\right]
~,\quad \boldsymbol{x}_{i+1} = P(\boldsymbol{x}_i)
\]
で定まる列とするとき
\[
\boldsymbol{x}_M = \boldsymbol{x}_0
\]
を満たす最小の自然数 $M = M_{(N)}$ が存在する.

 

このようにしてみると,Th 1.2-ex で与えた漸化式に対して,その表現行列を得ることができる.実際 $N = 6$ のときは
\[
\boldsymbol{x_{i+1}} =
\left[
\begin{array}{cccccc}
1&0&0&0&0&0\\
0&0&0&1&0&0 \\
0&1&0&0&0&0 \\
0&0&0&0&1&0 \\
0&0&1&0&0&0 \\
0&0&0&0&0&1
\end{array}
\right] \boldsymbol{x}_n
\]
となるのである.より一般に
\[
\boldsymbol{x_{i+1}} = A\boldsymbol{x_{i}}
\]
となる $N \times N$ 表現行列 $A = (a_{ij})$ は
\[
a_{ij} =
\left\{
\begin{array}{cl}
1 & ~~j = 2i-1 ~~ or ~~ j = 2i-N \\
0 & ~~{\rm otherwise}
\end{array}
\right.
\]
である.

 

結果考察

$N = 502$ までの検証の結果である.$N$ がこれより大きくなったときに,異なる結果となる可能性がある.

$N$ 枚のカードが初期配置にもどるまでに必要なパーフェクト・シャッフルの回数を $T(N)$ とする.

[1] $N = 2^k$ のとき,初期配置にもどるまでに必要な回数 $T(2^k)$ は $k$ 回である.また,この値はすべて極小値である.

[2] 上の結果をもとに $y = \log_{2}{x}$ のグラフを書き入れたところ
\[
T(N) \geqq \log_{2}{N}
\]
であることがわかった.すなわち,$2^k$ 枚のカードを用いたときがもっともリカバリー効率が高い.

[3] $N = 2^k + 2$ のとき,初期配置にもどるまでに必要な回数は $2k$ 回である.すなわち,もっともはやく初期配置にもどるような枚数にたった2枚加えただけで,その2倍の回数を必要とするのである.

[4] $4$ 以上のすべての偶数 $N$ に対して
\[
T(N) \leqq N-2
\]
であることもわかった.もっとも回数が必要なパターンと思われる.ただし,$N = 0,2$ の場合はどちらも1回でもどることになるが,面白くないので除外した.

なお,このパターンに該当する $N$ の値は
\[
N = 4,6,12,14,20,30,38,54,60,62,68,84,102,108,132,140,150,164,174,180,182,198,212,228,270,294,\ldots
\]
とつづく.4は最大効率でもあるが,これは4枚以上が正常にシャフルが意味をなすことを示していると思われる.また,$N$ が奇数のときの結果は偶数 $N+1$ のときと等しかったから
\[
T(N) \leqq N-1
\]
となり,該当するパターンは
\[
N = 3,5,11,13,19,29,37,53,59,61,67,83,101,107,131,139,149,163,173,179,181,197,211,227,269,293,\ldots
\]
となる.抜けているところがあるが,すべて素数のようだ.抜けているところについては今のところ,$T(N)$ が
\[
T(N) \leqq \frac{N-1}{2}
\]
を満たしていることだけがわかっている.今回はここまで.

 

今回の結論

少なくとも $4 \leqq N \leqq 512$ の範囲では,偶数 $N$ に対して
\[
\log_{2}{N} \leqq T(N) \leqq N-2
\]
が成り立つ.


スポンサーリンク