東京大学 2002年度 前期日程 第2次学力試験理系数学 第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回目は ${\displaystyle \{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$ について ${\displaystyle f(k)\equiv 2k(\mathrm{m}\mathrm{o}\mathrm{d}2N+1)}$ である。

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

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

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

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

位置は法 $2N+1$ で2倍

位置 $1,\dots ,2N$ を法 $2N+1$ の非零剰余として扱う。1回のシャッフルが剰余の2倍写像であることから、反復を一度に計算する。

(1) $$\begin{array}{rl}{\displaystyle }& {\displaystyle (1,2,3,4,5,6,7,8)}\\ {\displaystyle ⟼}& {\displaystyle (5,1,6,2,7,3,8,4)}\\ {\displaystyle ⟼}& {\displaystyle (7,5,3,1,8,6,4,2)}\\ {\displaystyle ⟼}& {\displaystyle (8,7,6,5,4,3,2,1)\mathrm{.}}\end{array}$$(2)
$1\leqq k\leqq N$ なら $f(k)=2k$、$N<k\leqq 2N$ なら$$f(k)=2(k-N)-1=2k-(2N+1)\mathrm{.}$$従って常に$$f(k)\equiv 2k(\mathrm{m}\mathrm{o}\mathrm{d}2N+1)\mathrm{.}$$(3)
$m$ 回後の位置を $f_m(k)$ とすれば、上の合同式を反復して$$f_m(k)\equiv 2^{m}k(\mathrm{m}\mathrm{o}\mathrm{d}2N+1)\mathrm{.}$$$N=2^{n-1}$ のとき$$2N+1=2^n+1,2^n\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}2N+1)\mathrm{.}$$従って$$f_{2n}(k)\equiv 2^{2n}k\equiv k(\mathrm{m}\mathrm{o}\mathrm{d}2N+1)\mathrm{.}$$$f_{2n}(k)$ と $k$ はともに $1,\dots ,2N$ の範囲にあるため実際に等しい。すべての $k$ が元の位置へ戻るので、数列全体も元に戻る。