N を正の整数とする．2N 個の項からなる数列
{ a
1 , a
2 , …… , a
N , b
1 , b
2 , …… , b
N }
を
{ b
1 , a
1 , b
2 , a
2 , …… , b
N , a
N }
という数列に並べ替える操作を「シャッフル」と呼ぶことにする．並べ替えた数列は b
1 を初項とし，b
i の次に a
i ，a
i の次に b
i+1 が来るようなものになる．また，数列 { 1 , 2 , …… , 2N } をシャッフルしたときに得られる数列において，数 k が現れる位置を f(k) で表す．
たとえば，N = 3 のとき，{ 1 , 2 , 3 , 4 , 5 , 6 } をシャッフルすると{ 4 , 1 , 5 , 2 , 6 , 3 } となるので，f(1) = 2 , f(2) = 4 , f(3) = 6 , f(4) = 1 , f(5) = 3 , f(6) = 5 である．
（１） 数列 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } を3 回シャッフルしたときに得られる数列を求めよ．
（２） 1≦k≦2N を満たす任意の整数 k に対し， f(k)−2k は 2N＋1 で割り切れることを示せ．
（３） n を正の整数とし，N = 2
n−1 のときを考える．数列 { 1 , 2 , 3 , …… , 2N } を 2n 回
シャッフルすると，{ 1 , 2 , 3 , …… , 2N } にもどることを証明せよ．
（１）元の並び → { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }
シャッフル１回 → { 5 , 1 , 6 , 2 , 7 , 3 , 8 , 4 }
シャッフル２回 → { 7 , 5 , 3 , 1 , 8 , 6 , 4 , 2 }
シャッフル３回 → {
8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 }
（２）1≦k≦N のとき f(k)＝2k より f(k)−2k＝0
N+1≦k≦2N のとき f(k)＝2(k−N)−1 より f(k)−2k＝−2N−1
どちらも 2N＋1 の倍数。
（３） （… これは、証明よりも、結論を楽しめば良いことにしましょう）
