東京大学 2002年度
理系数学 第6問

解答

(1)

$N=4$ である。はじめの数列 $\{1,2,3,4,5,6,7,8\}$ を $\{a_1,a_2,a_3,a_4,b_1,b_2,b_3,b_4\}$ と見ると、1回シャッフルして $\{5,1,6,2,7,3,8,4\}$ となる。

これをさらにシャッフルする。前半4項を $a_1,a_2,a_3,a_4$、後半4項を $b_1,b_2,b_3,b_4$ と見るので、2回目は $\{7,5,3,1,8,6,4,2\}$ である。さらに3回目は $\{8,7,6,5,4,3,2,1\}$ である。

(2)

まず $1\leqq k\leqq N$ とする。このとき、もとの数列のk番目の数kは $a_k$ である。シャッフル後、$a_k$ は $2k$ 番目に置かれるので $f(k)=2k$ である。したがって $f(k)-2k=0$ であり、これは $2N+1$ で割り切れる。

次に $N<k\leqq 2N$ とする。このとき $k=b_{k-N}$ である。シャッフル後、$b_{k-N}$ は $2(k-N)-1$ 番目に置かれるので $f(k)=2(k-N)-1=2k-(2N+1)$ である。したがって $f(k)-2k=-(2N+1)$ であり、これも $2N+1$ で割り切れる。

よって任意の $1\leqq k\leqq 2N$ について $f(k)\equiv 2k(\mathrm{mod}2N+1)$ である。

(3)

$m$ 回シャッフルした後に、数 $k$ が現れる位置を $f_m(k)$ とする。$m=1$ では(2)より $f_1(k)=f(k)\equiv 2k(\mathrm{mod}2N+1)$ である。

いま $f_m(k)\equiv 2^{m}k(\mathrm{mod}2N+1)$ と仮定する。次にもう1回シャッフルすると、位置も同じ規則で移るので $f_{m+1}(k)=f(f_m(k))\equiv 2f_m(k)\equiv 2^{m+1}k(\mathrm{mod}2N+1)$ である。よって帰納法により $f_m(k)\equiv 2^{m}k(\mathrm{mod}2N+1)$ がすべての正の整数 $m$ で成り立つ。

ここで $N=2^{n-1}$ だから $2N+1=2^n+1$ である。したがって $2^n\equiv -1(\mathrm{mod}2N+1)$ であり、両辺を2乗して $2^{2n}\equiv 1(\mathrm{mod}2N+1)$ である。よって $f_{2n}(k)\equiv 2^{2n}k\equiv k(\mathrm{mod}2N+1)$ となる。

最後に、$f_{2n}(k)$ も $k$ も $1$ 以上 $2N$ 以下の整数である。この範囲の2つの整数が $2N+1$ を法として合同なら、実際に等しい。したがって $f_{2n}(k)=k$ である。これはすべての $k$ で成り立つので、$2n$ 回シャッフルすると元の数列 $\{1,2,3,\dots ,2N\}$ にもどる。