ひっくり返しシャフル

ひっくり返しシャフル(ひっくりかえししゃふる、英: topswops, reverse card shuffle)は、英国出身の数学者コンウェイの考案した一人用ゲーム 
。数字１から数字"n" までの合計"n" 枚のカードで遊ぶ。無限ループに入ることなく、 必ず有限回で終了する。 
ゲームのルール.
数字１から数字"n" までの合計"n" 枚のカードをよく切り、横１列に並べる。（サイズ"n" のゲームと呼ぶ。左端を一番上、右端を一番下と呼ぶ。）
以下のシャフル操作を繰り返す。 
一番上のカードが数字１以外の数字"k" ならば、１番上から"k" 番目までの 
"k" 枚のカードの数字の左右順番を反転する。 
一番上のカードが数字１なら終了する。 
4,2,1,3 → 3,1,2,4 → 2,1,3,4 → 1,2,3,4 となり、３回のシャフルで数字１が一番上にきて終了する。 　 
性質.
サイズ"n"のゲームの終了までの最大シャフル回数をformula_1とすると、 
formula_2、formula_3、formula_4、formula_5、formula_6である。 
基本的現象.
１つのゲーム中に一番上にくるカードの数字を 
主役の数字、決してこない数字を脇役の数字と呼ぶ。 
１つのゲームの開始状態で脇役の数字２つの位置を交換しても、 
ゲーム終了までのシャフル回数は同一である。
１つのゲームの主役の数字の種類を"t" 種類とし、"t" 種類中で最大の数字を"M" とする。 
最大主役の数字"M" がはじめて一番上にくると、以後２度と一番上にこない。 
他の主役の数字は"M" より小さいので、以後数字"M" の位置にシャフル範囲が及ばない。
１つのゲーム中で最大主役の数字"M" が一番上に出現した直後に主役となる数字を
重大主役の数字という。重大主役の数字はそのゲーム中で最大主役の主役登場後にはじめて一番上にくる。
重大主役は主役となるまでは上から"M" 番目の位置であった。
重大主役が数字１ならゲーム終了で、２以上の数字ならゲームは続く。 
最大主役の数字"M" が"M" 番目の位置で、重大主役の数字がはじめて一番上にいる状態からのゲームを
後半ゲームと呼ぶ。後半ゲームの主役の数字の種類は、もとのゲームの主役の数字の種類より
１以上小さい。
１つのゲームで"r" 回のシャフルではじめて最大主役の数字"M" 
が一番上に出現したとすると、開始状態の数字１と最大主役の数字"M" の位置を交換した開始状態で 
ゲームを開始すると、同じく"r" 回のシャフルで数字１が一番上にきてゲームが終了する。
このゲームを変形版前半ゲームと呼ぶ。 
変形版前半ゲームの主役の数字の種類は、もとのゲームの主役の数字の種類に比べ、
重大主役が１なら、最大主役がいないため１以上小さく、重大主役が2以上なら、最大主役と重大主役がいないため２以上小さい。