東大入試数学理系2002より

　N を正の整数とする．2N 個の項からなる数列
　　　{ a₁ , a₂ , …… , a_N , b₁ , b₂ , …… , b_N }
を
　　　{ b₁ , a₁ , b₂ , a₂ , …… , b_N , a_N }
という数列に並べ替える操作を「シャッフル」と呼ぶことにする．並べ替えた数列は b₁ を初項とし，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ⁿ⁻¹ のときを考える．数列 { 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 の倍数。

（３）　（… これは、証明よりも、結論を楽しめば良いことにしましょう）