次: 3. 阪大前期理系 上: 2. 解答 前: 5.

6.

(1)

$$\begin{array}{ll} 元\cdots& \{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8... ... 3回\cdots& \{8,\ 7,\ 6,\ 5,\ 4,\ 3,\ 2,\ 1\} \end{array}$$

(2) $1\le k \le N$ のとき，1回のシャッフルでこの範囲の各数の前に 数が１つずつおかれる．ゆえに f(k)=2k ． $N+1\le k \le 2N$ のとき．シャッフルを，この範囲の数をそのまま 前に持ってくる段階と， それぞれの数の後ろに $1\le k \le N$ にあった数を置く操作に分ける． 前半の操作でこの範囲の数 k はでまず左へ N 動かされ，k-N の位置に来る． その上で各数の後ろに数が１つずつおかれることになる．ゆえに f(k)=2(ｋ-N)-1=2k-(2N+1) いずれも f(k)-2k は 2N+1 の倍数である．

(3) 整数 a と b を 2N+1 でわった余りが等しいとき

$$a\equiv b$$

と書くことにする．

$$a\equiv b,\ c\equiv d$$

とする． このとき

$$\begin{array}{l} a=(2N+1)q_a+r_1,\ b=(2N+1)q_b+r_1\\ c=(2N+1)q_c+r_2,\ d=(2N+1)q_d+r_2 \end{array}$$

とおくと

$$\begin{array}{l} a+c=(2N+1)(q_a+q_c)+(r_1+r_2)\\ b+d=(2N... ...bd=(2N+1)^2q_bq_d+(2N+1)(q_br_2+q_dr_1)+r_1r_2 \end{array}$$

であるから

$$\begin{array}{l} a+c\equiv b+d\\ ac\equiv bd \end{array}$$

が成り立つ．ゆえに関係 $\equiv$ は和・差・積に関して，数の演算と同様にできる．

したがって(2)は $1,\ \cdots,\ 2N$の各 k に対して $f(k)\equiv 2k$ を意味している．

f^m(k) で m 回のシャッフルで数 k の現れる位置を表す．

$$f^m(k)\equiv 2^mk \quad \cdots\maru{1}$$

を数学的帰納法で示す． m=1のときは上の考察から成立．

m-1 のときの成立するとする．つまり $f^{m-1}(k)\equiv 2^{m-1}k$．

$$2f^{m-1}(k)\equiv 2^mk$$

m=1 のときの成立を k=f^m-1(k) で用いると

$$f(f^{m-1}(k))\equiv 2f^{m-1}(k)$$

f^m(k)=f(f^m-1(k))だから，あわせてm のときもが成立する． ゆえに正整数 m に対してが成立する． N=2^n-1 で m=2n でこの結果を用いる．

$$f^{2n}(k)\equiv 2^{2n}k=(2^n)^2k=(2N)^2k$$

ところが $2N\equiv -1$ であるから

$$(2N)^2k\equiv (-1)^2k=k$$

$$∴ \quad f^{2n}(k)\equiv k\quad \cdots\maru{2}$$

$1,\ 2,\ 3,\ \cdots,\ 2N$ はちょうど 2N+1 で割った余りから0を除いたものである． したがっては， 数列 $\{1,\ 2,\ 3,\ \cdots,\ 2N\}$ の各数が2n 回のシャッフルで， 元の位置に戻ること，つまり数列 $\{1,\ 2,\ 3,\ \cdots,\ 2N\}$が $\{1,\ 2,\ 3,\ \cdots,\ 2N\}$ に戻ることを示している．