ひっくり返しシャフル
ひっくり返しシャフル(ひっくりかえししゃふる、英: topswops, reverse card shuffle)は、英国出身の数学者コンウェイの考案した一人用ゲーム[1][2]。数字１から数字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のゲームの終了までの最大シャフル回数を とすると、 、 、 、 、 である。
- は2のべき乗 以下である。(Wilfの結果)
- は 番目のフィボナッチ数 以下である。 (Klamkinの結果)
- 特別なn の場合、サイズ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 が変形版前半ゲームである。