ひっくり返しシャフル

ひっくり返しシャフル(ひっくりかえししゃふる、英: topswops, reverse card shuffle)は、英国出身の数学者コンウェイの考案した一人用ゲーム 。数字１から数字n までの合計n 枚のカードで遊ぶ。無限ループに入ることなく、 必ず有限回で終了する。

ゲームのルール

数字１から数字n までの合計n 枚のカードをよく切り、横１列に並べる。（サイズn のゲームと呼ぶ。左端を一番上、右端を一番下と呼ぶ。） 以下のシャフル操作を繰り返す。

一番上のカードが数字１以外の数字k ならば、１番上からk 番目までの k 枚のカードの数字の左右順番を反転する。

一番上のカードが数字１なら終了する。

• 例　数字１から数字４までのカードで開始状態4,2,1,3から開始すると、

4,2,1,3 → 3,1,2,4 → 2,1,3,4 → 1,2,3,4 となり、３回のシャフルで数字１が一番上にきて終了する。 　

性質

• １以上のどんなサイズのどんな開始状態からはじめても必ず有限回のシャフルでゲームが終了する。

サイズnのゲームの終了までの最大シャフル回数を$T(n)$とすると、 $T(1)=0$、$T(2)=1$、$T(3)=2$、$T(4)=4$、$T(5)=7$である。

• $T(n)$は2のべき乗　$2^{n-1}$　以下である。(Wilfの結果)
• $T(n)$は$n+1$番目のフィボナッチ数 $F_{n+1}$以下である。 (Klamkinの結果) 　
• 特別なn の場合、サイズnのゲームがちょうど最大シャフル回数$T(n)$で終了すると、一番上から順に 数字１から数字nまでが小さい順に整列する。しかし一般には整列しない。

基本的現象

主役の数字と脇役の数字

１つのゲーム中に一番上にくるカードの数字を 主役の数字、決してこない数字を脇役の数字と呼ぶ。 １つのゲームの開始状態で脇役の数字２つの位置を交換しても、 ゲーム終了までのシャフル回数は同一である。

最大主役の数字

１つのゲームの主役の数字の個数をt 個とし、t 個中で最大の数字をM とする。 最大主役の数字M がはじめて一番上にくると、以後２度と一番上にこない。 他の主役の数字はM より小さいので、以後数字M の位置にシャフル範囲が及ばない。

重大主役の数字

１つのゲーム中で最大主役の数字M が一番上に出現した直後に主役となる数字を 重大主役の数字という。重大主役の数字はそのゲーム中で最大主役の主役登場後にはじめて一番上にくる。 重大主役は主役となるまでは上からM 番目の位置であった。 重大主役が数字１ならゲーム終了で、２以上の数字ならゲームは続く。

後半ゲーム

最大主役の数字M がM 番目の位置で、重大主役の数字がはじめて一番上にいる状態からのゲームを 後半ゲームと呼ぶ。後半ゲームの主役の数字の個数は、もとのゲームの主役の数字の個数より １以上小さい。

変形版の前半ゲーム

１つのゲームでr 回のシャフルではじめて最大主役の数字M が一番上に出現したとすると、開始状態の数字１と最大主役の数字M の位置を交換した開始状態で ゲームを開始すると、同じくr 回のシャフルで数字１が一番上にきてゲームが終了する。 このゲームを変形版前半ゲームと呼ぶ。 変形版前半ゲームの主役の数字の個数は、もとのゲームの主役の数字の個数に比べ、 重大主役が１なら、最大主役がいないため１以上小さく、重大主役が2以上なら、最大主役と重大主役がいないため２以上小さい。

• 例　ゲーム 3,1,4,5,2 → 4,1,3,5,2 → 5,3,1,4,2 → 2,4,1,3,5 → 4,2,1,3,5 → 3,1,2,4,5 → 2,1,3,4,5 → 1,2,3,4,5 の最大主役の数字は５で、重大主役の数字は２である。最大主役5は一度一番上にくると２度と一番上にこない。重大主役2は、最大主役5によるシャフルで一番上にくるので、それ以前は一番上にこない。2,4,1,3,5から終了までのゲームが後半ゲームで、開始状態の数字１と最大主役の数字5を交換したゲーム3,5,4,1,2 → 4,5,3,1,2 → 1,3,5,4,2　が変形版前半ゲームである。

的中数字の総得点

数字jが上からj番目の位置にいる場合、この数字jを的中数字と呼ぶ。 的中数字に得点を与え、上から１番目なら1点、2番目なら2点、 3番目なら4点、...、 j番目なら$2^{j-1}$点を与え、 的中数字すべての得点の合計を総得点と呼ぶ。 ひっくり返し操作を1回行うと、その前後で総得点は2点以上増加する。

• 例　的中数字をカッコで示すと、ゲーム

3,1,4,5,2 → 4,1,(3),5,2 → 5,3,1,(4),2 → 2,4,1,3,(5) → 4,(2),1,3,(5) → 3,1,2,(4),(5) → 2,1,(3),(4),(5) → (1),(2),(3),(4),(5)　において、 総得点は、開始時の0点から、4点増加、4点増加、8点増加、２点増加、6点増加、4点増加、3点増加で、終了時31点になっている。