次: 2. 解答 上: 1. 問題 前: 5.

6.

N を正の整数とする． 2N 個の項からなる数列

$$\{a_1,\ a_2,\ \cdots,\ a_N,\ b_1,\ b_2,\ \cdots,\ b_N\}$$

を

$$\{b_1,\ a_1,\ b_2,\ a_2,\ \cdots,\ b_N,\ a_N\}$$

という数列に並べ替える操作を「シャッフル」と呼ぶことにする．並べ替えた数列は b₁ を初項とし， b_i の次に a_i ， a_i の次に b_i+1 が来るようなものになる． また，数列 $\{1,\ 2,\ \cdots,\ 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) 数列 $\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8\}$ を3解シャッフルしたときに 得られる数列を求めよ．

(2) $1\le k\le 2N$ を満たす任意の整数 k に対し， f(k)-2k は 2N+1 で割りきれることを示せ．

(3) n を正の整数とし， N=2^n-1 のときを考える． 数列 $\{1,\ 2,\ 3,\ \cdots,\ 2N\}$ を 2n 回シャッフルすると， $\{1,\ 2,\ 3,\ \cdots,\ 2N\}$ に戻ることを証明せよ．